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)
