费波纳切数列的前N项和公式大家都知道费波纳切数列1,1,2,3,5,8,13（第三项是前两相的和）试问这个数列 的前N项

引:
Fibonacci数列{an}满足递推关系:
(a0=0,) a1=1,a2=1,a(n)=a(n-1)+a(n-2),n>=3.
Fibonacci数列的通项(过程见(***))
an=(r^n-s^n)/(r-s),其中r,s=(1±√5)/2,附:r-s=√5
本题:求Fibonacci数列的前n项和Sn
a(n+2)=a(n+1)+a(n)
a(n+1)=a(n)+a(n-1)
a(n)=a(n-1)+a(n-2)
...
a(5)=a(4)+a(3)
a(4)=a(3)+a(2)
a(3)=a(2)+a(1)
易得:
a(n+2)=a(n)+a(n-1)+...+a1+a2
即a(n+2)=Sn+a2
故Sn=a(n+2)-1=(r^(n+2)-s^(n+2))/(r-s) - 1,
其中r,s=(1±√5)/2,附:r-s=√5
注:其特例:
a3=a1+a2=S1+a2
a4=(a2+a1)+a2=S2+a2
a5=(a2+a1)+(a3+a2)=S3+a2
(***)
Fibonacci数列{an}满足递推关系:
(a0=0,) a1=1,a2=1,a(n)=a(n-1)+a(n-2),n>=3.
Fibonacci数列的通项
首先我们由已知条件来构造等比数列.
令a(n)-r*a(n-1)=s(a(n-1)-r*a(n-2)) (#1)
与已知比较得:r+s=1,rs=-1 (##)
易得r,s=(1±√5)/2,附:r-s=√5
同时,(#1)式等价于以下(#2)式(从##式中r,s的对称性也可看出):
a(n)-s*a(n-1)=r(a(n-1)-s*a(n-2)) (#2)
(#1)得：a(n)-r*a(n-1)=s^(n-1)*(a1-r*a0) (#3)
(#2)得：a(n)-s*a(n-1)=r^(n-1)*(a1-s*a0)) (#4)
[注1：#3式很容易推得:{a(n)-r*a(n-1)}是公差为s的等比数列;]
[注2：#1,#3式中,s的指数与a的下标之和相等.这是递推式的一个小小技巧.
#1式中,s^1,a(n-1);#3式中,s^n,a0]
(#3,#4)联立得:(r-s)a(n-1)=r^(n-1)-s^(n-1)
从而：a(n)=(r^n-s^n)/(r-s)
代入r,s,即可.