唐得嬌，鄧偉升

(1.通?？h第一中學(xué)，云南 玉溪 652700；2.云南師范大學(xué) 數(shù)學(xué)學(xué)院，云南 昆明 650500)

斐波那契數(shù)列是組合數(shù)學(xué)中一個(gè)重要和活躍的研究課題，它有許多奇特的性質(zhì)及應(yīng)用[1-4]；斐波那契數(shù)列性質(zhì)的證明方法有歸納法、公式法、母函數(shù)法及平鋪法等[5-7]，但在某些性質(zhì)的證明中，使用上述方法有的比較困難，有的則比較簡(jiǎn)單，本文利用臺(tái)階法證明了斐波那契數(shù)列的若干性質(zhì)，并賦予其一定的組合意義。

1 斐波那契數(shù)列及臺(tái)階法

在1202年出版的《算盤書》中,意大利數(shù)學(xué)家列昂納多·斐波那契提出了有趣的“兔子問題”[1]：在一年之初把一對(duì)兔子(雌雄各一只)放入圍墻內(nèi)，從第二個(gè)月起，雌兔每月可產(chǎn)一對(duì)兔子(雌雄各一只)，而雌小兔長(zhǎng)滿2個(gè)月后開始產(chǎn)兔，也是每月產(chǎn)一對(duì)兔子(雌雄各一只)，若不考慮死亡問題，到年末圍墻內(nèi)共有多少對(duì)兔子？

設(shè)第n(n=0,1,2,…)個(gè)月底，圍墻內(nèi)共有Fn對(duì)兔子，則F0=1,F1=1.當(dāng)n≥2時(shí)，第n個(gè)月底的Fn對(duì)兔子可分為兩類：1)第n-1個(gè)月的Fn-1對(duì)兔子；2)在第n個(gè)月出生的兔子，共有Fn-2對(duì)；則第n個(gè)月底，兔子的對(duì)數(shù)Fn=Fn-1+Fn-2.由特征根法或生成函數(shù)法可得

數(shù)列{Fn}n≥0稱為斐波那契數(shù)列，數(shù)列中的項(xiàng)Fn稱為斐波那契數(shù).

“兔子問題”可等價(jià)描述為“上樓梯問題”：設(shè)某人上有n級(jí)臺(tái)階的樓梯，每步只能上1級(jí)臺(tái)階或2級(jí)臺(tái)階，試求上法數(shù)gn.顯然g0=1,g1=1；當(dāng)n≥2時(shí)，上法可分為兩類：1)若第一步上1級(jí)臺(tái)階，則剩余的n-1級(jí)臺(tái)階的上法數(shù)為gn-1種；2)若第一步上2級(jí)臺(tái)階，則剩余的n-2級(jí)臺(tái)階的上法數(shù)為gn-2種；因此gn=gn-1+gn-2.由于數(shù)列{gn}n≥0與{Fn}n≥0有相同的初始值和遞推關(guān)系，從而gn=Fn；將上有n級(jí)臺(tái)階的樓梯，每步只能上1級(jí)臺(tái)階或2級(jí)臺(tái)階的上樓梯方法稱為臺(tái)階法.

2 斐波那契數(shù)列若干性質(zhì)的臺(tái)階法證明

性質(zhì)1F0+F2+F4+…+F2n=F2n+1(n≥0).

證明i)利用遞推法證明

由F0=F1及Fn=Fn-1+Fn-2，可得

F0+F2+F4+…+F2n=(F1+F2)+F4+…+F2n=

(F3+F4)+F6+…+F2n=…=F2n-1+F2n=F2n+1.

ii)利用臺(tái)階法證明

因?yàn)榕_(tái)階數(shù)2n+1為奇數(shù)，所以至少有一步只上1級(jí)臺(tái)階.將F2n+1種上法分為n+1類：第k(k=0,1,…,n)類為最后一次上1級(jí)臺(tái)階到達(dá)第2k+1級(jí)臺(tái)階，其上法為先從第0級(jí)臺(tái)階上到第2k級(jí)臺(tái)階，然后上1級(jí)臺(tái)階，其上法數(shù)為F2k種，剩下的2(n-k)級(jí)臺(tái)階，每步上2級(jí)臺(tái)階.由加法原理可得

F0+F2+F4+…+F2n=F2n+1.

性質(zhì)2F1+F3+F5+…+F2n-1=F2n-1(n≥1).

證明i)利用遞推法證明

由F0=1及Fn=Fn-1+Fn-2，可得

F1+F3+F5+…+F2n-1=(F2-F0)+(F4-F2)+

(F6-F4)+…+(F2n-F2n-2)=F2n-F0=F2n-1.

ii)利用臺(tái)階法證明

上2n級(jí)臺(tái)階的上法數(shù)共有F2n種，上法可分為兩類：1)每步均上2級(jí)臺(tái)階，其上法數(shù)只有1種；2)至少有一步上1級(jí)臺(tái)階，上法數(shù)為F2n-1，因?yàn)榕_(tái)階數(shù)2n為偶數(shù)，則最后一次上1級(jí)臺(tái)階到達(dá)的位置必在偶數(shù)級(jí)臺(tái)階上，可將這F2n-1種上法分為n類：第k(k=1,2,…,n)類為最后一次上1級(jí)臺(tái)階到達(dá)的位置為第2k級(jí)臺(tái)階，其上法為先從第0級(jí)臺(tái)階上到第2k-1級(jí)臺(tái)階，然后上1級(jí)臺(tái)階，其上法數(shù)為F2k-1種，剩下的2(n-k)級(jí)臺(tái)階，每步上了2級(jí)臺(tái)階.由加法原理可得

F1+F3+F5+…+F2n-1=F2n-1.

由上可見，利用遞推法和臺(tái)階法都可對(duì)斐波那契數(shù)列的某些性質(zhì)進(jìn)行證明，但是臺(tái)階法證明過程能夠賦予這些性質(zhì)一定的組合意義，易于理解；而且對(duì)于斐波那契數(shù)列的某些性質(zhì)，采用遞推法等方法證明比較困難，而采用臺(tái)階法進(jìn)行證明則很簡(jiǎn)潔.

性質(zhì)3Fn+m=FnFm+Fn-1Fm-1(n≥1,m≥1).

證明Fn+m種上法可分為兩類：1)有一步踏在第n級(jí)臺(tái)階上，其上法是先上前n級(jí)臺(tái)階，然后上后m級(jí)臺(tái)階，上法共有FnFm種；2)沒有踏在第n級(jí)臺(tái)階上，其上法是先上前n-1級(jí)臺(tái)階，然后上2級(jí)臺(tái)階越過第n級(jí)臺(tái)階到達(dá)第n+1級(jí)臺(tái)階，最后上剩下的m-1級(jí)臺(tái)階，上法共有Fn-1Fm-1種.從而

Fn+m=FnFm+Fn-1Fm-1(n≥1,m≥1).

3 結(jié)語

斐波那契數(shù)列是一個(gè)非常有趣的數(shù)列，它與樹木生長(zhǎng)、幾何圖形、黃金分割和楊輝三角等有著非常奇妙的聯(lián)系，在優(yōu)選法和計(jì)算機(jī)科學(xué)等領(lǐng)域有著非常廣泛應(yīng)用.斐波那契數(shù)列的性質(zhì)的證明方法多種多樣，本文主要采用臺(tái)階法來證明了若干斐波那契數(shù)列的性質(zhì)，這種證明方法簡(jiǎn)潔明了且易于理解，同時(shí)賦予其一定的組合意義.