1、斐波那契數(shù)列一、 簡介斐波那契數(shù)列（fibonacci），又稱黃金分割數(shù)列，由數(shù)學家斐波那契最早以“兔子繁殖問題”引入，推動了數(shù)學的發(fā)展。故斐波那契數(shù)列又稱“兔子數(shù)列”。斐波那契數(shù)列指這樣的數(shù)列：1,1,2,3,5,8,13,，前兩個數(shù)的和等于后面一個數(shù)字。這樣我們可以得到一個遞推式，記斐波那契數(shù)列的第i項為fi，則fi=fi-1+fi-2.兔子繁殖問題指設(shè)有一對新生的兔子，從第三個月開始他們每個月都生一對兔子，新生的兔子從第三個月開始又每個月生一對兔子。按此規(guī)律，并假定兔子沒有死亡，10個月后共有多少個兔子？這道題目通過找規(guī)律發(fā)現(xiàn)答案就是斐波那契數(shù)列，第n個月兔子的數(shù)量是斐波那契數(shù)列的第n項

2、。二、 性質(zhì)如果要了解斐波那契數(shù)列的性質(zhì)，必然要先知道它的通項公式才能更簡單的推導(dǎo)出一些定理。那么下面我們就通過初等代數(shù)的待定系數(shù)法計算出通項公式。令常數(shù)p,q滿足fn-pfn-1=q(fn-1-pfn-2)。則可得：fn-pfn-1=q(fn-1-pfn-2)=q2(fn-2-pfn-3)=qn-2(f2-pf1)又fn-pfn-1=q(fn-1-pfn-2)fn-pfn-1=qfn-1-pqfn-2fn-1+fn-2-pfn-1-qfn-1+pqfn-2=0(1-p-q)fn-1+(1+pq)fn-2=0p+q=1,pq=-1是其中的一種方程組fn-pfn-1= qn-2(f2-pf1)=

3、qn-2(1-p)=qn-1fn=qn-1+pfn-1=qn-1+p(qn-2+p(qn-3+)=qn-1+pqn-2+p2qn-3+pn-1不難看出，上式是一個以p/q為公比的等比數(shù)列。將它用求和公式求和可以得到：fn=qn-1pqn-1pq-1=pn-qnp-q而上面出現(xiàn)了方程組p+q=1,pq=-1，可以得到p(1-p)=-1,p2-p-1=0，這樣就得到了一個標準的一元二次方程，配方得p2-p+0.25=1.25,(p-0.5)2=1.25,p=1.25+0.5。隨意取出一組解即可：p=5+12,q=1-52fn=pn-qnp-q=151+52n-1-52n這就是著名的斐波那契數(shù)列通項

4、公式。有了它，斐波那契數(shù)列的一些性質(zhì)也不難得出了。比如斐波那契數(shù)列相鄰兩項的比值趨向于黃金分割比，即：limnfnfn-1=1+521.6180339887根據(jù)斐波那契數(shù)列通項公式，可以得到fnfn-1=1+52n-1-52n1+52n-1-1-52n-1因為n是趨向于正無限的，因此我們可以知道：01-52m1)證明：利用通項公式，設(shè)=1+52,=1-=1-52fm-1fn+fmfn+1=15m-1-m-1n-n+m-mn+1-n+1=15n+m+1+n+m+1+n+m-1+n+m-1-m-1n-anm-1-mn+1-n+1m=15n+m1+n+m1+-mn1+-anm1+注意到1/+=sqr

5、t(5)=1/+,1/+=0=1/+,上式就變成了15n+m+n+m=fn+m這就是上述公式的證明. 三、 斐波那契數(shù)列與自然斐波那契數(shù)列中的斐波那契數(shù)會經(jīng)常出現(xiàn)在我們的眼前比如松果、鳳梨、樹葉的排列、某些花朵的花瓣數(shù)（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀，超越數(shù)e（可以推出更多），黃金矩形、黃金分割、等角螺線，十二平均律等。斐波那契數(shù)還可以在植物的葉、枝、莖等排列中發(fā)現(xiàn)。例如，在樹木的枝干上選一片葉子，記其為數(shù)0，然后依序點數(shù)葉子（假定沒有折損），直到到達與那些葉子正對的位置，則其間的葉子數(shù)多半是斐波那契數(shù)。葉子從一個位置到達下一個正對的位置稱為一個循回。葉子在一個循回中旋轉(zhuǎn)的圈數(shù)也是斐波那

6、契數(shù)。在一個循回中葉子數(shù)與葉子旋轉(zhuǎn)圈數(shù)的比稱為葉序（源自希臘詞，意即葉子的排列）比。多數(shù)的葉序比呈現(xiàn)為斐波那契數(shù)的比。圖為斐波那契弧線。關(guān)于遞推式的拓展研究一、 錯位排列問題有n個數(shù)，求有多少種排列使這n個數(shù)都不在原來的位置上。比如n=2時，有一種排列。設(shè)f(n)表示n個數(shù)的錯位排列數(shù)量，分兩種情況討論：1. 第n個數(shù)在第p(pn)個數(shù)的位置上，第p個數(shù)在第n個數(shù)的位置上，則此時共有f(n-2)種選擇。由于p有(n-1)種值，則總共有(n-1)f(n-2)種排列方法；2. 否則，共有(n-1)f(n-1)種排列方法。綜上所述，f(n)=(n-1)(f(n-1)+f(n-2)，f(1)=0,f(

7、2)=1。那這個數(shù)列的通項公式是什么呢？直接對這個數(shù)列不好進行操作，可以轉(zhuǎn)化一下。設(shè)錯位排列的概率函數(shù)為g(n)，其中g(shù)(1)=0,g(2)=0.5。在f(n)的遞推式兩邊同時除以n!即可得到gn=1ngn-2+n-1ng(n-1)。兩邊同時乘n得到ng(n)=(n-1)g(n-1)+g(n-2)n(g(n)-g(n-1)=g(n-2)-g(n-1)gn-gn-1=-1nn!,即可得到gn=i=2n-1ii!=i=0n-1ii!注意到e-1的泰勒展開式跟它好像有點像，是e-1=i=0n-1ii!+rn(-1)因此有如下的等式：limn+gn=e-10.36788同時，我們也可以得到了函數(shù)f的通

8、項公式為：fn=n!gn=n!i=0n-1ii!這就是一些關(guān)于錯位排序的性質(zhì)。二、 類斐波那契數(shù)列的研究我們知道斐波那契數(shù)列遞推式為f(n)=f(n-1)+f(n-2)，那么假如有更多項呢？假設(shè)f(n)=f(n-1)+f(n-2)+f(n-3)，其中f(1)=f(2)=f(3)=1.我們暫時稱這個數(shù)列為類斐波那契數(shù)列，那么它的通項公式又如何呢？令a,b,c滿足f(n)+af(n-1)+bf(n-2)=c(f(n-1)+af(n-2)+bf(n-3)則得到c-a=1,ac-b=1,bc=1，消元得c3-c2-c-1=0，利用牛頓迭代可以計算出c=1.83928675521416，則a=0.839

9、28675521416,b=0.54368901269208所以f(n)+af(n-1)+bf(n-2)=cn-3(1+a+b)，記t=1+a+b，兩邊同時除以cn構(gòu)造更多的常數(shù)項：f(n)cn+acfn-1cn-1+bc2fn-2cn-2=tc3為了方便，我們記gn=f(n)cn，則：gn+acgn-1+bc2gn-2=tc3令p,q,r滿足g(n)-pg(n-1)-q=r(g(n-1)-pg(n-2)-q)，則得到：p+r=-ac,pr=bc2,1-rq=tc3這個方程會發(fā)現(xiàn)沒有實數(shù)解，于是我們只能使用復(fù)數(shù)了：p=-0.22815549365396-0.32963360796702iq=0

10、.29087615630927+0.07807037249863ir=-0.22815549365396+0.32963360796702i繼續(xù)上面的遞推式，則有g(shù)(n)-pg(n-1)-q=rn-2(g(2)-pg(1)-q)。記t= g(2)-pg(1)-q，則：g(n)=pg(n-1)+rn-2t+q=p(pg(n-2)+rn-3t+q)+rn-2t+q=pn-1g(1)+pn-2t+pn-3rt+rn-2t+q+pq+pn-2q=pn-1g1+pn-2trpn-1-1rp-1+qpn-1-1p-1=pn-1c+rn-1t-pn-1tr-p+qpn-1-qp-1因此也就可以得到f的遞推式

11、了：fn=cnpn-1c+rn-1t-pn-1tr-p+qpn-1-qp-1不難得到，t=2.38297576790624，t=0.12876722129781+0.10114779836709i。遞推式中的c,p,q,t,t都是常數(shù)，但除了c以外都是復(fù)數(shù)，因此計算上會比較困難。在附錄中附上c+的程序，附復(fù)數(shù)計算的模板和使用遞推式計算類斐波那契數(shù)列的程序。三、 遞推式和矩陣如果對于每個線性遞推式都要先計算它的通項公式才能夠快速地得到某一項，那這個方法太過于復(fù)雜了。于是我們可以使用矩陣來加速遞推。比如斐波那契數(shù)列的遞推式也可以寫成：f(n)f(n-1)=1110f(n-1)f(n-2)因此就有如

12、下結(jié)果：f(n)f(n-1)=1110n-2f(2)f(1)其中矩陣的冪次方可以使用快速冪算法在o(logn)的時間內(nèi)解決，因此我們就可以在o(logn)的時間內(nèi)計算出斐波那契數(shù)列的第n項（排除高精度的時間），且精度要比虛數(shù)和小數(shù)精確的多。附錄利用通項公式計算類斐波那契數(shù)列的代碼：#include #include #include #include #include #include #include #include #include #include using namespace std;const double eps = 1e-15;struct complexdouble a,

13、b;/num=a+bicomplex& operator=(const complex& c)a = c.a;b = c.b;return *this;complex()a = b = 0;complex(double t1, double t2 = 0)a = t1;b = t2;complex operator+(const complex& c) const return complex(a + c.a, b + c.b);complex operator-(const complex& c) const return complex(a - c.a, b - c.b);complex

14、operator*(const complex& c) const double ta = a * c.a - b * c.b;double tb = b * c.a + a * c.b;return complex(ta, tb);complex operator/(const complex& c) const complex t = c;t.b = -t.b;t = (*this) * t;double div = c.a * c.a + c.b * c.b;t.a /= div;t.b /= div;return t;bool operator=(const complex& c) c

15、onst return fabs(a - c.a) + fabs(b - c.b) = 1)if (e & 1) res = res * c;c = c * c;return res;int main()double c = 2, t = 0;while (fabs(c - t) eps)t = c;c -= (c * c * c - c * c - c - 1) / (3 * c * c - 2 * c - 1);double a = c - 1, b = 1 / c;printf(%.14lfn, 1 + a + b);t = 1 + a + b;complex r = (csqrt(complex(a * a / c / c - 4 * b / c / c) - a / c) / 2;r.print();complex p = complex(-a / c) - r, q = complex(t / c / c / c) / (complex(1) - r);p.print(), q.print();complex t = complex(1 / c / c) - comp