# Lucas Sequence 盧卡斯數列

> Author:堇姬

# 定義
$D=P^2-4Q>0 (P,Q \in \mathbb{Z})$
$x^2-Px+Q=0$
其根為$a,b$

定義Lucas Sequence

### 第一類Lucas Sequence
$U_n(P,Q)=\frac {a^n-b^n}{a-b}$

$U_0(P,Q)=0$
$U_1(P,Q)=2$

### 第二類Lucas Sequence
$V_n(P,Q)=a^n+b^n$

$V_0(P,Q)=1$
$V_1(P,Q)=P$

# 一些特性
1. $V_{m+n}=V_m V_n-Q^n V_{m-n}$
2. $V_{2n}=V_n^2-2Q^n$
3. $V_{mn}(P,Q)=V_m(V_n(P,Q),Q^n)$

# 證明
### 證明 $V_{m+n}=V_m V_n-Q^n V_{m-n}$
---
$V_{m+n}=V_m V_n-Q^n V_{m-n}$
$a^{m+n}+b^{m+n}=(a^m+b^m)(a^n+b^n)-(ab)^n(a^{m-n}+b^{m-n})$
$a^{m+n}+b^{m+n}=a^{m+n}+a^mb^n+a^nb^m+b^{m+n}-a^mb^n-a^nb^m$
$a^{m+n}+b^{m+n}=a^{m+n}+b^{m+n}$

### 證明 $V_{2n}=V_n^2-2Q^n$
---
$V_{2n}=V_n^2-2a^n b^n$ (Vieta's formulas, $a+b=P,ab=Q$)
$a^{2n}+b^{2n}=(a^{n}+b^{n})^2-2a^n b^n$
$a^{2n}+b^{2n}=(a^{2n}+b^{2n}+2a^n b^n)-2a^n b^n$
$a^{2n}+b^{2n}=a^{2n}+b^{2n}$

### 證明 $V_{mn}(P,Q)=V_m(V_n(P,Q),Q^n)$
---
$x^2-Px+Q=0$
其根為$a,b$

$x^2-(a^n+b^n)x+(a^nb^n)=0$
其根為$r,s$

$V_{mn}(P,Q)=V_m(V_n(P,Q),Q^n)$
$a^{mn}+b^{mn}=V_m(a^n+b^n,a^nb^n)$
$a^{mn}+b^{mn}=r^m+s^m$

$r,s=\frac{(a^n+b^n) \pm \sqrt{(a^n+b^n)^2-4a^nb^n}}{2}$
$r,s=\frac{(a^n+b^n) \pm \sqrt{(a^n-b^n)^2}}{2}$
$r,s=\frac{(a^n+b^n) \pm (a^n-b^n)}{2}$
$r=\frac{(a^n+b^n) + (a^n-b^n)}{2}=a^n$
$s=\frac{(a^n+b^n) - (a^n-b^n)}{2}=b^n$
代回到$a^{mn}+b^{mn}=r^m+s^m$得證