常见数列归纳与分析

1.斐波那契数列

P.S.:此处首项下标设定为 1

递推公式：F_i=F_{i-1}+F_{i-2},F_1=F_2=1

特性：
1.\sum^{n}_{i=1}F_{i}=F_{n+2}-1

2.\sum^{n}_{i=1}F_i^2=F_n\ F_{n+1}

3.\sum_{i=1}^{n}i\ F_i=n\ F_{n+2}-F_{n+3}+2

4.F_{n+m}=F_n\ F_{m-1}+F_{m}\ F_{n+1}

5.F_{2n}/F_{n}=F_{n-1}+F_{n+1}

6.gcd(F_i,F_{i+1})=1

7.gcd(F_n,F_m)=F_{gcd(n,m)}

8.斐波那契数列中的第 n+2 项表示集合 {1,2,...,n} 中所有不含相邻正整数的子集的数量.

---

2.卡特兰数

P.S. 此处首项的下标设定为0

递推公式：
C_n=\sum_{i=0}^{n-1} C_iC_{n-i-1},C_0=C_1=1

常见递推公式：
C_n=\frac{C_{n-1}*(4*n-2)}{n+1}

其他形式的递推表达式：
C_n=\frac{2n\choose n}{n+1}
$C_n={2n \choose n}-{ 2n \choose