探求数列递推公式的若干途径

侯作奎

递推公式是数列的一种重要表示方法.许多计数问题需要探求数列的递推公式.那么如何探求数列递推公式呢？本文试图通过若干具体实例，给出探求数列递推公式的若干途径（方法）.

1 制定规则分类，利用分类计数原理

制定规则，并在这个规则下，将计数对象分类，这样比较容易导出递推关系.

例1 （1993年全国高考题）将数字1，2，3，4填入标号为1，2，3，4的四个格子里，每格填一个数字，则每个格子的标号与所填的数字均不相同的填法有（  ）.

A.9种  B.6种  C.11种  D.23种

解 将问题推广到一般：将1，2，3，…，n填入标号为1，2，3，…，n的n个格子里，每格填一个数字，且每个格子的标号与所填的数字均不相同，称这样的一个填法叫作一个错排.求错排种数.

假设n个自然数1，2，…n的错排种数为an.显然a2=1.

当n≥3时，由于是错排，故n必不在第n号格里，设n在第k号格里（k<n）.

以下对第n号格里的数字分类讨论：

（1）若第n号格里的数字是k，那么除n和k以外还要对余下的（n-2）个数进行错排，则此时共有an-2种排法（如图1）.

图1

（2）若第n号格里不是k，

那么把第n号格视作第k号格.这样就变成1，2，…，n-1个数的错排，此时有an-1种排法.

故当n在第k号格里时，共有an-1+an-2种排法.

因为放置n的k号格可在1，2，…，n-1中选取，有n-1种选法，故共有

an=（n-1）·（an-1+an-2）（n≥3）种不同排法.

原问题解答：因a2=1，a3=2，由上面递推关系得a4=（4-1）（2+1）=9.

评 这里制定规则：将n置于第k（k<n）号格中，讨论第n号格放置的数是否为k.从而将此时的错排分为：第n号格里的数字是k与不是k的两大类.从而较方便的沟通了an与an-1、an-2间的关系.

例2 （1996年爱朋思杯，上海市高中数学竞赛题）已知集合{1，2，3，4，5，6，7，8，9，10}，求该集合具有下列性质的子集的个数：每个子集至少含有2个元素，且每个子集中任意两个元素的差的绝对值大于1.

解 把问题推广到一般：已知集合{1，2，…，n}，求该集合具有下列性质的子集的个数：每个子集至少含有2个元素，且每个子集中任意两个元素的差的绝对值大于1.

设an是集合{1，2，…，n}的具有题设性质的子集个数，显然n≥3.

当n=3，4时，计算得a3=1，a4=3.

当n≥5时，将an个子集分为两类：

（1）含有元素n的子集：①集合{1，2，…，n-2}的每个符合题设性质的子集（至少含有2个元素）再新增一元素n构成的集合仍符合题设性质，故这样的子集有an-2个;②集合{1，2，…，n-2}中每一个元素与n构成的二元子集符合题设性质，故有n-2个.故含有元素n的子集个数为an-2+（n-2）;

（2）不含有元素n的子集，这样的子集由集合{1，2，…，n-1}来确定，有an-1个.

所以an=an-1+an-2+（n-2）（n≥5）.

原问题解答：因a3=1，a4=3，再逐次使用上述递推关系有a10=a9+a8+8=

133.

评 这里制定规则：考虑子集中是否含有元素n.将n≥5时的an个子集分为含元素n与不含元素n的两大类.在含元素n的子集类中，又分为二元子集与至少含三个元素的子集.通过这样的分类，沟通了an与an-1、an-2间的关系.

例3 用1，2，3三个数来构造n位数，但不允许有两个紧挨着的1出现在n位数中（例如，当n=5时，31213是允许的，11233，31112等是不允许的）.问能构造多少个这样的n位数？

解 设能构造an个符合要求的n位数.显然一位数的有1，2，3，即a1=3，两位数的有12，21，13，31，23，32，22，33共8个，即a2=8.

当n≥3时，分两类情形：（1）n位数的第1位数是2或3，则这样的n位数有2an-1个;

（2）n位数的第1位数是1，则第2位数只能是2或3，于是这样的n位数有2an-2个.由分类计数原理有：an=2an-1+2an-2（n≥3，n∈N*）.

于是 an+1=2an+2an-1（n≥2，n∈N*）……（*）

由此可求得an=123[（5+33）（1+3）n-1-（5-33）（1-3）n-1]（n≥2）.

a1=3也适合（*）式.

所以an=123[（5+33）（1+3）n-1-（5-33）（1-3）n-1]（n∈N*）.

评 因2与3是可以紧挨着的，于是制定规则：考虑n位数的第一位数字是否为1.将n≥3时的符合要求的an个数分为两类.一类是首位数字不是1的，有2an-1个;另一类是首位数字是1的，有2an-2个.通过这样的分类，使an与an-1、an-2之间的关系十分明朗.

例4 （加拿大第12届数学奥林匹克题）掷一枚硬币，每次正面出现得1分，反面出现得2分，试证：恰好得n分的概率是13[2+（-12）n].

证明 设事件“恰好得n分”的概率为Pn.事件“恰好得n分”可分为以下两种情形：①先得了n-2分（其概率为Pn-2），再掷得一次反面;②先得了n-1分（其概率为Pn-1），再掷得一次正面.由分类计数原理得“恰好得n分”的概率为Pn=12Pn-1+12Pn-2，即

2Pn+Pn-1=2Pn-1+Pn-2=…=2P2+P1=2×（12+12×12）+12=2.

从而Pn-23=-16·（-12）n-1Pn=13[2+（-12）n].

评 这里制定规则：考虑事件“恰好得n分”之前一次的不同得分情况.由此将事件“恰好得n分”之前一次的得分情况，分为得（n-2）分和得n-1分两类事件，沟通了Pn与Pn-1、Pn-2间的关系，顺利建立起了递推关系式：Pn=12Pn-1+12Pn-2.

2 探求an-1到an的新增情况

图2

例5 （2013年安徽）如图2，互不相同的点A1，A2，…，An，…，和B1，B2，…，Bn，…分别在角O的两边上，所有AnBn相互平行，且所有梯形AnBnBn+1An+1的面积均相等.设OAn=an.若a1=1，a2=2，则数列{an}的通项公式是    .

解 设△OAnBn的面积为Sn.因所有AnBn相互平行，a1=1，a2=2，所以OA1=A1A2，OB1=B1B2，从而S2S1=（a2a1）2=4S2=4S1.

所以梯形A1B1B2A2的面积=S2-S1=3S1.又所有梯形AnBnBn+1An+1的面积均相等，所以Sn+1=Sn+梯形AnBnBn+1An+1的面积=Sn+梯形A1B1B2A2的面积=Sn+3S1，即Sn+1=Sn+3S1……（*）.

所以Sn=S1+（n-1）3S1=（3n-2）S1SnS1=3n-2.

即（ana1）2=3n-2an=3n-2（n∈N*）.

评 这里着眼于对从Sn到Sn+1的分析，得到新增面积为3S1，从而一举得到递推关系式（*）.

例6 （1997年浙江五校高三联考题）记函数fn（x）=（1+2x）·（1+22x）·…·（1+2nx）展开式中，x2项的系数为an.试问是否存在常数a，b使对于不小于2的任何正整数n，都有an=83（2n-1-1）（a·2n+b）？

分析 本例常用方法是：先考虑特殊，然后一般性证明.即假设存在a，b，然后取n=2，3，得到特殊情形下的a，b之值，最后用数学归纳法证明所得a，b之值对n≥2（n∈N*）成立.这里我们通过建立递推关系来解决.

解 因fn+1（x）=fn（x）（1+2n+1x）=fn（x）+fn（x）·2n+1x.

由此知fn（x）·2n+1x中x2项的系数是新增的，易知新增x2项的系数为

2n+1（2+22+…+2n）=22n+2-2n+2.所以an+1=an+（22n+2-2n+2）……（*），

即an+1-an=22n+2-2n+2.

所以an+1-a2=∑nk=2（ak+1-ak）=∑nk=2（22k+2-2k+2）.

又a2=8，所以an+1=83（22n+1-8）+24-2n+3.

所以an=83（22n-1-8）+24-2n+2=83（2n-1-1）（2n-1）.

对比an的表达式，知存在a=1，b=-1，使n≥2（n∈N*）时，结论成立.

评 这里着眼于对fn（x）到fn+1（x）中的x2项系数新增情况的分析，顺利得到了递推式（*）.

3 间接求出

有些计数对象在某些限制条件下，不易直接计算出结果.这时不妨先求出总数，以及其

中不合要求的情况数，然后从总数中扣除不合要求的情况数即得所求.这种解决问题的思想方法也适用某些递推式的探求.

例7 （2001年全国高中数学联赛第12题）在一个正六边形的六个区域栽种观赏植物（如图3），要求同一块中种同一种植物，相邻的两块种不同的植物.现有4种不同的植物可供选择，则有几种栽种方案？

图3

解 将问题推广到一般：使用l（l≥3）种颜色的全部或其中几种颜色将一个1×n格棋盘染色，要求每一格染一种颜色，且相邻两格及两端的两格都不同色，问有多少种不同的染色方法？

假设1×n格棋盘有an种染法.显然1×1格棋盘有l种染法，即a1=l，同理a2=l（l-1）.

当n≥3时，暂不考虑棋盘两端的染色相同与否，则第1格有l种染法，第2格至第n格均有（l-1）种染法，则共有l（l-1）n-1种染法.

由于在对第n格染色时，只考虑了与第（n-1）格染色不同，因此在对第n格染色的（l-1）种方法中，与第一格有同色或不同色两种情况.

若第n格与第1格同色，将第1格与第n格“拼成一格”，则这时就是对1×（n-1）格棋盘的染色，有an-1种方法.

所以an=l（l-1）n-1-an-1（n≥3）.

据此可求得an=（l-1）n+（l-1）（-1）n（n≥3），显然n=2也适合.

所以an=l，（n=1）

（l-1）n+（l-1）（-1）n，（n≥2）

如果取n=6，l=4，即得2001年全国高中数学联赛第12题的答案：

a6=36+3·（-1）6=732.

4 利用曲线方程的定义

用数列{an}的第n项an或含有an的式子来表示曲线上相关点An的坐标，依点An在曲线上，利用曲线方程的定义，即可得数列递推关系式.

例8 （2010年浙江大学自主招生试题）如图4所示，y=x的图象下有一系列正三角形，求第n个正三角形的边长.

图4

解 如图所示，设第n个正三角形为△Bn-1AnBn（其中B0点是原点）.它的边长为bn，则点Bn的坐标为Bn（Sn，0）（其中Sn=b1+b2+…+bn）.于是

An（Sn-12bn，32bn）.由于点An在函数y=x的图象上，于是有：32bn=Sn-12bn，所以34b2n=Sn-12bn…①.于是有34b2n+1=Sn+1-12bn+1…②.

由②-①得：34（b2n+1-b2n）=12（bn+1+bn），所以bn+1-bn=23……③.

又因为直线y=3x与函数y=x的交点为B0（0，0）与A1（13，33），所以b1=B0B1=23.

于是数列{bn}构成以b1=23为首项，23为公差的等差数列，所以bn=23+（n-1）23=2n3，亦即第n个正三角形的边长为2n3.

评 这里利用等边三角形的性质，用数列{bn}的第n项bn或含有bn的式子来表示第n个三角形顶点An的坐标，依点An在曲线上，利用曲线方程的定义，得到bn与Sn的关系式①，进而得到递推关系式③.类似可作：

图5

如图5，A1，A2，…在x轴的正半轴上，B1，B2，…在曲线y=x上.若△OA1B1，△A1A2B2，△A2A3B3，…，均为等腰Rt△，且B1，B2，…为直角顶点.求前100个等腰直角三角形的面积和.

纵观本文所给出的几个基本而重要的探求递推关系的途径（方法），不难看出：无论是“分类”、还是“拼格”，其实质都是降维的手段，以便沟通相邻项的关系，从而建立起递推关系;而探求an-1到an的新增情况，则是寻求递推关系广为采用的切入点;用数列{an}的第n项an或含有an的式子来表示曲线上相关点An的坐标，再利用曲线方程的定义得到数列递推关系式，是探求解析几何中数列递推关系式的典型方法.