-
Fibonacci 数列的定义是：\(F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}(n>1)\)。
-
Lucas 数列的定义是：\(L_0=2,L_1=1,L_n=L_{n-1}+L_{n-2}(n>1)\)。
发现它们的定义十分相似。
通项公式
对于 Fibonacci 数列，我们有：
\[F_n={\dfrac{(\dfrac{1+\sqrt 5}{2})^n-(\dfrac{1-\sqrt 5}{2})^n}{\sqrt 5}}
\]
对于 Lucas 数列，我们有：
\[L_n = {(\dfrac{1+\sqrt 5}{2})^n + (\dfrac{1-\sqrt 5}{2})^n}
\]
生成函数法
定义Lucas 数列的生成函数 \(L(x)\)。由递推式，我们有：
\[\begin{aligned}
L(x) &= x^2L(x)+xL(x)+2-x\L(x) &= \dfrac{2-x}{1-x-x^2}
\end{aligned}
\]
我们考虑通过等比数列的生成函数来表示 \(L(x)\)。用待定系数法，设有：
\[\dfrac{A}{1-ax}+\dfrac{B}{1-bx} = \dfrac{2-x}{1-x-x^2} \\]
可以得到：
\[\begin{cases}
A+B=2 \Ab+aB=1 \a+b=1 \ab=-1 \\end{cases}
\]
解得
\[\begin{cases}
A=1 \B=1 \a = \dfrac{1+\sqrt 5}{2} \b = \dfrac{1-\sqrt 5}{2}
\end{cases}
\]
所以
\[L(x)=\sum_{n \ge 0}\left((\dfrac{1+\sqrt 5}{2})^n+(\dfrac{1-\sqrt 5}{2})^n\right)x^n \L_n = (\dfrac{1+\sqrt 5}{2})^n+(\dfrac{1-\sqrt 5}{2})^n
\]
同样地，对于 Fibonacci 数列，我们有：
\[\begin{aligned}
F(x) &= x^2F(x)+xF(x)+x \F(x) &= \dfrac{x}{1-x-x^2}
\end{aligned}
\]
待定系数，解得
\[\begin{cases}
A=\dfrac{1}{\sqrt 5} \B=-\dfrac{1}{\sqrt 5} \a = \dfrac{1+\sqrt 5}{2} \b = \dfrac{1-\sqrt 5}{2}
\end{cases}
\]
所以有
\[F(x)=\sum_{n \ge 0}\dfrac{1}{\sqrt 5}\left((\dfrac{1+\sqrt 5}{2})^n-(\dfrac{1-\sqrt 5}{2})^n\right)x^n \F_n = \dfrac{1}{\sqrt 5}\left((\dfrac{1+\sqrt 5}{2})^n-(\dfrac{1-\sqrt 5}{2})^n\right)
\]
斐波那契数列与卢卡斯数列
原文：https://www.cnblogs.com/Lewis-Li/p/Fibonacci_Lucas.html
