Fibonacci 数列的一些性质
Karry5307
·
·
个人记录
设 f_n 表示 Fibonacci 数列，满足 f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}。
通项公式：
f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)
其中设 \phi=\dfrac{1+\sqrt{5}}{2},\hat{\phi}=\dfrac{1+\sqrt{5}}{2}。（后面 Pisano Period 有用）
生成函数：
\sum_{i=0}^{\infty}f_ix^i=\frac{1}{1-x-x^2}
1.
\sum\limits_{i=0}^{n}f_i=f_{i+2}-1
对 n 归纳，显然当 n=0 时成立，当 n\geq 1 时有：
\sum\limits_{i=0}^{n}f_i=f_{i+1}-1+f_i=f_{i+2}-1
证毕，或者可以使用生成函数：
\sum\limits_{i=0}^{\infty}\left(\sum_{j=0}^{i}f_j\right)x^i=\frac{1}{(1-x-x^2)(1-x)}=\frac{1}{1-2x+x^3}
右边为
\sum\limits_{i=0}^{\infty}(f_{i+2}-1)x^i=\frac{\dfrac{1}{1-x-x^2}-1-x}{x^2}-\frac{1}{1-x}=\frac{1}{1-2x+x^3}
证毕。
2.
\sum\limits_{i=0}^{n}f_i^2=f_{i}f_{i+1}
对 n 归纳，显然当 n=0 时成立，当 n\geq 1 时有：
\sum\limits_{i=0}^{n}f_i^2=f_{n-1}f_{n}+f_n^2=f_nf_{n+1}
GF 的话，我不知道怎么表示 f^2_n 的生成函数，所以没有。
3.
\sum\limits_{i=0}^{n}f_i^3=\frac{f_nf_{n+1}^2+(-1)^{n-1}f_{n-1}+1}{2}
我不是很会证/kk
鱼鱼那个 我不是很会/wq
4.
\sum\limits_{i=0}^{n}f_{2i+1}=f_{2n+2}
对 n 归纳，显然当 n=0 时成立，当 n\geq 1 时有：
\sum\limits_{i=0}^{n}f_{2i+1}=f_{2n}+f_{2n-1}=f_{2n+2}
证毕。
5.
\sum\limits_{i=0}^{n}f_{2i}=f_{2n+1}-1
对 n 归纳，显然当 n=0 时成立，当 n\geq 1 时有：
\sum\limits_{i=0}^{n}f_{2i}=f_{2n-1}-1+f_{2n}=f_{2n+1}-1
证毕。