侯作奎

遞推公式是數(shù)列的一種重要表示方法.許多計(jì)數(shù)問(wèn)題需要探求數(shù)列的遞推公式.那么如何探求數(shù)列遞推公式呢？本文試圖通過(guò)若干具體實(shí)例，給出探求數(shù)列遞推公式的若干途徑（方法）.

1 制定規(guī)則分類(lèi)，利用分類(lèi)計(jì)數(shù)原理

制定規(guī)則，并在這個(gè)規(guī)則下，將計(jì)數(shù)對(duì)象分類(lèi)，這樣比較容易導(dǎo)出遞推關(guān)系.

例1 （1993年全國(guó)高考題）將數(shù)字1，2，3，4填入標(biāo)號(hào)為1，2，3，4的四個(gè)格子里，每格填一個(gè)數(shù)字，則每個(gè)格子的標(biāo)號(hào)與所填的數(shù)字均不相同的填法有（ ?）.

A.9種 ?B.6種 ?C.11種 ?D.23種

解 將問(wèn)題推廣到一般：將1，2，3，…，n填入標(biāo)號(hào)為1，2，3，…，n的n個(gè)格子里，每格填一個(gè)數(shù)字，且每個(gè)格子的標(biāo)號(hào)與所填的數(shù)字均不相同，稱(chēng)這樣的一個(gè)填法叫作一個(gè)錯(cuò)排.求錯(cuò)排種數(shù).

假設(shè)n個(gè)自然數(shù)1，2，…n的錯(cuò)排種數(shù)為an.顯然a2=1.

當(dāng)n≥3時(shí)，由于是錯(cuò)排，故n必不在第n號(hào)格里，設(shè)n在第k號(hào)格里（k<n）.

以下對(duì)第n號(hào)格里的數(shù)字分類(lèi)討論：

（1）若第n號(hào)格里的數(shù)字是k，那么除n和k以外還要對(duì)余下的（n-2）個(gè)數(shù)進(jìn)行錯(cuò)排，則此時(shí)共有an-2種排法（如圖1）.

圖1

（2）若第n號(hào)格里不是k，

那么把第n號(hào)格視作第k號(hào)格.這樣就變成1，2，…，n-1個(gè)數(shù)的錯(cuò)排，此時(shí)有an-1種排法.

故當(dāng)n在第k號(hào)格里時(shí)，共有an-1+an-2種排法.

因?yàn)榉胖胣的k號(hào)格可在1，2，…，n-1中選取，有n-1種選法，故共有

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

原問(wèn)題解答：因a2=1，a3=2，由上面遞推關(guān)系得a4=（4-1）（2+1）=9.

評(píng) 這里制定規(guī)則：將n置于第k（k<n）號(hào)格中，討論第n號(hào)格放置的數(shù)是否為k.從而將此時(shí)的錯(cuò)排分為：第n號(hào)格里的數(shù)字是k與不是k的兩大類(lèi).從而較方便的溝通了an與an-1、an-2間的關(guān)系.

例2 （1996年愛(ài)朋思杯，上海市高中數(shù)學(xué)競(jìng)賽題）已知集合{1，2，3，4，5，6，7，8，9，10}，求該集合具有下列性質(zhì)的子集的個(gè)數(shù)：每個(gè)子集至少含有2個(gè)元素，且每個(gè)子集中任意兩個(gè)元素的差的絕對(duì)值大于1.

解 把問(wèn)題推廣到一般：已知集合{1，2，…，n}，求該集合具有下列性質(zhì)的子集的個(gè)數(shù)：每個(gè)子集至少含有2個(gè)元素，且每個(gè)子集中任意兩個(gè)元素的差的絕對(duì)值大于1.

設(shè)an是集合{1，2，…，n}的具有題設(shè)性質(zhì)的子集個(gè)數(shù)，顯然n≥3.

當(dāng)n=3，4時(shí)，計(jì)算得a3=1，a4=3.

當(dāng)n≥5時(shí)，將an個(gè)子集分為兩類(lèi)：

（1）含有元素n的子集：①集合{1，2，…，n-2}的每個(gè)符合題設(shè)性質(zhì)的子集（至少含有2個(gè)元素）再新增一元素n構(gòu)成的集合仍符合題設(shè)性質(zhì)，故這樣的子集有an-2個(gè);②集合{1，2，…，n-2}中每一個(gè)元素與n構(gòu)成的二元子集符合題設(shè)性質(zhì)，故有n-2個(gè).故含有元素n的子集個(gè)數(shù)為an-2+（n-2）;

（2）不含有元素n的子集，這樣的子集由集合{1，2，…，n-1}來(lái)確定，有an-1個(gè).

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

原問(wèn)題解答：因a3=1，a4=3，再逐次使用上述遞推關(guān)系有a10=a9+a8+8=

133.

評(píng) 這里制定規(guī)則：考慮子集中是否含有元素n.將n≥5時(shí)的an個(gè)子集分為含元素n與不含元素n的兩大類(lèi).在含元素n的子集類(lèi)中，又分為二元子集與至少含三個(gè)元素的子集.通過(guò)這樣的分類(lèi)，溝通了an與an-1、an-2間的關(guān)系.

例3 用1，2，3三個(gè)數(shù)來(lái)構(gòu)造n位數(shù)，但不允許有兩個(gè)緊挨著的1出現(xiàn)在n位數(shù)中（例如，當(dāng)n=5時(shí)，31213是允許的，11233，31112等是不允許的）.問(wèn)能構(gòu)造多少個(gè)這樣的n位數(shù)？

解 設(shè)能構(gòu)造an個(gè)符合要求的n位數(shù).顯然一位數(shù)的有1，2，3，即a1=3，兩位數(shù)的有12，21，13，31，23，32，22，33共8個(gè)，即a2=8.

當(dāng)n≥3時(shí)，分兩類(lèi)情形：（1）n位數(shù)的第1位數(shù)是2或3，則這樣的n位數(shù)有2an-1個(gè);

（2）n位數(shù)的第1位數(shù)是1，則第2位數(shù)只能是2或3，于是這樣的n位數(shù)有2an-2個(gè).由分類(lèi)計(jì)數(shù)原理有：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*）.

評(píng) 因2與3是可以緊挨著的，于是制定規(guī)則：考慮n位數(shù)的第一位數(shù)字是否為1.將n≥3時(shí)的符合要求的an個(gè)數(shù)分為兩類(lèi).一類(lèi)是首位數(shù)字不是1的，有2an-1個(gè);另一類(lèi)是首位數(shù)字是1的，有2an-2個(gè).通過(guò)這樣的分類(lèi)，使an與an-1、an-2之間的關(guān)系十分明朗.

例4 （加拿大第12屆數(shù)學(xué)奧林匹克題）擲一枚硬幣，每次正面出現(xiàn)得1分，反面出現(xiàn)得2分，試證：恰好得n分的概率是13[2+（-12）n].

證明 設(shè)事件“恰好得n分”的概率為Pn.事件“恰好得n分”可分為以下兩種情形：①先得了n-2分（其概率為Pn-2），再擲得一次反面;②先得了n-1分（其概率為Pn-1），再擲得一次正面.由分類(lèi)計(jì)數(shù)原理得“恰好得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].

評(píng) 這里制定規(guī)則：考慮事件“恰好得n分”之前一次的不同得分情況.由此將事件“恰好得n分”之前一次的得分情況，分為得（n-2）分和得n-1分兩類(lèi)事件，溝通了Pn與Pn-1、Pn-2間的關(guān)系，順利建立起了遞推關(guān)系式：Pn=12Pn-1+12Pn-2.

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

圖2

例5 （2013年安徽）如圖2，互不相同的點(diǎn)A1，A2，…，An，…，和B1，B2，…，Bn，…分別在角O的兩邊上，所有AnBn相互平行，且所有梯形AnBnBn+1An+1的面積均相等.設(shè)OAn=an.若a1=1，a2=2，則數(shù)列{an}的通項(xiàng)公式是 ? ?.

解 設(shè)△OAnBn的面積為Sn.因所有AnBn相互平行，a1=1，a2=2，所以O(shè)A1=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*）.

評(píng) 這里著眼于對(duì)從Sn到Sn+1的分析，得到新增面積為3S1，從而一舉得到遞推關(guān)系式（*）.

例6 （1997年浙江五校高三聯(lián)考題）記函數(shù)fn（x）=（1+2x）·（1+22x）·…·（1+2nx）展開(kāi)式中，x2項(xiàng)的系數(shù)為an.試問(wèn)是否存在常數(shù)a，b使對(duì)于不小于2的任何正整數(shù)n，都有an=83（2n-1-1）（a·2n+b）？

分析 本例常用方法是：先考慮特殊，然后一般性證明.即假設(shè)存在a，b，然后取n=2，3，得到特殊情形下的a，b之值，最后用數(shù)學(xué)歸納法證明所得a，b之值對(duì)n≥2（n∈N*）成立.這里我們通過(guò)建立遞推關(guān)系來(lái)解決.

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

由此知fn（x）·2n+1x中x2項(xiàng)的系數(shù)是新增的，易知新增x2項(xiàng)的系數(shù)為

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）.

對(duì)比an的表達(dá)式，知存在a=1，b=-1，使n≥2（n∈N*）時(shí)，結(jié)論成立.

評(píng) 這里著眼于對(duì)fn（x）到fn+1（x）中的x2項(xiàng)系數(shù)新增情況的分析，順利得到了遞推式（*）.

3 間接求出

有些計(jì)數(shù)對(duì)象在某些限制條件下，不易直接計(jì)算出結(jié)果.這時(shí)不妨先求出總數(shù)，以及其

中不合要求的情況數(shù)，然后從總數(shù)中扣除不合要求的情況數(shù)即得所求.這種解決問(wèn)題的思想方法也適用某些遞推式的探求.

例7 （2001年全國(guó)高中數(shù)學(xué)聯(lián)賽第12題）在一個(gè)正六邊形的六個(gè)區(qū)域栽種觀賞植物（如圖3），要求同一塊中種同一種植物，相鄰的兩塊種不同的植物.現(xiàn)有4種不同的植物可供選擇，則有幾種栽種方案？

圖3

解 將問(wèn)題推廣到一般：使用l（l≥3）種顏色的全部或其中幾種顏色將一個(gè)1×n格棋盤(pán)染色，要求每一格染一種顏色，且相鄰兩格及兩端的兩格都不同色，問(wèn)有多少種不同的染色方法？

假設(shè)1×n格棋盤(pán)有an種染法.顯然1×1格棋盤(pán)有l(wèi)種染法，即a1=l，同理a2=l（l-1）.

當(dāng)n≥3時(shí)，暫不考慮棋盤(pán)兩端的染色相同與否，則第1格有l(wèi)種染法，第2格至第n格均有（l-1）種染法，則共有l(wèi)（l-1）n-1種染法.

由于在對(duì)第n格染色時(shí)，只考慮了與第（n-1）格染色不同，因此在對(duì)第n格染色的（l-1）種方法中，與第一格有同色或不同色兩種情況.

若第n格與第1格同色，將第1格與第n格“拼成一格”，則這時(shí)就是對(duì)1×（n-1）格棋盤(pán)的染色，有an-1種方法.

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

據(jù)此可求得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年全國(guó)高中數(shù)學(xué)聯(lián)賽第12題的答案：

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

4 利用曲線方程的定義

用數(shù)列{an}的第n項(xiàng)an或含有an的式子來(lái)表示曲線上相關(guān)點(diǎn)An的坐標(biāo)，依點(diǎn)An在曲線上，利用曲線方程的定義，即可得數(shù)列遞推關(guān)系式.

例8 （2010年浙江大學(xué)自主招生試題）如圖4所示，y=x的圖象下有一系列正三角形，求第n個(gè)正三角形的邊長(zhǎng).

圖4

解 如圖所示，設(shè)第n個(gè)正三角形為△Bn-1AnBn（其中B0點(diǎn)是原點(diǎn)）.它的邊長(zhǎng)為bn，則點(diǎn)Bn的坐標(biāo)為Bn（Sn，0）（其中Sn=b1+b2+…+bn）.于是

An（Sn-12bn，32bn）.由于點(diǎn)An在函數(shù)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àn)橹本€y=3x與函數(shù)y=x的交點(diǎn)為B0（0，0）與A1（13，33），所以b1=B0B1=23.

于是數(shù)列{bn}構(gòu)成以b1=23為首項(xiàng)，23為公差的等差數(shù)列，所以bn=23+（n-1）23=2n3，亦即第n個(gè)正三角形的邊長(zhǎng)為2n3.

評(píng) 這里利用等邊三角形的性質(zhì)，用數(shù)列{bn}的第n項(xiàng)bn或含有bn的式子來(lái)表示第n個(gè)三角形頂點(diǎn)An的坐標(biāo)，依點(diǎn)An在曲線上，利用曲線方程的定義，得到bn與Sn的關(guān)系式①，進(jìn)而得到遞推關(guān)系式③.類(lèi)似可作：

圖5

如圖5，A1，A2，…在x軸的正半軸上，B1，B2，…在曲線y=x上.若△OA1B1，△A1A2B2，△A2A3B3，…，均為等腰Rt△，且B1，B2，…為直角頂點(diǎn).求前100個(gè)等腰直角三角形的面積和.

縱觀本文所給出的幾個(gè)基本而重要的探求遞推關(guān)系的途徑（方法），不難看出：無(wú)論是“分類(lèi)”、還是“拼格”，其實(shí)質(zhì)都是降維的手段，以便溝通相鄰項(xiàng)的關(guān)系，從而建立起遞推關(guān)系;而探求an-1到an的新增情況，則是尋求遞推關(guān)系廣為采用的切入點(diǎn);用數(shù)列{an}的第n項(xiàng)an或含有an的式子來(lái)表示曲線上相關(guān)點(diǎn)An的坐標(biāo)，再利用曲線方程的定義得到數(shù)列遞推關(guān)系式，是探求解析幾何中數(shù)列遞推關(guān)系式的典型方法.