“斐波那契数列”的发明者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci，生于公元1170年，卒于1240年。籍贯大概是比萨）。他被人称作“比萨的列昂纳多”。1202年，他撰写了《珠算原理》(Liber Abaci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯研究数学。
斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21……
这个数列从第三项开始，每一项都等于前两项之和。它的通项公式为：(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}（又叫“比内公式”，是用无理数表示有理数的一个范例。）【√5表示根号5】
很有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的。
比如：随着数列项数的增加，前一项与后一项之比越逼近黄金分割0.6180339887……
还有一项性质，从第二项开始，每个奇数项的平方都比前后两项之积多1，每个偶数项的平方都比前后两项之积少1。
如果你看到有这样一个题目：某人把一个8*8的方格切成四块，拼成一个5*13的长方形，故作惊讶地问你：为什么64＝65？其实就是利用了斐波那契数列的这个性质：5、8、13正是数列中相邻的三项，事实上前后两块的面积确实差1，只不过后面那个图中有一条细长的狭缝，一般人不容易注意到。
如果任意挑两个数为起始，比如5、-2.4，然后两项两项地相加下去，形成5、-2.4、2.6、0.2、2.8、3、5.8、8.8、14.6……等，你将发现随着数列的发展，前后两项之比也越来越逼近黄金分割，且某一项的平方与前后两项之积的差值也交替相差某个值。
斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。
1.排列组合.
有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?
这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……
1，2，3，5，8，13……所以，登上十级，有89种
2.数列中相邻两项的前项比后项的极限.
就是问，当n趋于无穷大时，F(n)/F(n+1)的极限是多少？
这个可由它的通项公式直接得到，极限是(1-√5)/2，这个就是所谓的黄金分割点，也是代表大自然的和谐的一个数字。
3.求递推数列a(n)=1,a(n+1)=1+1/a(n).的通项公式.
由数学归纳法可以得到：a(n)=F(n+1)/F(n).将菲波那契数列的通项式代入，化简就得结果。
斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。
斐波那契数列
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？
我们不妨拿新出生的一对小兔子分析一下：
第一个月小兔子没有繁殖能力，所以还是一对;
两个月后，生下一对小兔民数共有两对;
三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对;
－－－－－－
依次类推可以列出下表：
经过月数：0123456789101112
兔子对数：1123581321345589144233
表中数字1，1，2，3，5，8－－－构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。
这个数列是意大利中世纪数学家斐波那契在＜算盘全书＞中提出的，这个级数的通项公式，除了具有a(n+2)=an+a(n+1)/的性质外，还可以证明通项公式为：an=1/√[（1＋√5/2) n-(1-√5/2) n](n=1,2,3.....）
斐波那契数列：1，1，2，3，5，8，13，21……
如果设F(n)为该数列的第n项(n∈N+)。那么这句话可以写成如下形式：
F(1)=F(2)=1,F(n)=F(n-1)+F(n-2) (n≥3)
显然这是一个线性递推数列。
通项公式的推导方法一：利用特征方程
线性递推数列的特征方程为：
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
则F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2
C1*X1^2 + C2*X2^2
解得C1=1/√5，C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】
通项公式的推导方法二：普通方法
设常数r,s
使得F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]
则r+s=1, -rs=1
n≥3时，有
F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]
F(n-1)-r*F(n-2)=s*[F(n-2)-r*F(n-3)]
F(n-2)-r*F(n-3)=s*[F(n-3)-r*F(n-4)]
……
F(3)-r*F(2)=s*[F(2)-r*F(1)]
将以上n-2个式子相乘，得：
F(n)-r*F(n-1)=[s^(n-2)]*[F(2)-r*F(1)]
∵s=1-r，F(1)=F(2)=1
上式可化简得：
F(n)=s^(n-1)+r*F(n-1)
那么：
F(n)=s^(n-1)+r*F(n-1)
= s^(n-1) + r*s^(n-2) + r^2*F(n-2)
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) + r^3*F(n-3)
……
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)*F(1)
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)
（这是一个以s^(n-1)为首项、以r^(n-1)为末项、r/s为公差的等比数列的各项的和）
=[s^(n-1)-r^(n-1)*r/s]/(1-r/s)
=(s^n - r^n)/(s-r)
r+s=1, -rs=1的一解为 s=(1+√5)/2, r=(1-√5)/2
则F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
main()
{
long fib[40] = {1,1};
int i;
for(i=2;i<40;i++)
{
fib[i ] = fib[i-1]+fib[i-2];
}
for(i=0;i<40;i++)
{
printf("F%d==%d\n", i, fib);
}
return 0;
}
var
fib: array[0..40]of longint;
i: integer;
begin
fib[0] := 1;
fib[1] := 1;
for i:=2 to 39 do
fib[i ] := fib[i-1] + fib[i-2];
for i:=0 to 39 do
write('F', i, '=', fib[i ]);
end.
对于斐波那契数列1,1,2,3,5,8,13…….有如下定义
F(n)=f(n-1)+f(n-2)
F(1)=1
F(2)=1
对于以下矩阵乘法
F(n+1) = 1 1 * F(n)
F(n) 1 0 F(n-1)
它的运算就是
F(n+1)=F(n)+F(n-1)
F(n)=F(n)
可见该矩阵的乘法完全符合斐波那契数列的定义
设1 为B，1 1为C
1 1 0
可以用迭代得到:
斐波那契数列的某一项F(n)=(BC^(n-2))1
这就是斐波那契数列的矩阵乘法定义.
另矩阵乘法的一个运算法则A¬^n(n为偶数)=A^(n/2)* A^(n/2).
因此可以用递归的方法求得答案.
时间效率：O(logn)，比模拟法O(n)远远高效。
代码（PASCAL）
{变量matrix是二阶方阵, matrix是矩阵的英文}
program fibonacci;
type
matrix=array[1..2,1..2] of qword;
var
c,cc:matrix;
n:integer;
function multiply(x,y:matrix):matrix;
var
temp:matrix;
begin
temp[1,1]:=x[1,1]*y[1,1]+x[1,2]*y[2,1];
temp[1,2]:=x[1,1]*y[1,2]+x[1,2]*y[2,2];
temp[2,1]:=x[2,1]*y[1,1]+x[2,2]*y[2,1];
temp[2,2]:=x[2,1]*y[1,2]+x[2,2]*y[2,2];
exit(temp);
end;
function getcc(n:integer):matrix;
var
temp:matrix;
t:integer;
begin
if n=1 then exit(c);
t:=n div 2;
temp:=getcc(t);
temp:=multiply(temp,temp);
if odd(n) then exit(multiply(temp,c))
else exit(temp);
end;
procedure init;
begin
readln(n);
c[1,1]:=1;
c[1,2]:=1;
c[2,1]:=1;
c[2,2]:=0;
if n=1 then
begin
writeln(1);
halt;
end;
if n=2 then
begin
writeln(1);
halt;
end;
cc:=getcc(n-2);
end;
procedure work;
begin
writeln(cc[1,1]+cc[1,2]);
end;
begin
init;
work;
end.
F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ]
其中[ x ]表示取距离 x 最近的整数。
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
21 17711
22 28657
23 46368
24 75025
25 121393
26 196418
27 317811
28 514229
29 832040
30 1346269
31 2179309
32 3524578
33 5702887
34 9227465
35 14930352
36 24157817
37 39088169
38 63245986
39 102334155
40 165580141
41 267914296
42 433494437
43 701408733
44 1134903170
45 1836311903
46 2971215073
47 4807526976
48 7778742049
49 12586269025
50 20365011074
51 32951280099
52 53316291173
53 86267571272
54 139583862445
55 225851433717
56 365435296162
57 591286729879
58 956722026041
59 1548008755920
60 2504730781961
61 4052739537881
62 6557470319842
63 10610209857723
64 17167680177565
65 27777890035288
66 44945570212853
67 72723460248141
68 117669030460994
69 190392490709135
70 308061521170129
71 498454011879264
72 806515533049393
73 1304969544928657
74 2111485077978050
75 3416454622906707
76 5527939700884757
77 8944394323791464
78 14472334024676221
79 23416728348467685
80 37889062373143906
81 61305790721611591
82 99194853094755497
83 160500643816367088
84 259695496911122585
85 420196140727489673
86 679891637638612258
87 1100087778366101931
88 1779979416004714189
89 2880067194370816120
90 4660046610375530309
91 7540113804746345429
92 12200160415121876738
......
斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21……
这个数列从第三项开始，每一项都等于前两项之和。它的通项公式为：(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}（又叫“比内公式”，是用无理数表示有理数的一个范例。）【√5表示根号5】
很有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的。
比如：随着数列项数的增加，前一项与后一项之比越逼近黄金分割0.6180339887……
还有一项性质，从第二项开始，每个奇数项的平方都比前后两项之积多1，每个偶数项的平方都比前后两项之积少1。
如果你看到有这样一个题目：某人把一个8*8的方格切成四块，拼成一个5*13的长方形，故作惊讶地问你：为什么64＝65？其实就是利用了斐波那契数列的这个性质：5、8、13正是数列中相邻的三项，事实上前后两块的面积确实差1，只不过后面那个图中有一条细长的狭缝，一般人不容易注意到。
如果任意挑两个数为起始，比如5、-2.4，然后两项两项地相加下去，形成5、-2.4、2.6、0.2、2.8、3、5.8、8.8、14.6……等，你将发现随着数列的发展，前后两项之比也越来越逼近黄金分割，且某一项的平方与前后两项之积的差值也交替相差某个值。
斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。
1.排列组合.
有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?
这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……
1，2，3，5，8，13……所以，登上十级，有89种
2.数列中相邻两项的前项比后项的极限.
就是问，当n趋于无穷大时，F(n)/F(n+1)的极限是多少？
这个可由它的通项公式直接得到，极限是(1-√5)/2，这个就是所谓的黄金分割点，也是代表大自然的和谐的一个数字。
3.求递推数列a(n)=1,a(n+1)=1+1/a(n).的通项公式.
由数学归纳法可以得到：a(n)=F(n+1)/F(n).将菲波那契数列的通项式代入，化简就得结果。
斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。
斐波那契数列
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？
我们不妨拿新出生的一对小兔子分析一下：
第一个月小兔子没有繁殖能力，所以还是一对;
两个月后，生下一对小兔民数共有两对;
三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对;
－－－－－－
依次类推可以列出下表：
经过月数：0123456789101112
兔子对数：1123581321345589144233
表中数字1，1，2，3，5，8－－－构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。
这个数列是意大利中世纪数学家斐波那契在＜算盘全书＞中提出的，这个级数的通项公式，除了具有a(n+2)=an+a(n+1)/的性质外，还可以证明通项公式为：an=1/√[（1＋√5/2) n-(1-√5/2) n](n=1,2,3.....）
斐波那契数列：1，1，2，3，5，8，13，21……
如果设F(n)为该数列的第n项(n∈N+)。那么这句话可以写成如下形式：
F(1)=F(2)=1,F(n)=F(n-1)+F(n-2) (n≥3)
显然这是一个线性递推数列。
通项公式的推导方法一：利用特征方程
线性递推数列的特征方程为：
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
则F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2
C1*X1^2 + C2*X2^2
解得C1=1/√5，C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】
通项公式的推导方法二：普通方法
设常数r,s
使得F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]
则r+s=1, -rs=1
n≥3时，有
F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]
F(n-1)-r*F(n-2)=s*[F(n-2)-r*F(n-3)]
F(n-2)-r*F(n-3)=s*[F(n-3)-r*F(n-4)]
……
F(3)-r*F(2)=s*[F(2)-r*F(1)]
将以上n-2个式子相乘，得：
F(n)-r*F(n-1)=[s^(n-2)]*[F(2)-r*F(1)]
∵s=1-r，F(1)=F(2)=1
上式可化简得：
F(n)=s^(n-1)+r*F(n-1)
那么：
F(n)=s^(n-1)+r*F(n-1)
= s^(n-1) + r*s^(n-2) + r^2*F(n-2)
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) + r^3*F(n-3)
……
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)*F(1)
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)
（这是一个以s^(n-1)为首项、以r^(n-1)为末项、r/s为公差的等比数列的各项的和）
=[s^(n-1)-r^(n-1)*r/s]/(1-r/s)
=(s^n - r^n)/(s-r)
r+s=1, -rs=1的一解为 s=(1+√5)/2, r=(1-√5)/2
则F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
main()
{
long fib[40] = {1,1};
int i;
for(i=2;i<40;i++)
{
fib[i ] = fib[i-1]+fib[i-2];
}
for(i=0;i<40;i++)
{
printf("F%d==%d\n", i, fib);
}
return 0;
}
var
fib: array[0..40]of longint;
i: integer;
begin
fib[0] := 1;
fib[1] := 1;
for i:=2 to 39 do
fib[i ] := fib[i-1] + fib[i-2];
for i:=0 to 39 do
write('F', i, '=', fib[i ]);
end.
对于斐波那契数列1,1,2,3,5,8,13…….有如下定义
F(n)=f(n-1)+f(n-2)
F(1)=1
F(2)=1
对于以下矩阵乘法
F(n+1) = 1 1 * F(n)
F(n) 1 0 F(n-1)
它的运算就是
F(n+1)=F(n)+F(n-1)
F(n)=F(n)
可见该矩阵的乘法完全符合斐波那契数列的定义
设1 为B，1 1为C
1 1 0
可以用迭代得到:
斐波那契数列的某一项F(n)=(BC^(n-2))1
这就是斐波那契数列的矩阵乘法定义.
另矩阵乘法的一个运算法则A¬^n(n为偶数)=A^(n/2)* A^(n/2).
因此可以用递归的方法求得答案.
时间效率：O(logn)，比模拟法O(n)远远高效。
代码（PASCAL）
{变量matrix是二阶方阵, matrix是矩阵的英文}
program fibonacci;
type
matrix=array[1..2,1..2] of qword;
var
c,cc:matrix;
n:integer;
function multiply(x,y:matrix):matrix;
var
temp:matrix;
begin
temp[1,1]:=x[1,1]*y[1,1]+x[1,2]*y[2,1];
temp[1,2]:=x[1,1]*y[1,2]+x[1,2]*y[2,2];
temp[2,1]:=x[2,1]*y[1,1]+x[2,2]*y[2,1];
temp[2,2]:=x[2,1]*y[1,2]+x[2,2]*y[2,2];
exit(temp);
end;
function getcc(n:integer):matrix;
var
temp:matrix;
t:integer;
begin
if n=1 then exit(c);
t:=n div 2;
temp:=getcc(t);
temp:=multiply(temp,temp);
if odd(n) then exit(multiply(temp,c))
else exit(temp);
end;
procedure init;
begin
readln(n);
c[1,1]:=1;
c[1,2]:=1;
c[2,1]:=1;
c[2,2]:=0;
if n=1 then
begin
writeln(1);
halt;
end;
if n=2 then
begin
writeln(1);
halt;
end;
cc:=getcc(n-2);
end;
procedure work;
begin
writeln(cc[1,1]+cc[1,2]);
end;
begin
init;
work;
end.
F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ]
其中[ x ]表示取距离 x 最近的整数。
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
21 17711
22 28657
23 46368
24 75025
25 121393
26 196418
27 317811
28 514229
29 832040
30 1346269
31 2179309
32 3524578
33 5702887
34 9227465
35 14930352
36 24157817
37 39088169
38 63245986
39 102334155
40 165580141
41 267914296
42 433494437
43 701408733
44 1134903170
45 1836311903
46 2971215073
47 4807526976
48 7778742049
49 12586269025
50 20365011074
51 32951280099
52 53316291173
53 86267571272
54 139583862445
55 225851433717
56 365435296162
57 591286729879
58 956722026041
59 1548008755920
60 2504730781961
61 4052739537881
62 6557470319842
63 10610209857723
64 17167680177565
65 27777890035288
66 44945570212853
67 72723460248141
68 117669030460994
69 190392490709135
70 308061521170129
71 498454011879264
72 806515533049393
73 1304969544928657
74 2111485077978050
75 3416454622906707
76 5527939700884757
77 8944394323791464
78 14472334024676221
79 23416728348467685
80 37889062373143906
81 61305790721611591
82 99194853094755497
83 160500643816367088
84 259695496911122585
85 420196140727489673
86 679891637638612258
87 1100087778366101931
88 1779979416004714189
89 2880067194370816120
90 4660046610375530309
91 7540113804746345429
92 12200160415121876738
......