斐波那契数列 – 一些性质与推论

广义斐波那契数列

定义：任何形如$f_i=f_{i-1}+f_{i-2}, f_1=x,f_2=y$的数列，称为广义斐波那契数列。

$F_1=F_2=1$的斐波那契数列的通项公式

$$F_n=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]$$

证明方法多样，可惜我都不会。知乎 – 斐波那契通项公式是怎样推导出来的？

下文中以$F_n$代指斐波那契数列的第$n$项，$f_n$代表广义斐波那契数列的第$n$项。

性质与推论

$$\sum\limits_{i=1}^{n}f_i=f_{n+2}+f_{2}$$

证明：数学归纳法。

考虑以下等式：$$\begin{aligned}& f_1=x,f_2=y, \newline
& f_3=f_1+f_2, \newline
& f_4=f_3+f_2=f_1+f_2+f_2, \newline
& f_5=f_4+f_3=f_3+f_2+f_1+f_2, \newline
& f_6=f_5+f_4=f_4+f_3+f_2+f_1+f_2, \newline
& \dots \\
& f_n=f_{n-2}+f_{n-1}=\sum\limits_{i=1}^{n-3}f_i+f_{n-2}+f_2\end{aligned}$$

对于广义斐波那契数列$f_n=f_{n-1}+f_{n-2}, f_1=x,f_2=y$，我们有$$f_n=F_{n-2}\times x+F_{n-1}\times y$$

证明：数学归纳法。

考虑$$\begin{aligned}& f_1=x, f_2=y, \\
& f_3=x+y, \\
& f_4=x+2y, \\
& f_5=2x+3y, \dots \end{aligned}$$

对于$f_3,f_4$，有$f_3=F_1\times x+F_2 \times y, f_4=F_2\times x+F_3\times y$，则有$$\begin{aligned}f_5 & =f_3+f_4\\
& =(F_1+F_2)\times x+(F_2+F_3)\times y\\
& =F_3 \times x+F_4 \times y \end{aligned}$$。故由数学归纳法可知原命题成立。

对于广义斐波那契数列$f$，有$f_{n+m}=f_nF_{m-1}+f_{n+1}F_m$。

证明：

定义一新数列$f’$，有$f’_1=f_n,f’_2=f_{n+1}$，故由上一推论可得$$\begin{aligned}f’_{m+1}& =f_{n+m}\\
& =f’_1\times F_{m-1}+f’_2\times F_m \\
& =f_nF_{m-1}+f_{n+1}F_m\end{aligned}$$，得证。

练习：CF446C DZY Loves Fibonacci Numbers