Editing Fibonacci sequence (section)

===Closed-form expression <span class="anchor" id="Binet's formula"></span>===
Like every [[sequence]] defined by a homogeneous [[linear recurrence with constant coefficients]], the Fibonacci numbers have a [[closed-form expression]].<ref>{{cite book |title=Discrete Mathematics with Ducks |first=sarah-marie|last=belcastro|author-link=Sarah-Marie Belcastro |edition=2nd |publisher=CRC Press |year=2018 |isbn=978-1-351-68369-2 |page=260 |url=https://books.google.com/books?id=xoqADwAAQBAJ}} [https://books.google.com/books?id=xoqADwAAQBAJ&pg=PA260 Extract of page 260]</ref> It has become known as '''Binet's formula''', named after French mathematician [[Jacques Philippe Marie Binet]], though it was already known by [[Abraham de Moivre]] and [[Daniel Bernoulli]]:<ref>{{citation | last1 = Beutelspacher | first1 = Albrecht | last2 = Petri | first2 = Bernhard | contribution = Fibonacci-Zahlen | doi = 10.1007/978-3-322-85165-9_6 | pages = 87–98 | publisher = Vieweg+Teubner Verlag | title = Der Goldene Schnitt | series = Einblick in die Wissenschaft | year = 1996| isbn = 978-3-8154-2511-4 }}</ref>

<math display=block>
F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5},
</math>

where

<math display=block>
\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\ldots
</math>

is the [[golden ratio]], and <math>\psi</math> is its [[Conjugate (square roots)|conjugate]]:{{Sfn | Ball | 2003 | p = 156}}

<math display=block>
\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\ldots.
</math>

Since <math>\psi = -\varphi^{-1}</math>, this formula can also be written as

<math display=block>
F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt 5} = \frac{\varphi^n - (-\varphi)^{-n}}{2\varphi - 1}.
</math>

To see the relation between the sequence and these constants,{{Sfn | Ball | 2003 | pp = 155–156}} note that <math>\varphi</math> and <math>\psi</math> are both solutions of the equation <math display=inline>x^2 = x + 1</math> and thus <math>x^n = x^{n-1} + x^{n-2},</math> so the powers of <math>\varphi</math> and <math>\psi</math> satisfy the Fibonacci recursion. In other words,

<math display=block>\begin{align}
\varphi^n &= \varphi^{n-1} + \varphi^{n-2}, \\[3mu]
\psi^n &= \psi^{n-1} + \psi^{n-2}.
\end{align}</math>

It follows that for any values {{mvar|a}} and {{mvar|b}}, the sequence defined by

<math display=block>U_n=a \varphi^n + b \psi^n</math>

satisfies the same recurrence,

<math display=block>\begin{align}
U_n &= a\varphi^n +  b\psi^n \\[3mu]
&= a(\varphi^{n-1} + \varphi^{n-2}) +  b(\psi^{n-1} + \psi^{n-2}) \\[3mu]
&= a\varphi^{n-1} + b\psi^{n-1} + a\varphi^{n-2} + b\psi^{n-2} \\[3mu]
&= U_{n-1} + U_{n-2}.
\end{align}</math>

If {{mvar|a}} and {{mvar|b}} are chosen so that {{math|1=''U''<sub>0</sub> = 0}} and {{math|1=''U''<sub>1</sub> = 1}} then the resulting sequence {{math|''U''<sub>''n''</sub>}} must be the Fibonacci sequence. This is the same as requiring {{mvar|a}} and {{mvar|b}} satisfy the system of equations:

<math display=block>
\left\{\begin{align} a + b &= 0 \\ \varphi a + \psi b &= 1\end{align}\right.
</math>

which has solution

<math display=block>
a = \frac{1}{\varphi-\psi} = \frac{1}{\sqrt 5},\quad  b = -a,
</math>

producing the required formula.

Taking the starting values {{math|''U''<sub>0</sub>}} and {{math|''U''<sub>1</sub>}} to be arbitrary constants, a more general solution is:

<math display=block> U_n = a\varphi^n + b\psi^n </math>

where

<math display=block>\begin{align}
a&=\frac{U_1-U_0\psi}{\sqrt 5}, \\[3mu]
b&=\frac{U_0\varphi-U_1}{\sqrt 5}.
\end{align}</math>