1202年，萊昂納多·斐波那契，也稱為斐波那契，提出了這個問題。
某人將一對兔子放在一個四周都有圍牆的地方。如果假設每對兔子每月生一對新的兔子，並且從第二個月開始這些新兔子就可以繁殖，那麼一年內從那一對兔子可以繁殖出多少對兔子？
這超越了人口增長基本指數模型，它包括了新生兒最初一段時期不育的事實。然而，它保留了其他簡化假設，例如沒有妊娠期和沒有死亡率。
在下個月出現的新的兔子對的數量僅僅是上個月存活的兔子對的數量，因為這些兔子都會生育，因為它們已經存活了兩個月。下個月存活的兔子對的數量是當前月存活的數量加上新生兒數量的總和。
f ( n + 1 ) = f ( n ) + f ( n − 1 ) where f ( 0 ) = 1 , f ( 1 ) = 1 {\displaystyle f(n+1)=f(n)+f(n-1)\qquad {\text{where }}f(0)=1{\text{, }}f(1)=1} 這是一個遞推關係 的例子（之所以稱之為遞推關係，是因為 f {\displaystyle f} f {\displaystyle f}
month 0 1 2 3 4 5 6 7 8 9 10 11 12 pairs 1 1 2 3 5 8 13 21 34 55 89 144 233 {\displaystyle {\begin{array}{r|ccccccccccccc}{\textit {month}}&0&1&2&3&4&5&6&7&8&9&10&11&12\\\hline {\textit {pairs}}&1&1&2&3&5&8&13&21&34&55&89&144&233\end{array}}}
斐波那契數列 。本章的內容可以用來給出一個公式，我們可以用它來計算 f ( n + 1 ) {\displaystyle f(n+1)} f ( n ) {\displaystyle f(n)} f ( n − 1 ) {\displaystyle f(n-1)}
為此，觀察到遞推是一個線性關係，因此我們可以給出它的合適矩陣形式。
( 1 1 1 0 ) ( f ( n ) f ( n − 1 ) ) = ( f ( n + 1 ) f ( n ) ) where ( f ( 1 ) f ( 0 ) ) = ( 1 1 ) {\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}{\begin{pmatrix}f(n)\\f(n-1)\end{pmatrix}}={\begin{pmatrix}f(n+1)\\f(n)\end{pmatrix}}\qquad {\text{where }}{\begin{pmatrix}f(1)\\f(0)\end{pmatrix}}={\begin{pmatrix}1\\1\end{pmatrix}}} 然後，當我們將 T {\displaystyle T} v → n {\displaystyle {\vec {v}}_{n}} f ( n + 1 ) {\displaystyle f(n+1)} f ( n ) {\displaystyle f(n)} v → n = T n v → 0 {\displaystyle {\vec {v}}_{n}=T^{n}{\vec {v}}_{0}} T {\displaystyle T} T = P D P − 1 {\displaystyle T=PDP^{-1}} T n = P D n P − 1 {\displaystyle T^{n}=PD^{n}P^{-1}} D {\displaystyle D} n {\displaystyle n} D {\displaystyle D} n {\displaystyle n}
T {\displaystyle T} λ 2 − λ − 1 {\displaystyle \lambda ^{2}-\lambda -1} ( 1 + 5 ) / 2 {\displaystyle (1+{\sqrt {5}})/2} ( 1 − 5 ) / 2 {\displaystyle (1-{\sqrt {5}})/2}
( 1 1 1 0 ) = ( 1 + 5 2 1 − 5 2 1 1 ) ( 1 + 5 2 0 0 1 − 5 2 ) ( 1 5 − 1 − 5 2 5 − 1 5 1 + 5 2 5 ) {\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}={\begin{pmatrix}{\frac {1+{\sqrt {5}}}{2}}&{\frac {1-{\sqrt {5}}}{2}}\\1&1\end{pmatrix}}{\begin{pmatrix}{\frac {1+{\sqrt {5}}}{2}}&0\\0&{\frac {1-{\sqrt {5}}}{2}}\end{pmatrix}}{\begin{pmatrix}{\frac {1}{\sqrt {5}}}&-{\frac {1-{\sqrt {5}}}{2{\sqrt {5}}}}\\{\frac {-1}{\sqrt {5}}}&{\frac {1+{\sqrt {5}}}{2{\sqrt {5}}}}\end{pmatrix}}} 介紹向量並取其 n {\displaystyle n}
( f ( n + 1 ) f ( n ) ) = ( 1 1 1 0 ) n ( f ( 1 ) f ( 0 ) ) = ( 1 + 5 2 1 − 5 2 1 1 ) ( 1 + 5 2 n 0 0 1 − 5 2 n ) ( 1 5 − 1 − 5 2 5 − 1 5 1 + 5 2 5 ) ( f ( 1 ) f ( 0 ) ) {\displaystyle {\begin{array}{rl}{\begin{pmatrix}f(n+1)\\f(n)\end{pmatrix}}&={\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}{\begin{pmatrix}f(1)\\f(0)\end{pmatrix}}\\&={\begin{pmatrix}{\frac {1+{\sqrt {5}}}{2}}&{\frac {1-{\sqrt {5}}}{2}}\\1&1\end{pmatrix}}{\begin{pmatrix}{\frac {1+{\sqrt {5}}}{2}}^{n}&0\\0&{\frac {1-{\sqrt {5}}}{2}}^{n}\end{pmatrix}}{\begin{pmatrix}{\frac {1}{\sqrt {5}}}&-{\frac {1-{\sqrt {5}}}{2{\sqrt {5}}}}\\{\frac {-1}{\sqrt {5}}}&{\frac {1+{\sqrt {5}}}{2{\sqrt {5}}}}\end{pmatrix}}{\begin{pmatrix}f(1)\\f(0)\end{pmatrix}}\end{array}}} 我們可以從該等式的第二項計算 f ( n ) {\displaystyle f(n)}
f ( n ) = 1 5 [ ( 1 + 5 2 ) n + 1 − ( 1 − 5 2 ) n + 1 ] {\displaystyle f(n)={\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+1}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n+1}\right]} 注意到 f {\displaystyle f} ( 1 − 5 ) / 2 {\displaystyle (1-{\sqrt {5}})/2}
線性遞推關係 具有以下形式
f ( n + 1 ) = a n f ( n ) + a n − 1 f ( n − 1 ) + ⋯ + a n − k f ( n − k ) {\displaystyle f(n+1)=a_{n}f(n)+a_{n-1}f(n-1)+\dots +a_{n-k}f(n-k)} (它也被稱為 *差分方程*). 0 = − f ( n + 1 ) + a n f ( n ) + a n − 1 f ( n − 1 ) + ⋯ + a n − k f ( n − k ) {\displaystyle 0=-f(n+1)+a_{n}f(n)+a_{n-1}f(n-1)+\dots +a_{n-k}f(n-k)} k {\displaystyle k} f ( 0 ) {\displaystyle f(0)} f ( k ) {\displaystyle f(k)} 2 {\displaystyle 2} f ( 0 ) = 1 {\displaystyle f(0)=1} f ( 1 ) = 1 {\displaystyle f(1)=1} f ( 2 ) {\displaystyle f(2)} f ( 3 ) {\displaystyle f(3)} f ( n ) {\displaystyle f(n)}
首先，我們定義我們正在處理的向量空間。令 V {\displaystyle V} N = { 0 , 1 , 2 , … } {\displaystyle \mathbb {N} =\{0,1,2,\ldots \}} f {\displaystyle f} { 1 , 2 , … } {\displaystyle \{1,2,\ldots \}} 0 {\displaystyle 0}
暫時不考慮初始條件，對於任何遞迴關係，我們可以考慮其解空間 V {\displaystyle V} S {\displaystyle S} f {\displaystyle f} g {\displaystyle g} g ( 0 ) = 1 {\displaystyle g(0)=1} g ( 1 ) = 3 {\displaystyle g(1)=3} g ( 2 ) = 4 {\displaystyle g(2)=4} g ( 3 ) = 7 {\displaystyle g(3)=7}
子集 S {\displaystyle S} V {\displaystyle V} f 1 {\displaystyle f_{1}} f 2 {\displaystyle f_{2}}
a n + 1 ( f 1 + f 2 ) ( n + 1 ) + ⋯ + a n − k ( f 1 + f 2 ) ( n − k ) {\displaystyle a_{n+1}(f_{1}+f_{2})(n+1)+\dots +a_{n-k}(f_{1}+f_{2})(n-k)} = ( a n + 1 f 1 ( n + 1 ) + ⋯ + a n − k f 1 ( n − k ) ) + ( a n + 1 f 2 ( n + 1 ) + ⋯ + a n − k f 2 ( n − k ) ) = 0. {\displaystyle {\begin{aligned}&=(a_{n+1}f_{1}(n+1)+\dots +a_{n-k}f_{1}(n-k))\\&\quad +(a_{n+1}f_{2}(n+1)+\dots +a_{n-k}f_{2}(n-k))\\&=0.\end{aligned}}} 而且，它在標量乘法下是封閉的，因為
a n + 1 ( r f 1 ) ( n + 1 ) + ⋯ + a n − k ( r f 1 ) ( n − k ) {\displaystyle a_{n+1}(rf_{1})(n+1)+\dots +a_{n-k}(rf_{1})(n-k)} = r ( a n + 1 f 1 ( n + 1 ) + ⋯ + a n − k f 1 ( n − k ) ) = r ⋅ 0 = 0. {\displaystyle {\begin{aligned}&=r(a_{n+1}f_{1}(n+1)+\dots +a_{n-k}f_{1}(n-k))\\&=r\cdot 0\\&=0.\end{aligned}}} 我們可以給出 S {\displaystyle S} S {\displaystyle S} R k {\displaystyle \mathbb {R} ^{k}}
f ↦ ( f ( 0 ) f ( 1 ) ⋮ f ( k ) ) {\displaystyle f\mapsto {\begin{pmatrix}f(0)\\f(1)\\\vdots \\f(k)\end{pmatrix}}} 問題 3 表明此對映是線性的。因為，如上所述，遞推關係的任何解都由 k {\displaystyle k} S {\displaystyle S} k {\displaystyle k}
因此（同樣，沒有任何初始條件），我們可以透過取僅 k {\displaystyle k} k {\displaystyle k}
為此，我們將遞推關係 f ( n + 1 ) = a n f ( n ) + ⋯ + a n − k f ( n − k ) {\displaystyle f(n+1)=a_{n}f(n)+\dots +a_{n-k}f(n-k)}
( a n a n − 1 a n − 2 … a n − k + 1 a n − k 1 0 0 … 0 0 0 1 0 0 0 1 ⋮ ⋮ ⋱ ⋮ 0 0 0 … 1 0 ) ( f ( n ) f ( n − 1 ) ⋮ f ( n − k ) ) = ( f ( n + 1 ) f ( n ) ⋮ f ( n − k + 1 ) ) {\displaystyle {\begin{pmatrix}a_{n}&a_{n-1}&a_{n-2}&\ldots &a_{n-k+1}&a_{n-k}\\1&0&0&\ldots &0&0\\0&1&0\\0&0&1\\\vdots &\vdots &&\ddots &&\vdots \\0&0&0&\ldots &1&0\end{pmatrix}}{\begin{pmatrix}f(n)\\f(n-1)\\\vdots \\f(n-k)\end{pmatrix}}={\begin{pmatrix}f(n+1)\\f(n)\\\vdots \\f(n-k+1)\end{pmatrix}}} 在試圖找到矩陣的特徵函式時，我們可以看到 2 × 2 {\displaystyle 2\!\times \!2}
( a n − λ a n − 1 1 − λ ) = λ 2 − a n λ − a n − 1 {\displaystyle {\begin{pmatrix}a_{n}-\lambda &a_{n-1}\\1&-\lambda \end{pmatrix}}=\lambda ^{2}-a_{n}\lambda -a_{n-1}} 以及 3 × 3 {\displaystyle 3\!\times \!3}
( a n − λ a n − 1 a n − 2 1 − λ 0 0 1 − λ ) = − λ 3 + a n λ 2 + a n − 1 λ + a n − 2 {\displaystyle {\begin{pmatrix}a_{n}-\lambda &a_{n-1}&a_{n-2}\\1&-\lambda &0\\0&1&-\lambda \end{pmatrix}}=-\lambda ^{3}+a_{n}\lambda ^{2}+a_{n-1}\lambda +a_{n-2}} 問題 4 表明特徵方程如下所示。
| a n − λ a n − 1 a n − 2 … a n − k + 1 a n − k 1 − λ 0 … 0 0 0 1 − λ 0 0 1 ⋮ ⋮ ⋱ ⋮ 0 0 0 … 1 − λ | {\displaystyle {\begin{vmatrix}a_{n}-\lambda &a_{n-1}&a_{n-2}&\ldots &a_{n-k+1}&a_{n-k}\\1&-\lambda &0&\ldots &0&0\\0&1&-\lambda \\0&0&1\\\vdots &\vdots &&\ddots &&\vdots \\0&0&0&\ldots &1&-\lambda \end{vmatrix}}} = ± ( − λ k + a n λ k − 1 + a n − 1 λ k − 2 + ⋯ + a n − k + 1 λ + a n − k ) {\displaystyle =\pm (-\lambda ^{k}+a_{n}\lambda ^{k-1}+a_{n-1}\lambda ^{k-2}+\dots +a_{n-k+1}\lambda +a_{n-k})} 我們將這個多項式稱為與遞推關係“相關”的多項式。（我們將找到這個多項式的根，因此可以忽略 ± {\displaystyle \pm }
如果 − λ k + a n λ k − 1 + a n − 1 λ k − 2 + ⋯ + a n − k + 1 λ + a n − k {\displaystyle -\lambda ^{k}+a_{n}\lambda ^{k-1}+a_{n-1}\lambda ^{k-2}+\dots +a_{n-k+1}\lambda +a_{n-k}} f ( n ) {\displaystyle f(n)} k {\displaystyle k} k {\displaystyle k}
假設 r 1 {\displaystyle r_{1}} r 2 {\displaystyle r_{2}} r k {\displaystyle r_{k}} f r 1 ( n ) = r 1 n {\displaystyle f_{r_{1}}(n)=r_{1}^{n}} f r k ( n ) = r k n {\displaystyle f_{r_{k}}(n)=r_{k}^{n}} 問題 2 顯示，每個函式都是該遞推關係的解，並且這 k {\displaystyle k} f ( n + 1 ) = a n f ( n ) + ⋯ + a n − k f ( n − k ) {\displaystyle f(n+1)=a_{n}f(n)+\dots +a_{n-k}f(n-k)} 0 = − f ( n + 1 ) + a n f ( n ) + ⋯ + a n − k f ( n − k ) {\displaystyle 0=-f(n+1)+a_{n}f(n)+\dots +a_{n-k}f(n-k)} 0 = − λ k + a n λ k − 1 + ⋯ + a n − k + 1 λ + a n − k {\displaystyle 0=-\lambda ^{k}+a_{n}\lambda ^{k-1}+\dots +a_{n-k+1}\lambda +a_{n-k}} r 1 {\displaystyle r_{1}} r k {\displaystyle r_{k}} f ( n ) = c 1 r 1 n + c 2 r 2 n + ⋯ + c k r k n {\displaystyle f(n)=c_{1}r_{1}^{n}+c_{2}r_{2}^{n}+\dots +c_{k}r_{k}^{n}} c 1 , … , c n ∈ R {\displaystyle c_{1},\dots ,c_{n}\in \mathbb {R} }
現在，給定一些初始條件，以便我們對特定解感興趣，我們可以求解 c 1 {\displaystyle c_{1}} c n {\displaystyle c_{n}} − λ 2 + λ + 1 {\displaystyle -\lambda ^{2}+\lambda +1} ( 1 ± 5 ) / 2 {\displaystyle (1\pm {\sqrt {5}})/2} f ( n ) = c 1 ( ( 1 + 5 ) / 2 ) n + c 2 ( ( 1 − 5 ) / 2 ) n {\displaystyle f(n)=c_{1}((1+{\sqrt {5}})/2)^{n}+c_{2}((1-{\sqrt {5}})/2)^{n}} n = 0 {\displaystyle n=0} n = 1 {\displaystyle n=1}
c 1 + c 2 = 1 ( 1 + 5 / 2 ) c 1 + ( 1 − 5 / 2 ) c 2 = 1 {\displaystyle {\begin{array}{*{2}{rc}r}c_{1}&+&c_{2}&=&1\\(1+{\sqrt {5}}/2)c_{1}&+&(1-{\sqrt {5}}/2)c_{2}&=&1\end{array}}} 這產生 c 1 = 1 / 5 {\displaystyle c_{1}=1/{\sqrt {5}}} c 2 = − 1 / 5 {\displaystyle c_{2}=-1/{\sqrt {5}}}
最後，我們考慮非齊次情況，其中關係具有形式 f ( n + 1 ) = a n f ( n ) + a n − 1 f ( n − 1 ) + ⋯ + a n − k f ( n − k ) + b {\displaystyle f(n+1)=a_{n}f(n)+a_{n-1}f(n-1)+\dots +a_{n-k}f(n-k)+b} b {\displaystyle b}
1883 年，愛德華·盧卡斯提出了以下問題。
在貝納勒斯的大寺院中，在標誌著世界中心的圓頂下方，放置著一塊黃銅盤，上面固定著三根鑽石針，每根高一肘，粗如蜜蜂的身體。在創世之初，上帝在其中一根針上放置了 64 個純金圓盤，最大的圓盤放在黃銅盤上，其他圓盤則依次變小，直到最上面的一個。這就是布拉瑪之塔。日夜不停，僧侶們根據布拉瑪的固定且不變的法則，將圓盤從一根鑽石針轉移到另一根鑽石針上，這些法則要求值班的僧侶一次只能移動一個圓盤，並且必須將這個圓盤放在一根針上，以便沒有更小的圓盤在它下面。當 64 個圓盤從上帝在創世之初放置它們的針上轉移到其他任何一根針上時，塔樓、寺廟和婆羅門都會化為塵土，伴隨著一聲巨響，世界將不復存在。
（德·帕維爾 (1884) 從 鮑爾 (1962) 中的翻譯。）
需要多少次圓盤移動？我們不會直接處理 64 個圓盤的問題，而是從三個圓盤開始，考慮更少圓盤的情況。
首先，所有三個圓盤都在同一根針上。
將小圓盤移到最遠端的針上，將中等大小的圓盤移到中間的針上，然後將小圓盤移到中間的針上，我們得到以下結果。
現在我們可以將大圓盤移過來。然後，為了完成，我們重複移動較小圓盤的過程，這次它們最終會落在第三根針上，在大圓盤的頂部。
所以要看到的是，為了移動最大的圓盤，也就是底部的圓盤，我們至少需要：首先將較小的圓盤移動到中間的針上，然後移動大圓盤，然後將所有較小的圓盤從中間的針上移動到最終的針上。這三個步驟給了我們這個遞迴關係。
T ( n + 1 ) = T ( n ) + 1 + T ( n ) = 2 T ( n ) + 1 where T ( 1 ) = 1 {\displaystyle T(n+1)=T(n)+1+T(n)=2T(n)+1\quad {\text{where }}T(1)=1} 我們可以很容易地得到 T {\displaystyle T}
n 1 2 3 4 5 6 7 8 9 10 T ( n ) 1 3 7 15 31 63 127 255 511 1023 {\displaystyle {\begin{array}{r|cccccccccc}n&1&2&3&4&5&6&7&8&9&10\\\hline T(n)&1&3&7&15&31&63&127&255&511&1023\end{array}}}
我們認識到它們只是 2 的冪減 1。
為了推匯出這個等式而不是僅僅猜測它，我們將原始關係寫成 − 1 = − T ( n + 1 ) + 2 T ( n ) {\displaystyle -1=-T(n+1)+2T(n)} 0 = − T ( n ) + 2 T ( n − 1 ) {\displaystyle 0=-T(n)+2T(n-1)} − λ + 2 {\displaystyle -\lambda +2} r 1 = 2 {\displaystyle r_{1}=2} T ( n ) = c 1 2 n {\displaystyle T(n)=c_{1}2^{n}}
這是齊次解。現在我們需要一個特解。
因為非齊次關係 − 1 = − T ( n + 1 ) + 2 T ( n ) {\displaystyle -1=-T(n+1)+2T(n)} T ( n ) = − 1 {\displaystyle T(n)=-1} T ( n + 1 ) = 2 T ( n ) + 1 {\displaystyle T(n+1)=2T(n)+1} T ( n ) = c 1 2 n − 1 {\displaystyle T(n)=c_{1}2^{n}-1}
初始條件 T ( 1 ) = 1 {\displaystyle T(1)=1} c 1 = 1 {\displaystyle c_{1}=1} n {\displaystyle n} 2 n − 1 {\displaystyle 2^{n}-1}
在更復雜的情況下找到一個特定的解，自然地，也更加複雜。關於遞推關係的令人愉快且有益，但具有挑戰性的資料來源是 (Graham, Knuth & Patashnik 1988 )。對於更多關於漢諾塔的資訊，(Ball 1962 ) 或 (Gardner 1957 ) 是很好的起點。(Hofstadter 1985 ) 也是如此。一些用於嘗試一些遞推關係的計算機程式碼在練習之後給出。
問題 3
檢查給定的 S {\displaystyle S} R k {\displaystyle \mathbb {R} ^{k}}
問題 4
證明矩陣的特徵方程如所述，即與關係相關的多項式。（提示：展開最後一列，並使用歸納法將起作用。）
問題 6
（這指的是下面的計算機程式碼中給出的值 T ( 64 ) = 18 , 446 , 744 , 073 , 709 , 551 , 615 {\displaystyle T(64)=18,446,744,073,709,551,615}
計算機程式碼
首先，漢諾塔程式碼是對遞推關係的直接實現。
(define (tower-of-hanoi-moves n)
(if (= n 1)
1
(+ (* (tower-of-hanoi-moves (- n 1))
2)
1) ) )
T ( 64 ) {\displaystyle T(64)} 2 ∗ T ( 63 ) − 1 {\displaystyle 2*T(63)-1} T ( 63 ) {\displaystyle T(63)} 2 {\displaystyle 2} 1 {\displaystyle 1} T ( 63 ) {\displaystyle T(63)} 2 ∗ T ( 62 ) − 1 {\displaystyle 2*T(62)-1} T ( 62 ) {\displaystyle T(62)} 63 {\displaystyle 63} T ( 1 ) {\displaystyle T(1)} T ( 1 ) = 1 {\displaystyle T(1)=1} T ( 2 ) {\displaystyle T(2)} T ( 64 ) {\displaystyle T(64)}
下一個程式計算前幾個值的表。（一些語言說明：'() 是空列表，即空序列，cons 將某個元素推送到列表開頭。注意，在最後一行，proc 過程被呼叫，引數為 n。）
(define (first-few-outputs proc n)
(first-few-outputs-helper proc n '()) )
;
(define (first-few-outputs-aux proc n lst)
(if (< n 1)
lst
(first-few-outputs-aux proc (- n 1) (cons (proc n) lst)) ) )
SCM 提示符下的會話如下所示。
>(first-few-outputs tower-of-hanoi-moves 64)
Evaluation took 120 mSec
(1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767
65535 131071 262143 524287 1048575 2097151 4194303 8388607
16777215 33554431 67108863 134217727 268435455 536870911
1073741823 2147483647 4294967295 8589934591 17179869183
34359738367 68719476735 137438953471 274877906943 549755813887
1099511627775 2199023255551 4398046511103 8796093022207
17592186044415 35184372088831 70368744177663 140737488355327
281474976710655 562949953421311 1125899906842623
2251799813685247 4503599627370495 9007199254740991
18014398509481983 36028797018963967 72057594037927935
144115188075855871 288230376151711743 576460752303423487
1152921504606846975 2305843009213693951 4611686018427387903
9223372036854775807 18446744073709551615)
T ( 1 ) {\displaystyle T(1)} T ( 64 ) {\displaystyle T(64)} 120 {\displaystyle 120}
解決方案
Ball, W.W. (1962), Mathematical Recreations and Essays , MacMillan De Parville (1884), La Nature , vol. I, Paris, pp. 285–286 Gardner, Martin (May. 1957), "Mathematical Games: About the remarkable similarity between the Icosian Game and the Tower of Hanoi", Scientific American : 150–154 Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1988), Concrete Mathematics , Addison-Wesley Hofstadter, Douglas R. (1985), Metamagical Themas:~Questing for the Essence of Mind and Pattern , Basic Books 
![{\displaystyle f(n)={\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+1}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n+1}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1d7d2d6735b19864569278d4689ec6f0eb0d142)
