本文参考了组合数学课件，精简整理了一下内容并谈谈自己的理解

设{ an a n }为一序列，把该序列中 an a n 和它前面几个 ai a i (0≤i≤n)关联起来的方程称做一个递推关系（递归关系）。 类似于 a0 a 0 =1， a1 a 1 =1的叫做初值 初值+递推关系=带初值的递推关系 说白了就是用前面推出来的值推出当前值，然后再推出后面的值的一个递推式，和dp的递推式差不多。

设这n条直线将圆分成的区域数为 an a n ，如果有n-1条直线将圆分成 an−1 a n − 1 个区域，那么再加入第n条直线与在圆内的其他n-1条直线相交。显然，这条直线在圆内被分成n条线段，而每条线段又将第n条直线在圆内经过的区域分成两个区域。这样，加入第n条直线后，圆内就增加了n个区域。而对于n=0，显然有 a0 a 0 =1，所以有如下递推公式： an=an−1+n(n>=1) a n = a n − 1 + n ( n >= 1 ) a0=1 a 0 = 1 展开可以看出类似等差数列，化简后得： an=n∗(n+1)+22 a n = n ∗ ( n + 1 ) + 2 2

用 an a n 表示从一根柱子上的 n n 个圆盘全部转移到另一根柱子上的转移次数。显然，a1=1a1=1, a2=3 a 2 = 3 。当 n≥3 n ≥ 3 时，要将柱子A上的 n n 个圆盘转移到柱子C上，可以这样设想。先把柱子A上的n−1n−1个圆盘转移到柱子B上，这需要转移 an−1 a n − 1 次；然后把柱子A上最后一个圆盘转移到柱子C上，显然这需要转移一次；最后再把柱子B上的n-1个圆盘转移到柱子C上，这也需要转移 an−1 a n − 1 次。到此时转移完毕，一共转移了 2an−1+1 2 a n − 1 + 1 次。于是可以建立如下带初值的递推关系: an=2an−1+1(n>=2) a n = 2 a n − 1 + 1 ( n >= 2 ) a1=1 a 1 = 1

设第 n n 个月时养殖场中兔子的对数为FnFn。并定义 F0=1 F 0 = 1 ，显然有， F1=1 F 1 = 1 。 由于在第 n n 个月时，除了有第n−1n−1个月时养殖场中的全部兔子 Fn−1 F n − 1 外，还应该有 Fn−2 F n − 2 对新兔子，这是因为在第 n−2 n − 2 个月就已经有的每对兔子，在第 n n 个月里都应生一对新的兔子。因此可以建立如下带初值的递推关系. Fn=Fn−1+Fn−2Fn=Fn−1+Fn−2 F0=F1=1 F 0 = F 1 = 1 该数列即为Fibonacci数列

设这 n n 个圆将平面分成anan个区域。易知， a1=2,a2=4 a 1 = 2 , a 2 = 4 。 现在假设前 n−1 n − 1 个圆将平面分成了 an−1 a n − 1 个区域，当加入第 n n 个圆(虚线圆)时，由题设这个圆与前面的n−1n−1个圆一定交于 2(n−1) 2 ( n − 1 ) 个点，这 2(n−1) 2 ( n − 1 ) 个点把第n个圆分成 2(n−1) 2 ( n − 1 ) 条弧，而每条弧正好将前面的 n−1 n − 1 个圆分成的区域中的其经过的每个区域分成 2 2 个区域，故新加入的第nn个圆使所成的区域数增加了 2(n−1) 2 ( n − 1 ) 。因此可以建立如下带初值的递推关系： an=an−1+2(n−1) a n = a n − 1 + 2 ( n − 1 ) a1=2 a 1 = 2

设不同的结合方式数为 an a n 。定义 a1=1 a 1 = 1 ，显然有 a2=1 a 2 = 1 。 由于对乘积 b1×b2×…×bn b 1 × b 2 × … × b n 的任一结合方式，必有某一个k使得最后的运算为积 b1×b2×…×bk b 1 × b 2 × … × b k 与积 bk+1×bk+2×…×bn b k + 1 × b k + 2 × … × b n 相乘。当k 固定时，对乘积 b1×b2×…×bk b 1 × b 2 × … × b k 有 ak a k 种不同的结合方式，而对乘积 bk+1×bk+2×…×bn b k + 1 × b k + 2 × … × b n 有 an−k a n − k 种不同的结合方式。由乘法法则知，对某一个 k k 共有ak∗an−kak∗an−k 种不同的结合方式。再由加法法则即得如下带初值的递推关系： an=∑n−1k=1ak∗an−k a n = ∑ k = 1 n − 1 a k ∗ a n − k a1=1,a2=1 a 1 = 1 , a 2 = 1