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也类似;

上一篇:bzoj1485: [HNOI2009]有趣的数列(Catalan数)


下一篇:nlp总结