亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

源起

根據(jù)高德納（Donald Ervin Knuth）的《計算機(jī)程序設(shè)計藝術(shù)》（ The Art of Computer Programming ），1150年印度數(shù)學(xué)家Gopala和金月在研究箱子包裝物件長寬剛好為1和2的可行方法數(shù)目時，首先描述這個數(shù)列。在西方，最先研究這個數(shù)列的人是比薩的列奧那多（意大利人斐波那契Leonardo Fibonacci），他描述兔子生長的數(shù)目時用上了這數(shù)列:

第一個月初有一對剛誕生的兔子

第二個月之后（第三個月初）它們可以生育

每月每對可生育的兔子會誕生下一對新兔子

兔子永不死去

假設(shè)在n月有兔子總共a對，n+1月總共有b對。在n+2月必定總共有a+b對：因為在n+2月的時候，前一月（n+1月）的b對兔子可以存留至第n+2月（在當(dāng)月屬于新誕生的兔子尚不能生育）。而新生育出的兔子對數(shù)等于所有在n月就已存在的a對

表達(dá)式

為求得斐波那契數(shù)列的一般表達(dá)式，可以借助線性代數(shù)的方法。高中的初等數(shù)學(xué)知識也能求出。

初等代數(shù)解法

已知

a 1 = 1 {\displaystyle a_{1}=1}

a 2 = 1 {\displaystyle a_{2}=1}

a n = a n ? ? --> 1 + a n ? ? --> 2 {\displaystyle a_{n}=a_{n-1}+a_{n-2}}

首先構(gòu)建等比數(shù)列

設(shè) a n + α α --> a n ? ? --> 1 = β β --> ( a n ? ? --> 1 + α α --> a n ? ? --> 2 ) {\displaystyle a_{n}+\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})} 化簡得a n = ( β β --> ? ? --> α α --> ) a n ? ? --> 1 + α α --> β β --> a n ? ? --> 2 {\displaystyle a_{n}=(\beta -\alpha )a_{n-1}+\alpha \beta a_{n-2}} 比較系數(shù)可得：{ β β --> ? ? --> α α --> = 1 α α --> β β --> = 1 {\displaystyle {\begin{cases}\beta -\alpha =1\\\alpha \beta =1\end{cases}}} 不妨設(shè) β β --> > 0 , α α --> > 0 {\displaystyle \beta >0,\alpha >0} 解得：

{ α α --> = 5 ? ? --> 1 2 β β --> = 5 + 1 2 {\displaystyle {\begin{cases}\alpha ={\dfrac {{\sqrt {5}}-1}{2}}\\\beta ={\dfrac {{\sqrt {5}}+1}{2}}\end{cases}}} 又因為有 a n + α α --> a n ? ? --> 1 = β β --> ( a n ? ? --> 1 + α α --> a n ? ? --> 2 ) {\displaystyle a_{n}+\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})} ， 即 { a n + α α --> a n ? ? --> 1 } {\displaystyle \left\{a_{n}+\alpha a_{n-1}\right\}} 為等比數(shù)列。

求出數(shù)列{ a n + α α --> a n ? ? --> 1 {\displaystyle a_{n}+\alpha a_{n-1}} }

由以上可得：a n + 1 + α α --> a n = ( a 2 + α α --> a 1 ) β β --> n ? ? --> 1 = ( 1 + α α --> ) β β --> n ? ? --> 1 = β β --> n {\displaystyle {\begin{aligned}a_{n+1}+\alpha a_{n}&=(a_{2}+\alpha a_{1})\beta ^{n-1}\\&=(1+\alpha )\beta ^{n-1}\\&=\beta ^{n}\\\end{aligned}}}

變形得： a n + 1 β β --> n + 1 + α α --> β β --> a n β β --> n = 1 β β --> {\displaystyle {\frac {a_{n+1}}{\beta ^{n+1}}}+{\frac {\alpha }{\beta }}{\frac {a_{n}}{\beta ^{n}}}={\frac {1}{\beta }}} 。 令 b n = a n β β --> n {\displaystyle b_{n}={\frac {a_{n}}{\beta ^{n}}}}

求數(shù)列{ b n {\displaystyle b_{n}} }進(jìn)而得到{ a n {\displaystyle a_{n}} }

b n + 1 + α α --> β β --> b n = 1 β β --> {\displaystyle b_{n+1}+{\frac {\alpha }{\beta }}b_{n}={\frac {1}{\beta }}} 設(shè) b n + 1 + λ λ --> = ? ? --> α α --> β β --> ( b n + λ λ --> ) {\displaystyle b_{n+1}+\lambda =-{\frac {\alpha }{\beta }}(b_{n}+\lambda )} ，解得 λ λ --> = ? ? --> 1 α α --> + β β --> {\displaystyle \lambda =-{\frac {1}{\alpha +\beta }}} 。 故數(shù)列 { b n + λ λ --> } {\displaystyle \left\{b_{n}+\lambda \right\}} 為等比數(shù)列 即 b n + λ λ --> = ( ? ? --> α α --> β β --> ) n ? ? --> 1 ( b 1 + λ λ --> ) {\displaystyle b_{n}+\lambda =\left(-{\frac {\alpha }{\beta }}\right)^{n-1}\left(b_{1}+\lambda \right)} 。而 b 1 = a 1 β β --> = 1 β β --> {\displaystyle b_{1}={\frac {a_{1}}{\beta }}={\frac {1}{\beta }}} ， 故有 b n + λ λ --> = ( ? ? --> α α --> β β --> ) n ? ? --> 1 ( 1 β β --> + λ λ --> ) {\displaystyle b_{n}+\lambda =\left(-{\frac {\alpha }{\beta }}\right)^{n-1}\left({\frac {1}{\beta }}+\lambda \right)} 又有 { α α --> = 5 ? ? --> 1 2 β β --> = 5 + 1 2 {\displaystyle {\begin{cases}\alpha ={\dfrac {{\sqrt {5}}-1}{2}}\\\beta ={\dfrac {{\sqrt {5}}+1}{2}}\end{cases}}} 和 b n = a n β β --> n {\displaystyle b_{n}={\frac {a_{n}}{\beta ^{n}}}} 可得 a n = 5 5 ? ? --> [ ( 1 + 5 2 ) n ? ? --> ( 1 ? ? --> 5 2 ) n ] {\displaystyle a_{n}={\frac {\sqrt {5}}{5}}\cdot \left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]}

得出 a n {\displaystyle {a_{n}}} 表達(dá)式

a n = 5 5 ? ? --> [ ( 1 + 5 2 ) n ? ? --> ( 1 ? ? --> 5 2 ) n ] {\displaystyle a_{n}={\frac {\sqrt {5}}{5}}\cdot \left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]}

線性代數(shù)解法

( F n + 2 F n + 1 ) = ( 1 1 1 0 ) ? ? --> ( F n + 1 F n ) {\displaystyle {\begin{pmatrix}F_{n+2}\\F_{n+1}\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}\cdot {\begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}}}

( F n + 2 F n + 1 F n + 1 F n ) = ( 1 1 1 0 ) n + 1 {\displaystyle {\begin{pmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n}\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n+1}}

構(gòu)建一個矩陣方程

設(shè)J n 為第n個月有生育能力的兔子數(shù)量，A n 為這一月份的兔子數(shù)量。

上式表達(dá)了兩個月之間，兔子數(shù)目之間的關(guān)系。而要求的是，A n+1 的表達(dá)式。

求矩陣的特征值： λ λ --> {\displaystyle \lambda }

行列式： ? ? --> λ λ --> ( 1 ? ? --> λ λ --> ) ? ? --> 1 × × --> 1 = λ λ --> 2 ? ? --> λ λ --> ? ? --> 1 {\displaystyle -\lambda (1-\lambda )-1\times 1=\lambda ^{2}-\lambda -1}

當(dāng)行列式的值為0，解得 λ λ --> 1 {\displaystyle \lambda _{1}} = 1 2 ( 1 + 5 ) {\displaystyle {\frac {1}{2}}(1+{\sqrt {5}})} 或 λ λ --> 2 {\displaystyle \lambda _{2}} = 1 2 ( 1 ? ? --> 5 ) {\displaystyle {\frac {1}{2}}(1-{\sqrt {5}})}

特征向量

將兩個特征值代入

求特征向量 x → → --> {\displaystyle {\vec {x}}} 得

x → → --> 1 {\displaystyle {\vec {x}}_{1}} = ( 1 1 2 ( 1 + 5 ) ) {\displaystyle {\begin{pmatrix}1\\{\frac {1}{2}}(1+{\sqrt {5}})\end{pmatrix}}}

x → → --> 2 {\displaystyle {\vec {x}}_{2}} = ( 1 1 2 ( 1 ? ? --> 5 ) ) {\displaystyle {\begin{pmatrix}1\\{\frac {1}{2}}(1-{\sqrt {5}})\end{pmatrix}}}

分解首向量

第一個月的情況是兔子一對，新生0對。

將它分解為用特征向量表示。

用數(shù)學(xué)歸納法證明

從

可得到

化簡矩陣方程

將（4） 代入 （5）

根據(jù)3

求A的表達(dá)式

現(xiàn)在在6的基礎(chǔ)上，可以很快求出A n+1 的表達(dá)式，將兩個特征值代入6中

（7）即為A n+1 的表達(dá)式

組合數(shù)解法

F n = ∑ ∑ --> i = 0 ∞ ∞ --> ( n ? ? --> i i ) {\displaystyle F_{n}=\sum _{i=0}^{\infty }{\binom {n-i}{i}}}

近似值

用計算機(jī)求解

可通過編程觀察斐波那契數(shù)列。分為兩類問題，一種已知數(shù)列中的某一項，求序數(shù)。第二種是已知序數(shù)，求該項的值。

可通過遞歸遞推的算法解決此兩個問題。 事實上當(dāng)n相當(dāng)巨大的時候，O（n）的遞推/遞歸非常慢……這時候要用到矩陣快速冪這一技巧，可以使遞歸加速到O(logn)

和黃金分割的關(guān)系

開普勒發(fā)現(xiàn)數(shù)列前、后兩項之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... ,也組成了一個數(shù)列，會趨近黃金分割：

斐波那契數(shù)亦可以用連分?jǐn)?shù)來表示：

1 1 = 1 2 1 = 1 + 1 1 3 2 = 1 + 1 1 + 1 1 5 3 = 1 + 1 1 + 1 1 + 1 1 8 5 = 1 + 1 1 + 1 1 + 1 1 + 1 1 {\displaystyle {\frac {1}{1}}=1\qquad {\frac {2}{1}}=1+{\frac {1}{1}}\qquad {\frac {3}{2}}=1+{\frac {1}{1+{\frac {1}{1}}}}\qquad {\frac {5}{3}}=1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}\qquad {\frac {8}{5}}=1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}}}}

F n = 1 5 [ ( 1 + 5 2 ) n ? ? --> ( 1 ? ? --> 5 2 ) n ] = φ φ --> n 5 ? ? --> ( 1 ? ? --> φ φ --> ) n 5 {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]={\varphi ^{n} \over {\sqrt {5}}}-{(1-\varphi )^{n} \over {\sqrt {5}}}}

而黃金分割數(shù)亦可以用無限連分?jǐn)?shù)表示：

而黃金分割數(shù)也可以用無限多重根號表示：

和自然的關(guān)系

許多的生物構(gòu)成都和斐波那契數(shù)列有正相關(guān)。例如人體從腳底至頭頂之距離和從肚臍至腳底之距趨近于 lim n → → --> ∞ ∞ --> F n F ( n ? ? --> 1 ) {\displaystyle \lim _{n\to \infty }{\frac {F_{n}}{F_{(n-向日葵}種子 ,向日葵的種子螺旋排列有99%是 F n {\displaystyle F_{n}} 。

恒等式

證明以下的恒等式有很多方法。以下會用組合論述來證明。

F n {\displaystyle F_{n}} 可以表示用多個1和多個2相加令其和等于 n {\displaystyle n} 的方法的數(shù)目。

不失一般性，我們假設(shè) n ≥ ≥ --> 1 {\displaystyle n\geq 1} ， F n + 1 {\displaystyle F_{n+1}} 是計算了將1和2加到n的方法的數(shù)目。若第一個被加數(shù)是1，有 F n {\displaystyle F_{n}} 種方法來完成對 n ? ? --> 1 {\displaystyle n-1} 的計算；若第一個被加數(shù)是2，有 F n ? ? --> 1 {\displaystyle F_{n-1}} 來完成對 n ? ? --> 2 {\displaystyle n-2} 的計算。因此，共有 F n + F n ? ? --> 1 {\displaystyle F_{n}+F_{n-1}} 種方法來計算n的值。

F 0 + F 1 + F 2 + F 3 + . . . + F n = F n + 2 ? ? --> 1 {\displaystyle F_{0}+F_{1}+F_{2}+F_{3}+...+F_{n}=F_{n+2}-1}

計算用多個1和多個2相加令其和等于 n + 1 {\displaystyle n+1} 的方法的數(shù)目，同時至少一個加數(shù)是2的情況。

如前所述，當(dāng) n > 0 {\displaystyle n>0} ，有 F n + 2 {\displaystyle F_{n+2}} 種這樣的方法。因為當(dāng)中只有一種方法不用使用2，就即 1 + 1 + . . . + 1 {\displaystyle 1+1+...+1} （ n + 1 {\displaystyle n+1} 項），于是我們從 F n + 2 {\displaystyle F_{n+2}} 減去1。

若第1個被加數(shù)是2，有 F n {\displaystyle F_{n}} 種方法來計算加至 n ? ? --> 1 {\displaystyle n-1} 的方法的數(shù)目；

若第2個被加數(shù)是2、第1個被加數(shù)是1，有 F n ? ? --> 1 {\displaystyle F_{n-1}} 種方法來計算加至 n ? ? --> 2 {\displaystyle n-2} 的方法的數(shù)目。

重復(fù)以上動作。

若第 n + 1 {\displaystyle n+1} 個被加數(shù)為2，它之前的被加數(shù)均為1，就有 F 0 {\displaystyle F_{0}} 種方法來計算加至0的數(shù)目。

若該數(shù)式包含2為被加數(shù)，2的首次出現(xiàn)位置必然在第1和 n + 1 {\displaystyle n+1} 的被加數(shù)之間。2在不同位置的情況都考慮到后，得出 F n + F n ? ? --> 1 + . . . + F 0 {\displaystyle F_{n}+F_{n-1}+...+F_{0}} 為要求的數(shù)目。

F 1 + 2 F 2 + 3 F 3 + . . . + n F n = n F n + 2 ? ? --> F n + 3 + 2 {\displaystyle F_{1}+2F_{2}+3F_{3}+...+nF_{n}=nF_{n+2}-F_{n+3}+2}

F 1 + F 3 + F 5 + . . . + F 2 n ? ? --> 1 = F 2 n {\displaystyle F_{1}+F_{3}+F_{5}+...+F_{2n-1}=F_{2n}}

F 2 + F 4 + F 6 + . . . + F 2 n = F 2 n + 1 ? ? --> 1 {\displaystyle F_{2}+F_{4}+F_{6}+...+F_{2n}=F_{2n+1}-1}

F 1 2 + F 2 2 + F 3 2 + . . . + F n 2 = F n F n + 1 {\displaystyle {F_{1}}^{2}+{F_{2}}^{2}+{F_{3}}^{2}+...+{F_{n}}^{2}=F_{n}F_{n+1}}

F n ? ? --> 1 F n + 1 ? ? --> F n 2 = ( ? ? --> 1 ) n {\displaystyle F_{n-1}F_{n+1}-{F_{n}}^{2}=(-1)^{n}}

定理

特別地，當(dāng) m = n 時，

F n {\displaystyle F_{n}} 整除 F m {\displaystyle F_{m}} ，當(dāng)且僅當(dāng) n 整除 m ，其中 n ≧3。

gcd ( F m , F n ) = F gcd ( m , n ) {\displaystyle \gcd(F_{m},F_{n})=F_{\gcd(m,n)}}

任意連續(xù)三個菲波那契數(shù)兩兩互素，亦即，對于每一個 n ，

相關(guān)的數(shù)列

費(fèi)波那西數(shù)列是費(fèi)波那西n步數(shù)列步數(shù)為2的特殊情況，也和盧卡斯數(shù)列有關(guān)。

和盧卡斯數(shù)列的關(guān)系

反費(fèi)波那西數(shù)列

反費(fèi)波那西數(shù)列的遞歸公式如下：

如果它以1,-1，之后的數(shù)是：1,-1,2,-3,5,-8, ...

即是 F 2 n + 1 = G 2 n + 1 , F 2 n = ? ? --> G 2 n {\displaystyle F_{2n+1}=G_{2n+1},F_{2n}=-G_{2n}} 。

反費(fèi)波那西數(shù)列兩項之間的比會趨近 ? ? --> 1 φ φ --> = ? ? --> 0.618 {\displaystyle -{\frac {1}{\varphi }}=-0.618} 。

巴都萬數(shù)列

費(fèi)波那西數(shù)列可以用一個接一個的正方形來表現(xiàn)，巴都萬數(shù)列則是用一個接一個的等邊三角形來表現(xiàn)，它有 P n = P n ? ? --> 2 + P n ? ? --> 3 {\displaystyle P_{n}=P_{n-2}+P_{n-3}} 的關(guān)系。

應(yīng)用

1970年，尤里·馬季亞謝維奇指出了偶角標(biāo)的斐波那契函數(shù)

正是滿足Julia Robison假設(shè)的丟番圖函數(shù)，因而證明了希爾伯特第十問題是不可解的。

相關(guān)猜想

斐波那契數(shù)列中是否存在無窮多個素數(shù)？

在斐波那契數(shù)列中，有素數(shù)： 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917…… 目前已知最大素數(shù)是第81839個斐波那契數(shù)，一共有17103位數(shù)。

程序參考

JavaScript迭代版

functionfib(n){varfib_n=function(curr,next,n){if(n==0){returncurr;}else{returnfib_n(next,curr+next,n-1);}}returnfib_n(0,1,n);}alert(fib(40));

C語言通項公式版

#include#includeintmain(){intn;doubleconstant_a=(1+sqrt(5))/2;doubleconstant_b=(1-sqrt(5))/2;doubleconstant_c=sqrt(5)/5;doublevalue_1=0;intvalue_2=0;scanf("%d",&n);if(n>0){for(inti=0;i<n;i++){value_1=constant_c*(pow(constant_a,i)-pow(constant_b,i));value_2=(int)value_1;printf("%d\n",value_2);}return0;}else{return-1;}}

Python語言通項公式版

1 # Fibonacci numbers module 2 3 deffib(n):# write Fibonacci series up to n 4 a,b=0,1 5 whileb<n: 6 print(b,end=" ") 7 a,b=b,a+b 8 print() 9 10 deffib2(n):# return Fibonacci series up to n11 result=[]12 a,b=0,113 whileb<n:14 result.append(b)15 a,b=b,a+b16 returnresult

fibs=[0,1]numZS=input("How many Fibonacci numbers do you want? ")foriinrange(numZS-2):fibs.append(fibs[-2]+fibs[-1])printfibs

Common Lisp

(defun fibs (x) (cond ((equal x 0) 1) ((equal x 1) 1) (t (+ (fibs (- x 1)) (fibs (- x 2)))))) (defun fibs (x) (do ((n 0 (+ n 1)) (i 1 j) (j 1 (+ i j))) ((equal n x) i)))

參考文獻(xiàn)

KNUTH, D. E.1997. The Art of Computer ProgrammingArt of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. Chapter 1.2.8.

Arakelian, Hrant (2014). Mathematics and History of the Golden Section . Logos, 404 p. ISBN 978-5-98704-663-0, (rus.)

克里福德A皮科夫.數(shù)學(xué)之戀.湖南科技出版社.

參見

齊肯多夫定理

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。