费波纳切数列的前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)