【附】为方便有需要者编辑，特附纯文本如后。另外，文末提供有PPT照片版。
跃峰奥数PPT1代数组合3-1
（研究特例建立递归之组合论证）
所谓递归，就是建立“n”的问题与“小于n”的若干同构子问题之间的等量关系。通常有如下6种递归方式：
（1）增减元递归，在“n”的情形中减去（通常是固定其取值）或增加一个元素，转化为“n-1”（或“n 1”）的情形。
减元时，一般都采用“减首项”建立递归：先考虑第一步的各种情况，再将后若干步捆绑作为n-1的情形；
但若“n”的问题必须先完成“n-1”的问题时，则采用“减末项”递归：先将前面若干步捆绑作为n-1的情形，再考虑最后一步的各种情况）。
当递归关系难以发现时，研究初值是一个有效手段。
（2）容斥递归，为计算n情形下计算对象的个数an，先计算满足部分条件的“拟对象”个数In，然后从中减去不满足余下条件的“坏对象”个数Jn，我们有an=In-Jn。
在计算Jn时，如果可以转化为原问题在n-1情形下的计数，则得到
Jn=f（an-1），由此建立递归：an=In- f（an-1）。
先看减元递归。前两个例子很简单，主要是用来说明什么是“减首项”与“减末项”。
【代数3-1】对给定的正整数n，计算Σk=0[n/2]Cn2k3n-2k（冯跃峰编题）。
【题感】从条件看，“和式”的代表项Cn2k3n-2k具有明显的组合意义：它呈现“积”的形式，想到构造某种事件，可分两个步骤完成——第1个步骤有Cn2k种方法，第2个步骤有3n-2k种方法。
这只需分别Cn2k、3n-2k考察的意义，便可找到合适的组合模型。
【局部观察】对于Cn2k，可看成n个位置中取定2k个位置。
对于3n-2k，可分割为两部分来考察：
一部分是n-2k，它恰好是从“n个位置中取定2k个位置”后剩下的其他位置的个数。为了使前面选取的位置个数与后面“剩下的”位置数一致，可将前面的Cn2k改为Cnn-2k。
再结合底数“3”， 3n-2k恰好是选取的n-2k个位置中都有3种方法完成某件事。比如，将3个不同的数1、2、3任意排在这n-2k个位置上。
现在的问题是，前面留下的“2k个位置”做什么事情好呢？注意此时每个位置完成该事件都只有唯一的方法。于是，在这2k个位置都排同一个数，比如4即可。
由此不难构造相应的组合问题：计算由1，2，3，4组成的n位数，其中含有 2k个4。
但k是变化的：0≤k≤[n/2]，这意味着可以含有0，2，4，…，[n/2]个4，它恰好包含所有“偶数个”4的情形。
含“偶数个4”总觉得有点别扭，由于4与1的地位平行，将4换成1，问题更自然。
【组合模型】考虑如下的问题：用1，2，3，4可以组成多少个含有偶数个1的n位数?
为使“偶数个1”相对确定，需引入容量参数。
【容量参数】设有2k个1（0≤k≤[n/2]），则从n个位置中取2k个位置排1，有Cn2k种方法，剩下的n-2k个位置可排2、3、4，都有3种方法，所以含有2k个1的n位数的个数为Cn2k3n-2k。
注意到0≤k≤[n/2]，所以合乎条件的n位数的个数：
an=Σk=0[n/2]Cn2k3n-2k。
现在从另“递归”的角度计算an，设n位数为（x1x2…xn-1xn）。
前面是考虑“要素列”的每一个要素的变化构造模型。现在我们要在要素列中减去一个要素，建立递归。这采用“减首项”方式即可。
【减元递归】设n位数为（x1x2…xn-1xn），考察首位x1。
若首位排1，则后面的n-1位数中只有奇数个1。注意到偶数个1的n-1位数有an-1个，从而奇数个1的n-1位数有4n-1-an-1个；
若首位不排1，则有3种排法，后n-1位数有偶数个1，有an-1种排法，此时有3an-1种排法。所以，
an=（4n-1-an-1） 3an-1=4n-1 2an-1……（1）
由（1）可知，数列{ an-2an-1}是公比为4的等比数列，于是
an-2an-1=4（an-1-2an-2），
由此变形，又有
an-4an-1=2（an-1-4an-2）=（a2-4a1）2n-2=（10-4·3）2n-2=-2n-1……（2）
联立（1），（2），解得 an=2·4n-1 2n-1。
故Σk=0[n/2]Cn2k3n-2k=2·4n-1 2n-1。
注：解递归方程还有另外的方法（通法）。
【另解】由（1）两边同除以4n，得 an/4n=1/4 （1/2）（an-1/4n-1），
此即常见递归方程：xn=axn-1 b，可转化为等比数列求解。
【新写】考虑如下的问题：用1，2，3，4可以组成多少个含有偶数个1的n位数?
设有2k个1（0≤k≤[n/2]），则从n个位置中取2k个位置排1，有Cn2k种方法，剩下的n-2k个位置可排2、3、4，都有3种方法，所以含有2k个1的n位数的个数为Cn2k3n-2k。
注意到0≤k≤[n/2]，所以合乎条件的n位数的个数：an=Σk=0[n/2]Cn2k3n-2k。
另一方面，设n位数为（x1x2…xn-1xn）。
若x1=1，则后面的n-1位数中只有奇数个1。注意到偶数个1的n-1位数有an-1个，从而奇数个1的n-1位数有4n-1-an-1个；
若x1≠1，则x1有3种排法，后n-1位数有偶数个1，有an-1种排法，此时有3an-1种排法。所以，an=（4n-1-an-1） 3an-1=4n-1 2an-1……（1）
由（1）可知，数列{ an-2an-1}是公比为4的等比数列，于是
an-2an-1=4（an-1-2an-2）， 由此变形，又有
an-4an-1=2（an-1-4an-2）=
（a2-4a1）2n-2=（10-4·3）2n-2=-2n-1……（2）
联立（1），（2），解得 an=2·4n-1 2n-1。
故Σk=0[n/2]Cn2k3n-2k=2·4n-1 2n-1。
