Editing Fibonacci sequence (section)

== Relation to the golden ratio ==
{{main|Golden ratio}}

===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>

=== Computation by rounding ===
Since
<math display=inline>\left|\frac{\psi^{n}}{\sqrt 5}\right| < \frac{1}{2}</math> for all {{math|''n'' ≥ 0}}, the number {{math|''F''<sub>''n''</sub>}} is the closest [[integer]] to <math>\frac{\varphi^n}{\sqrt 5}</math>. Therefore, it can be found by [[rounding]], using the nearest integer function:
<math display=block>F_n=\left\lfloor\frac{\varphi^n}{\sqrt 5}\right\rceil,\ n \geq 0.</math>

In fact, the rounding error quickly becomes very small as {{mvar|n}} grows, being less than 0.1 for {{math|''n'' ≥ 4}}, and less than 0.01 for {{math|''n'' ≥ 8}}.  This formula is easily inverted to find an index of a Fibonacci number {{mvar|F}}:
<math display=block>n(F) = \left\lfloor  \log_\varphi \sqrt{5}F\right\rceil,\ F \geq 1.</math>

Instead using the [[floor function]] gives the largest index of a Fibonacci number that is not greater than {{mvar|F}}:
<math display=block>n_{\mathrm{largest}}(F) = \left\lfloor  \log_\varphi \sqrt{5}(F+1/2)\right\rfloor,\ F \geq 0,</math>
where <math>\log_\varphi(x) = \ln(x)/\ln(\varphi) = \log_{10}(x)/\log_{10}(\varphi)</math>, <math>\ln(\varphi) = 0.481211\ldots</math>,<ref>{{Cite OEIS|1=A002390|2=Decimal expansion of natural logarithm of golden ratio|mode=cs2}}</ref> and <math>\log_{10}(\varphi) = 0.208987\ldots</math>.<ref>{{Cite OEIS|1=A097348|2=Decimal expansion of arccsch(2)/log(10)|mode=cs2}}</ref>

=== Magnitude ===
Since ''F<sub>n</sub>'' is [[Asymptotic analysis|asymptotic]] to <math>\varphi^n/\sqrt5</math>, the number of digits in {{math|''F''<sub>''n''</sub>}} is asymptotic to <math>n\log_{10}\varphi\approx 0.2090\, n</math>. As a consequence, for every integer {{math|''d'' > 1}} there are either 4 or 5 Fibonacci numbers with {{mvar|d}} decimal digits.

More generally, in the [[radix|base]] {{mvar|b}} representation, the number of digits in {{math|''F''<sub>''n''</sub>}} is asymptotic to <math>n\log_b\varphi = \frac{n \log \varphi}{\log b}.</math>

=== Limit of consecutive quotients ===
[[Johannes Kepler]] observed that the ratio of consecutive Fibonacci numbers [[convergent sequence|converges]]. He wrote that "as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost", and concluded that these ratios approach the golden ratio <math>\varphi\colon </math> <ref>{{Citation|last=Kepler |first=Johannes |title=A New Year Gift: On Hexagonal Snow |year=1966 |isbn=978-0-19-858120-8 |publisher=Oxford University Press |page= 92}}</ref><ref>{{Citation | title = Strena seu de Nive Sexangula | year = 1611}}</ref>
<math display=block>\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi.</math>

This convergence holds regardless of the starting values <math>U_0</math> and <math>U_1</math>, unless <math>U_1 = -U_0/\varphi</math>. This can be verified using [[#Binet's formula|Binet's formula]]. For example, the initial values 3 and 2 generate the sequence 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ...&thinsp;. The ratio of consecutive elements in this sequence shows the same convergence towards the golden ratio.

In general, <math>\lim_{n\to\infty}\frac{F_{n+m}}{F_n}=\varphi^m
</math>, because the ratios between consecutive Fibonacci numbers approaches <math>\varphi</math>.

: [[File:Fibonacci tiling of the plane and approximation to Golden Ratio.gif|thumb|upright=2.2|left|Successive tilings of the plane and a graph of approximations to the golden ratio calculated by dividing each Fibonacci number by the previous]]
{{Clear}}

=== Decomposition of powers ===
Since the golden ratio satisfies the equation
<math display=block>\varphi^2 = \varphi + 1,</math>

this expression can be used to decompose higher powers <math>\varphi^n</math> as a linear function of lower powers, which in turn can be decomposed all the way down to a linear combination of <math>\varphi</math> and 1. The resulting [[recurrence relation]]ships yield Fibonacci numbers as the linear [[coefficient]]s:
<math display=block>\varphi^n = F_n\varphi + F_{n-1}.</math>
This equation can be [[Mathematical proof|proved]] by [[Mathematical induction|induction]] on {{math|''n'' ≥ 1}}:
<math display=block>\begin{align}
\varphi^{n+1} &= (F_n\varphi + F_{n-1})\varphi = F_n\varphi^2 + F_{n-1}\varphi \\
&= F_n(\varphi+1) + F_{n-1}\varphi = (F_n + F_{n-1})\varphi + F_n = F_{n+1}\varphi + F_n.
\end{align}</math>
For <math>\psi = -1/\varphi</math>, it is also the case that <math>\psi^2 = \psi + 1</math> and it is also the case that
<math display=block>\psi^n = F_n\psi + F_{n-1}.</math>

These expressions are also true for {{math|''n'' < 1}} if the Fibonacci sequence ''F<sub>n</sub>'' is [[Generalizations of Fibonacci numbers#Extension to negative integers|extended to negative integers]] using the Fibonacci rule <math>F_n = F_{n+2} - F_{n+1}.</math>

=== Identification ===
Binet's formula provides a proof that a positive integer {{mvar|x}} is a Fibonacci number [[if and only if]] at least one of <math>5x^2+4</math> or <math>5x^2-4</math> is a [[Square number|perfect square]].<ref>{{Citation | title = Fibonacci is a Square | last1 = Gessel | first1 = Ira | journal = [[The Fibonacci Quarterly]] | volume = 10 | issue = 4 | pages = 417–19 |date=October 1972 | url = https://www.fq.math.ca/Scanned/10-4/advanced10-4.pdf | access-date = April 11, 2012 }}</ref> This is because Binet's formula, which can be written as <math>F_n = (\varphi^n - (-1)^n \varphi^{-n}) / \sqrt{5}</math>, can be multiplied by <math>\sqrt{5} \varphi^n</math> and solved as a [[quadratic equation]] in <math>\varphi^n</math> via the [[quadratic formula]]:

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

Comparing this to <math>\varphi^n = F_n \varphi + F_{n-1} = (F_n\sqrt{5} + F_n + 2 F_{n-1})/2</math>, it follows that
: <math display=block>5{F_n}^2 + 4(-1)^n = (F_n + 2F_{n-1})^2\,.</math>
In particular, the left-hand side is a perfect square.