Editing Fibonacci sequence (section)

== Matrix form ==
A 2-dimensional system of linear [[difference equation]]s that describes the Fibonacci sequence is

<math display=block>
\begin{pmatrix} F_{k+2} \\ F_{k+1} \end{pmatrix}
= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{k+1} \\ F_{k}\end {pmatrix} </math>
alternatively denoted
<math display=block> \vec F_{k+1} = \mathbf{A} \vec F_{k},</math>

which yields <math>\vec F_n = \mathbf{A}^n  \vec F_0</math>.  The [[eigenvalue]]s of the [[matrix (mathematics)|matrix]] {{math|'''A'''}} are <math>\varphi=\tfrac12\bigl(1+\sqrt5~\!\bigr)</math> and <math>\psi=-\varphi^{-1}=\tfrac12\bigl(1-\sqrt5~\!\bigr)</math> corresponding to the respective [[eigenvector]]s
<math display=block>\vec \mu=\begin{pmatrix} \varphi \\ 1 \end{pmatrix}, \quad \vec\nu=\begin{pmatrix} -\varphi^{-1} \\ 1 \end{pmatrix}.</math>

As the initial value is
<math display=block>\vec F_0=\begin{pmatrix} 1 \\ 0 \end{pmatrix}=\frac{1}{\sqrt{5}}\vec{\mu}\,-\,\frac{1}{\sqrt{5}}\vec{\nu},</math>

it follows that the {{mvar|n}}th element is
<math display=block>\begin{align}
\vec F_n\ &= \frac{1}{\sqrt{5}}A^n\vec\mu-\frac{1}{\sqrt{5}}A^n\vec\nu \\
&= \frac{1}{\sqrt{5}}\varphi^n\vec\mu - \frac{1}{\sqrt{5}}(-\varphi)^{-n}\vec\nu \\
&= \cfrac{1}{\sqrt{5}}\left(\cfrac{1+\sqrt{5}}{2}\right)^{\!n}\begin{pmatrix} \varphi \\ 1 \end{pmatrix} \,-\, \cfrac{1}{\sqrt{5}}\left(\cfrac{1-\sqrt{5}}{2}\right)^{\!n}\begin{pmatrix}{c} -\varphi^{-1} \\ 1 \end{pmatrix}.
\end{align}</math>

From this, the {{mvar|n}}th element in the Fibonacci series may be read off directly as a [[closed-form expression]]:
<math display=block>
F_n = \cfrac{1}{\sqrt{5}}\left(\cfrac{1+\sqrt{5}}{2}\right)^{\!n} - \, \cfrac{1}{\sqrt{5}}\left(\cfrac{1-\sqrt{5}}{2}\right)^{\!n}.
</math>

Equivalently, the same computation may be performed by [[Matrix diagonalization|diagonalization]] of {{math|'''A'''}} through use of its [[eigendecomposition]]:

<math display=block>\begin{align} A & = S\Lambda S^{-1}, \\[3mu]
 A^n & = S\Lambda^n S^{-1},
\end{align}</math>

where 

<math display=block>
\Lambda=\begin{pmatrix} \varphi & 0 \\ 0 & -\varphi^{-1}\! \end{pmatrix}, \quad
S=\begin{pmatrix} \varphi & -\varphi^{-1} \\ 1 & 1 \end{pmatrix}.
</math>

The closed-form expression for the {{mvar|n}}th element in the Fibonacci series is therefore given by

<math display=block>\begin{align} \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} & = A^{n} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}\ \\
 & = S \Lambda^n S^{-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} \\
 & = S \begin{pmatrix} \varphi^n & 0 \\ 0 & (-\varphi)^{-n} \end{pmatrix} S^{-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} \\
 & = \begin{pmatrix} \varphi & -\varphi^{-1} \\ 1 & 1 \end{pmatrix}
     \begin{pmatrix}\varphi^n & 0 \\ 0 & (-\varphi)^{-n} \end{pmatrix}
     \frac{1}{\sqrt{5}}\begin{pmatrix} 1 & \varphi^{-1} \\ -1 & \varphi \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix},
\end{align}</math>

which again yields
<math display=block>F_n = \cfrac{\varphi^n-(-\varphi)^{-n}}{\sqrt{5}}.</math>

The matrix {{math|'''A'''}} has a [[determinant]] of −1, and thus it is a 2&thinsp;×&thinsp;2 [[unimodular matrix]].

This property can be understood in terms of the [[continued fraction]] representation for the golden ratio {{mvar|φ}}:

<math display=block>\varphi = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}}.</math>

The [[convergent (continued fraction)|convergents]] of the continued fraction for {{mvar|φ}} are ratios of successive Fibonacci numbers: {{math|1=''φ''<sub>''n''</sub> = ''F''<sub>''n''+1</sub> / ''F''<sub>''n''</sub>}} is the {{mvar|n}}-th convergent, and the {{math|(''n''&thinsp;+&thinsp;1)}}-st convergent can be found from the recurrence relation {{math|1=''φ''<sub>''n''+1</sub> = 1 + 1 / ''φ''<sub>''n''</sub>}}.<ref>{{Cite web |title=The Golden Ratio, Fibonacci Numbers and Continued Fractions. |url=https://nrich.maths.org/2737 |access-date=2024-03-22 |website=nrich.maths.org |language=en}}</ref> The matrix formed from successive convergents of any continued fraction has a determinant of +1 or −1.  The matrix representation gives the following closed-form expression for the Fibonacci numbers:

<math display=block>\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.</math>

For a given {{mvar|n}}, this matrix can be computed in {{math|''O''(log ''n'')}} arithmetic operations, using the [[exponentiation by squaring]] method.

Taking the determinant of both sides of this equation yields [[Cassini's identity]],
<math display=block>(-1)^n = F_{n+1}F_{n-1} - {F_n}^2.</math>

Moreover, since {{math|'''A'''<sup>''n''</sup>'''A'''<sup>''m''</sup> {{=}} '''A'''<sup>''n''+''m''</sup>}} for any [[square matrix]] {{math|'''A'''}}, the following [[identity (mathematics)|identities]] can be derived (they are obtained from two different coefficients of the [[matrix product]], and one may easily deduce the second one from the first one by changing {{mvar|n}} into {{math|''n'' + 1}}),
<math display=block>\begin{align}
 {F_m}{F_n} + {F_{m-1}}{F_{n-1}} &= F_{m+n-1}, \\[3mu]
 F_{m} F_{n+1} + F_{m-1} F_n &= F_{m+n} .
\end{align}</math>

In particular, with {{math|1=''m'' = ''n''}},
<math display=block>\begin{align}
 F_{2 n-1} &= {F_n}^2 + {F_{n-1}}^2 \\[6mu]
 F_{2 n\phantom{{}-1}}   &= (F_{n-1}+F_{n+1})F_n \\[3mu]
          &= (2 F_{n-1}+F_n)F_n \\[3mu]
          &= (2 F_{n+1}-F_n)F_n.
\end{align}</math>

These last two identities provide a way to compute Fibonacci numbers [[Recursion (computer science)|recursively]] in {{math|''O''(log ''n'')}} arithmetic operations. This matches the time for computing the {{mvar|n}}-th Fibonacci number from the closed-form matrix formula, but with fewer redundant steps if one avoids recomputing an already computed Fibonacci number (recursion with [[memoization]]).<ref>{{citation|title=In honour of Fibonacci|first=Edsger W.|last=Dijkstra|author-link=Edsger W. Dijkstra|year=1978|url=https://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF}}</ref>