遞歸數列在實際問題中的應用

張遠東

【摘要】遞歸數列是高考數列命題的熱點.它的方法活，類型多，解題方法也不盡相同.本文綜合前人的研究歸納總結出幾種常見類型的遞歸數列，并應用到實際問題中.例如傳球問題、爬樓梯問題、染色等遞歸數列的實際問題在中小學試題中頻頻出現，對它們的研究也顯得更有意義.本文對這些問題進行了簡單研究.

【關鍵詞】遞歸；數列；應用

1.增長率的問題

例1 某工廠年初有固定資金1000萬元，假設經過投入生產，每年資金增長率為50%，但每年要扣除消費基金x萬元，余下的資金投入再生產，若經過5年后扣除消費基金還至少有2000萬元，求x能取到的最大值（精確到1萬元）.

解 設用an表示經n年后扣消費基金余下的資金，那么有

故x能取到的最大值為424萬元.

注 本題充分利用前后兩年的余款來建立遞歸關系an=an-1（1+50%）-x，避免了逐項類推找規律的煩瑣過程.

2.爬樓梯問題

例2 假設一個人向上爬樓梯時，每一步可以上1級或2級，問這個人爬n級樓梯一共有多少種不同的爬法？

解 設爬n級樓梯一共有an種爬法.

當n=1時，a1=1.

當n=2時，①每一步一級；②每一步兩級，有2種走法.

當n=3時，①每一步一級；②先一級后兩級；③先兩級后一級，一共有3種走法.

當n=4時，①他第一步走一級還剩3級，轉化為n=3的情況，有3種走法；

②他第一步走兩級還剩2級，轉化為n=2的情況，有2種走法，所以一共有5種走法.

當n=5時，①他第一步走一級還剩4級，轉化為n=4的情況，有5種走法；

②他第一步走兩級還剩3級，轉化為n=3的情況，有3種走法，

所以一共有8種走法.

……

當為n級時也有兩種情況：

①他第一步走一級還剩n-1級，有an-1種走法；

②他第一步走兩級還剩n-2級，有an-2種走法.

所以一共有an-1+an-2種走法.

即an=an-1+an-2.

推廣 假定一個人爬樓梯時，每一步能上1級、2級或3級，那么這個人爬n級樓梯一共會有多少種不同的爬法呢？

由上面的解題思路很容易解答.這也是一個遞歸數列的問題，其遞歸式為

an=an-1+an-2+an-3，其中a1=1，a2=2，a3=4.

3.放球問題

例3 有編號1，2，3，4，…，n的n個不同的球，分別裝入編號為1，2，3，4，…，n的n個筐里（一筐一個），序號不能相同，共有多少種方法？

解 設n個球裝n個筐中（序號不同）有an種裝法，則a1=0，a2=1，a3=2，an包含兩類：

①1號球裝入k號筐，k號球裝入1號筐（k=2，3，…，n），還剩（n-2）個球（n-2）個筐（序號不同），共有an-2種裝法，又k有（n-1）種選擇，所以這類情況有C1n-1an-2種放法；

②1號球裝入k號筐，但k號球不裝入1號筐（k=2，3，…，n），此時可以把k號球當作1號球，即還剩（n-1）個球（n-1）個筐（序號不同），共有an-1種裝法，又k有（n-1）種選擇，所以這類情況有C1n-1an-1種放法.

所以an=C1n-1an-2+C1n-1an-1=（n-1）（an-2+an-1），（n≥3）.

4.傳球問題

例4 有m個人在做相互傳球訓練，第一次讓甲先傳球給其余m-1人中的任一人，第二次再由拿球者再傳給其余m-1人中的任一人，這樣共相互傳了n次球，則在第n次傳球后仍傳回到甲手中的傳法種數共有多少種？

解 設經過傳球n次，第n次傳到甲的傳球方法數有an種，設傳球n次，第n次不傳給甲的傳球方法數有bn種，an+bn表示這n次傳球可以傳給m-1人中的任一人.易得a1=0，an+bn=（m-1）n，而an+1=bn（第n+1次傳到甲只需第n次不傳到甲）.所以an+an+1=（m-1）n.

，

即an+1[]（-1）n+1-an[]（-1）n=-（1-m）n，利用累差疊加的方法可得

傳球問題、爬樓梯問題等經常困擾著學生，本文針對這幾類問題進行了探究，并與遞歸數列的相關類型建立聯系，揭示它們的本質，使得這幾類問題的解題變得清晰明了.