每日彙整: 2017-02-27

樹莓派、樹莓派之學習、樹莓派之教育

時間序列︰生成函數《五》

眼尖心細的讀者或許會覺得作者上一篇的推導太可疑︰

假設

G(x) = \sum \limits_{n=0}^{\infty} F_n x^n ，從遞迴關係可得

F_{n+2} = F_{n+1} + F_n , \ F_0 = 0, F_1 = 1

\longrightarrow F_{n+2} \cdot x^{n+2} = F_{n+1} \cdot x^{n+2} + F_n \cdot x^{n+2}

\longrightarrow \sum \limits_{n=0}^{\infty} F_{n+2} x^{n+2} = x \cdot \sum \limits_{n=0}^{\infty} F_{n+1} x^{n+1} + x^2 \cdot \sum \limits_{n=0}^{\infty} F_n x^n

\longrightarrow G(x) - x = x \cdot G(x) + x^2 \cdot G(x)

\therefore G(x) = \frac{x}{1 - x - x^2}

如果\lambda_{+} , \lambda_{-} 是 1 + x - x^2 = 0 的兩個根，而且 \lambda_{+} > \lambda_{-} ，也就是說 \lambda_{+} = \frac{1 + \sqrt {5} } {2} , \lambda_{-} = \frac{1 - \sqrt {5} } {2} ，那麼 G(x) 可改寫為

\frac{1}{\lambda_{+} - \lambda_{-}} \left( \frac{1}{1 - \lambda_{+} x} - \frac{1}{1 - \lambda_{-} x} \right)

 

分明是偷用著費波那契數列的特徵方程式 r^2 = r + 1 ，而不是生成函數 G(x) 的分母方程式 1 - x - x^2 = 0 做部分分式分解。非為著辯解，實乃費波那契數列有豐富的性質，不過勸思勸學而已。

Fibonacci Number

The Fibonacci numbers are the sequence of numbers {F_n}_(n=1)^infty defined by the linear recurrence equation

F_n=F_(n-1)+F_(n-2)
(1)

with F_1=F_2=1. As a result of the definition (1), it is conventional to define F_0=0.

The Fibonacci numbers for n=1, 2, … are 1, 1, 2, 3, 5, 8, 13, 21, … (OEIS A000045).

Fibonacci numbers can be viewed as a particular case of the Fibonacci polynomials F_n(x) with F_n=F_n(1).

Fibonacci numbers are implemented in the Wolfram Language as Fibonacci[n].

The Fibonacci numbers are also a Lucas sequence U_n(1,-1), and are companions to the Lucas numbers (which satisfy the same recurrence equation).

FoxTrot by Bill Amend

The above cartoon (Amend 2005) shows an unconventional sports application of the Fibonacci numbers (left two panels). (The right panel instead applies the Perrin sequence).

 

此處先補足推導過程，再言其他。假設 \alpha > \beta 是分母方程式 1 - x - x^2 = 0 的兩個根。解之可得 \alpha = \frac{-1 + \sqrt{5}}{2} , \ \beta = \frac{-1 - \sqrt{5}}{2} ，當然 \alpha + \beta = -1 , \ \alpha \cdot \beta = -1 。由於

{\alpha}^{-1} = \frac{2}{-1 + \sqrt{5}} = {\lambda}_{+} ，

{\beta}^{-1} = \frac{2}{-1 - \sqrt{5}} = {\lambda}_{-} 。因此

\frac{x}{1 - x - x^2} = - \frac{1}{\alpha - \beta} \left( \frac{\alpha}{x -\alpha} - \frac{\beta}{x- \beta} \right)

= \frac{{\lambda}_{+} {\lambda}_{-}}{{\lambda}_{+} - {\lambda}_{-}} \left( \frac{1}{{\alpha}^{-1} x - 1} - \frac{1}{{\beta}^{-1} x - 1} \right)

\therefore = \frac{1}{\lambda_{+} - \lambda_{-}} \left( \frac{1}{1 - \lambda_{+} x} - \frac{1}{1 - \lambda_{-} x} \right) 。

【※ 註︰ {\lambda}_{+} + {\lambda}_{-} = 1 , \ {\lambda}_{+} {\lambda}_{-} = -1 】

 

事實上，那個 {\lambda}_{+} 就是著名的

黃金比例

黃金比例，又稱黃金分割[1]，是一個數學常數，一般以希臘字母  \phi 表示[2][3][4]。可以透過以下代數式定義：

  {\frac {a+b}{a}}={\frac {a}{b}}\,{\stackrel {\text{def}}{=}}\,\phi \quad (a>b>0)

這也是黃金比例一名的由來。
黃金比例的準確值為  {\frac {1+{\sqrt {5}}}{2}}，所以是無理數，而大約值則為（小數點後20位，OEIS A001622）：

\phi =1.61803398874989484820\ldots

應用時一般取1.618，就像圓周率在應用時取3.14一樣。

黃金分割具有嚴格的比例性、藝術性、和諧性，蘊藏著豐富的美學價值，而且呈現於不少動物和植物的外觀。現今很多工業產品、電子產品、建築物或藝術品均普遍應用黃金分割，展現其功能性與美觀性。

A golden rectangle (in pink) with longer side a and shorter side b, when placed adjacent to a square with sides of length a, will produce a similar golden rectangle with longer side a + b and shorter side a. This illustrates the relationship  {\frac {a+b}{a}}={\frac {a}{b}}\equiv \varphi .

 

。她的歷史充滿韻律

Origins

The Fibonacci sequence appears in Indian mathematics, in connection with Sanskrit prosody.[8][13] In the Sanskrit tradition of prosody, there was interest in enumerating all patterns of long (L) syllables that are 2 units of duration, and short (S) syllables that are 1 unit of duration. Counting the different patterns of L and S of a given duration results in the Fibonacci numbers: the number of patterns that are m short syllables long is the Fibonacci number Fm + 1.[9]

Susantha Goonatilake writes that the development of the Fibonacci sequence “is attributed in part to Pingala (200 BC), later being associated with Virahanka (c. 700 AD), Gopāla (c. 1135), and Hemachandra (c. 1150)”.[7] Parmanand Singh cites Pingala’s cryptic formula misrau cha (“the two are mixed”) and cites scholars who interpret it in context as saying that the cases for m beats (Fm+1) is obtained by adding a [S] to Fm cases and [L] to the Fm−1 cases. He dates Pingala before 450 BC.[14]

However, the clearest exposition of the sequence arises in the work of Virahanka (c. 700 AD), whose own work is lost, but is available in a quotation by Gopala (c. 1135):

Variations of two earlier meters [is the variation]… For example, for [a meter of length] four, variations of meters of two [and] three being mixed, five happens. [works out examples 8, 13, 21]… In this way, the process should be followed in all mātrā-vṛttas [prosodic combinations].[15]

The sequence is also discussed by Gopala (before 1135 AD) and by the Jain scholar Hemachandra (c. 1150).

A page of Fibonacci‘s Liber Abaci from the Biblioteca Nazionale di Firenze showing (in box on right) the Fibonacci sequence with the position in the sequence labeled in Latin and Roman numerals and the value in Hindu-Arabic numerals.

 

，以及具有旺盛的生育力。

Outside India, the Fibonacci sequence first appears in the book Liber Abaci (1202) by Fibonacci.[6] Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that: a newly born pair of rabbits, one male, one female, are put in a field; rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits; rabbits never die and a mating pair always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was: how many pairs will there be in one year?

  • At the end of the first month, they mate, but there is still only 1 pair.
  • At the end of the second month the female produces a new pair, so now there are 2 pairs of rabbits in the field.
  • At the end of the third month, the original female produces a second pair, making 3 pairs in all in the field.
  • At the end of the fourth month, the original female has produced yet another new pair, and the female born two months ago also produces her first pair, making 5 pairs.

At the end of the nth month, the number of pairs of rabbits is equal to the number of new pairs (which is the number of pairs in month n − 2) plus the number of pairs alive last month (n − 1). This is the nth Fibonacci number.[16]

The name “Fibonacci sequence” was first used by the 19th-century number theorist Édouard Lucas.[17]

The number of rabbits form the Fibonacci sequence