Fibonacci数列的性质

Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, .... F[0] = 0;

1: gcd(Fn, Fm) = F[gcd(n, m)]; 当n - m = 1 或 2时满足，可用数学归纳法证明；

2: 特征方程为 x^2 = x + 1, 类Fibonacci数列的特征方程为：ax^2 = bx + c; aF[n] = bF[n - 1] + cF[n - 2];

3: (证明方法为补项和数学归纳法)

f[0] + f[1] + ... + f[n] = f[n + 2] - 1;

f[0] + f[2] + ... + f[2n] = f[2n + 1] - 1;

f[1] + f[3] + ... + f[2n - 1] = f[2n];

f[0] ^ 2 + f[1] ^ 2 + ... f[n] ^ 2 = f[n] * f[n + 1];

f[n] ^ 2 = (-1) ^ (n + 1) + f[n - 1] * f[n + 1];

f[2n] = f[n] * (f[n + 1] + f[n - 1]);

4: f[n] % x = 0 则 f[n * k] % x = 0; k 为整数;

5: lim n -> oo f[n + 1] / f[n] = 0.618.... , 证明方法为递推式两边取比值，然后求极限

6: 斐波那契数列的第n+2项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数, 证明：考虑第n个数，有f[n] = f[n - 1] + f[n - 2], 边界通过 f[1] = 2确定;

7: 与组合数的关系：F(n)=C(n-1,0)+C(n-2,1)+…+C(n-1-m,m) (m<=n-1-m), 将杨辉三角斜对角求和，组成Fibonacci数列

8: 对于质数P, f[n] % P 有循环节，如果5是模P的二次剩余，则循环节长度是P - 1的因子，否则是2(P + 1)的因子; 类Fibonacci也类似；

巴特西