定义

斐波那契数，又称黄金分割数列。
递推公式是： F(n)=F(n−1)+F(n−2) <script id="MathJax-Element-23" type="math/tex">F(n)=F(n-1)+F(n-2)</script>.

推导通项公式

设常数 r <script id="MathJax-Element-2" type="math/tex">r</script>和s<script id="MathJax-Element-3" type="math/tex">s</script>，使得 F(n)−r×F(n−1)=s×[F(n−1)−r×F(n−2)] <script id="MathJax-Element-4" type="math/tex">F(n)-r\times F(n-1)=s\times [F(n-1)-r\times F(n-2 )]</script>
所以 r+s=1,−r×s=1 <script id="MathJax-Element-5" type="math/tex">r+s=1,-r\times s=1</script>
在 3≤n <script id="MathJax-Element-6" type="math/tex">3\leq n</script>的时候，有

<script id="MathJax-Element-7" type="math/tex; mode=display">\begin{align} F(n)-rF(n-1)&=s\times [F(n-1)-r\times F(n-2)]\\ F(n-1)-rF(n-2)&=s\times [F(n-2)-r\times F(n-3)]\\ F(n-2)-rF(n-3)&=s\times [F(n-3)-r\times F(n-4)]\\ ……&\ ……\\ F(3)-rF(2)&=s\times [F(2)-r\times F(1)]\\ \end{align}</script>
联立解方程组得到：
<script id="MathJax-Element-8" type="math/tex; mode=display">F(n)-r\times F(n-1)=s^{n-2}\times [F(2)-r\times F(1)]</script>
因为 <script id="MathJax-Element-9" type="math/tex; mode=display">s=1-r,F(1)=F(2)=1</script>
上式可化简得：
<script id="MathJax-Element-10" type="math/tex; mode=display">F(n)=s^{n-1}+r\times F(n-1)</script>
那么：
<script id="MathJax-Element-11" type="math/tex; mode=display">\begin{align} F(n)&=s^{n-1}+r\times F(n-1)\\ &=s^{n-1}+r\times s^{n-2}+r^2\times F(n-2)\\ &……\\ &=s^{n-1}+r\times s^{n-2}+r^2\times s^{n-3}+…+r^{n-2}\times r^{n-1}\\ \end{align}</script>
所以这是个等比数列的和。
也就是 <script id="MathJax-Element-12" type="math/tex; mode=display">=\frac{s^n-r^n}{s-r}</script>
因为 r+s=1,−rs=1 <script id="MathJax-Element-13" type="math/tex">r+s=1,-rs=1</script>，所以一组解是
<script id="MathJax-Element-14" type="math/tex; mode=display">s=\frac {1+\sqrt 5}{2}</script>
<script id="MathJax-Element-15" type="math/tex; mode=display">r=\frac {1-\sqrt 5}{2}</script>
则 <script id="MathJax-Element-16" type="math/tex; mode=display">F(n)=\frac {\sqrt 5}{5}[(\frac {1+\sqrt 5}{2})^n-(\frac {1-\sqrt 5}{2})^n]</script>

性质

相邻互质

gcd(Fn,Fn−1)=1 <script id="MathJax-Element-17" type="math/tex">gcd(F_n,F_{n-1})=1</script>
证明：
由于 gcd(Fn,Fn−1)=gcd(Fn−1,Fn−2)=…=F1=1 <script id="MathJax-Element-18" type="math/tex">gcd(F_n,F_{n-1})=gcd(F_{n-1},F_{n-2})=…=F1=1</script>
（利用欧几里得算法可以证明）

任意两项的gcd

gcd(Fm,Fn)=Fgcd(n,m) <script id="MathJax-Element-19" type="math/tex">gcd(F_m,F_n)=F_{gcd(n,m)}</script>
证明：
当 m=n <script id="MathJax-Element-20" type="math/tex">m=n</script>显然成立。

练习题

斐波那契中的gcd
斐波那契变式1
斐波那契数列的最小公倍数问题
题解