Question

写一个求Fibonacci数列前n项和的函数.

Answer 1

首先求Fibonacci通项公式：
递推式：
a n+1=a n+a n-1
特征方程：
x^2-x-1=0
特征根：
a=二分之（1+根号5）,b=二分之（1-根号5）.则
an=(a^n-b^n)/根号5
前n项和就是两个等比数列求和(a^n和b^n的求和).
sn=[a^2-b^2-a^(n+2)+b^(n+2)]/(根号5*ab)