每日一题系列：斐波那契数列（不断更新题解）

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：

递推公式

通项公式

通项公式推导

此问题的线性递推数列属于二阶线性递推数列（n+2 -  n = 2）

由上可知，斐波那契数列递推公式的特征方程为：

解得    

则 ，，

斐波那契数列的性质

与黄金分割的关系

有趣的是，这样一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当 n 趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割 0.618（或者说后一项与前一项的比值小数部分越来越逼近 0.618）

平方与前后项关系

从第二项开始，每个偶数项的平方都比前后两项之积少 1，每个奇数项的平方都比前后两项之积多 1，也就是： 

                                             

或

                                              

两倍项的关系

                             

与集合子集的关系

斐波那契数列的第n+2项同时也代表了集合中所有不不包含相邻正整数的子集个数。

比如，n = 3, 第n+2项 为 5，此时 中所有不不包含相邻正整数的子集为 空集、{1}、{2}、{3}、{1，3}

项求和性质

斐波那契数列值的快速求法

                                                            

其中[x]表示取距离x最近的整数。

数学问题

1. 有一段楼梯有10 级台阶，规定每一步只能跨一级或两级，要登上第10 级台阶有几种不同的走法?

首先考虑登上第一级有一种走法（{1}），登上第二级种走法（{1，1}，{2}），我们知道，由于最后一步同样只能跨一级或者两级，登上第三阶有两种情况，

• 最后一步跨一级
• 最后一步跨两级

所以它的走法数就等于两种情况相加，也就是前两级的走法数相加（）。

2. 一枚均匀的硬币掷10次，问不连续出现正面的可能情形有多少种？

3. 求递推数列的通项公式？

4. 一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

和台阶问题类似，从一开始是新出生的一对小兔子，可得：

可见，从第三个月兔子具有繁殖能力开始，因为成兔对数，等于上月的成兔对数+上月的幼仔对数（是由上上月的成兔生的，经过两个月变成了成兔）。所以，当月的幼兔对数 等于 上月的成兔对数，也就等于上上月的兔子对数，再加 上月的兔子对数 就是当月的兔子对数。是符合斐波那契数列的性质的。

斐波那契数列的矩阵乘法定义

设矩阵A=第一行（1，1）第二行（1，0） 迭代n次可以得到：

                           F(n+ 1) =  （0，1）* A^(F(2)，F(1))T = （0，1）* A^( n ) * (1,1)T