探求數(shù)列遞推公式的若干途徑

侯作奎

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

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

制定規(guī)則，并在這個規(guī)則下，將計數(shù)對象分類，這樣比較容易導出遞推關(guān)系.

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

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

解 將問題推廣到一般：將1，2，3，…，n填入標號為1，2，3，…，n的n個格子里，每格填一個數(shù)字，且每個格子的標號與所填的數(shù)字均不相同，稱這樣的一個填法叫作一個錯排.求錯排種數(shù).

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

當n≥3時，由于是錯排，故n必不在第n號格里，設(shè)n在第k號格里（k<n）.

以下對第n號格里的數(shù)字分類討論：

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

圖1

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

那么把第n號格視作第k號格.這樣就變成1，2，…，n-1個數(shù)的錯排，此時有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，由上面遞推關(guān)系得a4=（4-1）（2+1）=9.

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

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

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

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

當n=3，4時，計算得a3=1，a4=3.

當n≥5時，將an個子集分為兩類：

（1）含有元素n的子集：①集合{1，2，…，n-2}的每個符合題設(shè)性質(zhì)的子集（至少含有2個元素）再新增一元素n構(gòu)成的集合仍符合題設(shè)性質(zhì)，故這樣的子集有an-2個;②集合{1，2，…，n-2}中每一個元素與n構(gòu)成的二元子集符合題設(shè)性質(zhì)，故有n-2個.故含有元素n的子集個數(shù)為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，再逐次使用上述遞推關(guān)系有a10=a9+a8+8=

133.

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

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

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

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

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

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

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

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

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

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

圖2

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

解 設(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*）.

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

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

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

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

由此知fn（x）·2n+1x中x2項的系數(shù)是新增的，易知新增x2項的系數(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）.

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

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

3 間接求出

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

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

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

圖3

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

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

當n≥3時，暫不考慮棋盤兩端的染色相同與否，則第1格有l(wèi)種染法，第2格至第n格均有（l-1）種染法，則共有l(wèi)（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）.

據(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年全國高中數(shù)學聯(lián)賽第12題的答案：

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

4 利用曲線方程的定義

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

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

圖4

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

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

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

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

圖5

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

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