递推法在计数中的应用之一
数学的核心思想，我们从小学开始依次接触到算术思想、代数思想、函数思想，高中最重要的应该是递推思想：处理和自然数n有关的命题时，我们难以直接得到结果，退而求其次，如果能得到n与n-1,n-2…等前面的结果有关的等式（即递推公式），下面再计算出最终结果，也是一种常用而重要的方法。这有点像《老子》里面说的：道生一、一生二、二生三、三生万物的味道，也是数学归纳法的精髓。下面通过例题介绍递推方法在计数中的应用：
1、有一个楼梯，有8个台阶，小明每次走一个或两个台阶，则他有多少种不同的走法。
思路分析：解决此问题要么通过列举（台阶数较少的时候），要么通过递推，很难直接算出结果。下面我们通过递推思路算出一般的结果。
注：此题是很经典的问题，我在带儿子上小学二年级升三年级的奥数课上都看到他们以此作为例题。上述数列是著名而经典的斐波那契数列（也称为兔子数列），许多问题都与之有关，当然可以用特征方程算出本题的通项公式为：
2、有一个楼梯，有8个台阶，小明每次走一个、两个或三个台阶，则他有多少种不同的走法。
思路分析：与上题类似，继续通过递推，得到递推公式。
注：此题也是很经典的问题，是上述问题的配套练习。其特征方程是三次方程，三个根中有虚数，不过理论上也能用三个根的n次线性关系表示出其通项公式。
3、切面条问题：一根面条，依次用刀切k次，最多能将其分成多少段？
解：这个很简单显然是k 1.
4、切饼问题：一个饼，用刀切n次，最多能将其切成多少块？
思路分析：这个可以列举找规律，但是这样不严谨。也可以通过排列组合直接计算。不过比较自然的方法还是递推。
注：1）显然此问题等价于n条直线最多将圆（或者平面）分成多少块。
2）容易发现本题中增加的块数即为上题中切面条数。这也是很容易理解的，因为由上述证明过程知增加的块数即为n-1各点分此直线的块数。
5、切西瓜问题： 一个西瓜，用刀切4次，最多能将其切成多少块？n次呢？
思路分析：这是三维问题，十分考察空间想象力。不难想象1刀2块，2刀最多4块，3刀最多8块（相当于空间直角坐标系的八卦限）。4刀就很难想象了。找规律16块不太靠谱，估计达不到。按上一题的思路先三刀切成7块，再横着切一刀得到14块似乎又不够多，所以猜测15块是比较合理的。下面从空间想象、对应计算、递推等三个方向提供三个思路。
思路解法一：空间想象，三刀最多切成8块，得到一个空间坐标系的八卦限模型，第四刀要增加的块数最多，必须此刀所在平面尽可能多的与前面8块相交，不可能与8块都相交，因为由对称性不妨设此平面在原点上方，则下面四块至少有1块与此平面不相交，当然容易作出与7块都相交的平面，从而增加了7块，即4刀最多将西瓜切成15块。
思路解法二：对应计算。4刀切完以后，会形成一个四面体，将此四面延伸为平面。则此四面体有4个顶点，形成每个顶点相邻三个面延长后在四面体的“外部”会形成1块，故这样的块有4块。此四面体有6个棱，形成每个棱的两面延长后在四面体的外部会形成一块，故这样的块有6块。此四面体有4个面，形成每个三角形面的三个面延长后在四面体外部会形成一块，故这样的块有4块。最后此四面体有一个体，故还有一块。综上共有4 6 4 1=15块，即4刀最多将西瓜切成15块。
思路解法三：递推。前三刀最多将西瓜切成8块。第四刀要增加最多的块数，一定和前面的块数尽可能多的相交，我们只需考虑第四刀所在的平面切西瓜的截面，显然是个圆。此平面每经过一个区域，则此区域在此平面上交出一块来，反之亦然。即此圆面上的每一个小块与增加的块数一一对应。而增加的块数即为前面3个平面在第4个平面上的投影（显然是3条直线）截此平面的最多块数，由上一题知为7.从而增加了7块，即4刀最多将西瓜切成15块。
对于一般的结果，感觉还是第三个思路比较自然，
注：1）显然此问题等价于n个平面最多将球（或者空间）分成多少块。
2）容易发现本题中增加的块数即为上题中切饼数。这也是很容易理解的，因为由上述递推过程就是将增加的块数转化为用直线分平面的个数问题。
当然不用组合恒等式，直接拼凑也不难理解，因为二次式当然是三次式相邻两项的差（一般称为差分），下面只要待定一下系数即可。
当然类似的组合恒等式还有很多。
4）4刀切西瓜问题是一个非常经典的问题，我第一次接触是初中时看到一本《有趣的数学》上面的一道趣题，第一次接触会觉得难以想象。毕竟人类的大脑皮层是二维的，对于三维的问题普遍缺乏想象力，可能人类天生就没有空间想象能力。此问题我也经常给学生讲，初次接触本题的学生一般都很难理解和想象。当然可以自己在家里用西瓜或者苹果等做实验来验证本结果。我儿子小学一年级升二年级的暑假期间，报了一个小学奥数班，我作为家长在教室后面听课，老师讲得很好，课堂上就讲了上述切饼问题，后来老师又说到切西瓜问题，提问学生4刀切西瓜问题。当时我很惊讶。因为这个问题对于他们1年级的学生绝对是太难了！因为高中学生和成人都很难想象和理解。不过后来老师讲了她的答案是14块，即像切饼一样先3刀切成7块然后再横着一刀每块分成两块得到14块。课后我与老师交流时指出了这个错误。并建议她以后这个问题不给低年级的小学生讲。
6、切糕问题：一块蛋糕边缘有10颗樱桃，每两个樱桃之间切上1刀，最多能将此蛋糕切成多少块？
思路分析：本题相当于：圆周上有10个点两两连线最多将圆面分成多少块？直接计算略有些困难，一般会找规律，很容易算出来：0点1块，1点2块，2点4块，3点8块，4点16块，…很容易猜测n点2^n块。看似很合理，事实上这个结论是错误的，一般的这种分块的计数问题的结果通常是多项式函数，不会像指数函数增长这么快。
如何验证呢？只能继续列举，不难数出6个点时最多将圆分成31块（如果三条对角线共点则30块，块数最多时显然不能有三线共点）。如果继续往下数，7个点时是57块。所以上述猜想是错误的。
那到底有什么规律呢？
写出这列数：1，2，4，8，16，31，57；
基本规律就是相邻两项做差（差分）：用后一项减去前一项，依次为：1，2，4，8，15，26；
如果嫌规律还不够强，还可以继续如法炮制，再减一次，为：1，2，4，7，11，
再减一次为：1，2，3，4，…
规律就很明显了，最后一个为正整数列，从而一步一步递推，可以得到10个点两两连线最多能将圆面分成256块（而不是原来猜测的512块）。
聪明的读者可能已经发现，上述结果中第一次的差分数列其实就是第5题的切西瓜数列，第二次的差分数列是第4题的切饼数列，第三次的差分数列是第3题的切面条数列。当然我们可以继续按上题结果进行求和：
不难检验，上述通项公式是正确的，不过这个推理过程显然是有瑕疵的，因为我们后面的规律也是找到的，并没有严格证明，所以这个证明还是有问题的。
下面提供三个不同的思路对本题给出证明：
思路一：递推
解法一：设n个点依次为前n-1个点两两连线已经将圆周分成块，对于第n个点，要使得其与其他点连线分成的块数最多，则不能有三线共点，与的连线与其他的线段都要相交，直线一侧有i-1个点，另一侧有n-1-i个点，只有异侧的两点间连线才会与相交，这样的连线数为(i-1)( n-1-i),相应的交点个数为(i-1)( n-1-i)，而增加的块数还要再加1，为(i-1)( n-1-i) 1，从而我们可以得到递推公式为：
殊途同归，得到了与以上相同的递推公式，以下如法炮制，即可得到其通项公式为
思路二：用平面欧拉公式V-E F=1，其中V、E、F分别对应平面上简单多边形的顶点数、边数、和面数。
思路三：直接建立一一对应
注：1）本题难度较高，很经典。答案也比较有迷惑性。如果找规律，很容易掉入陷阱之中，当然本题也是一个经典的反例。告诉大家单纯靠找规律有时候会犯错误。
2）3、4、5、6四个题目难度依次增加，后面一题依次是上一题求和得到。其中3、4、5其实分别是相应的一维（直线）、二维（平面）、三维（空间）中相应的情景，依次用递推的思想和方法转化为更简单、更低纬度中的情形加以解决。很好地体现了“道生一、一生二、二生三、三生万物”的递推思想。第6题虽然结果也是第5题求和得到，但是无法类似前面问题，直接递推转化到第5题中情形。因此只能另起锅灶，重新证明。我们给出了三种证明方式。证明一递推的思想比较容易想到，只是中间计算略有些复杂，一不小心就会出现问题。证明二巧妙利用平面欧拉公式、建立对应加以解决。不过中间计算棱数E的时候也颇费周折。证明三按图索骥，直接建立对应。算是神来之笔，过程似乎很简洁，不过不是很好想到，也不是很好理解。
