Fibonacci

Fibonacci#

Fibonacci Sequence#

\( F := \begin{cases} F_0 &= 0 \\ F_1 &= 1 \\ F_{n + 1} &= F_n + F_{n - 1} && n \in \{ 2, 3, \dots \} \\ \end{cases} \)

Claim: if \(m\) divides two consecutive Fibonacci numbers it is \(1\)#

Claim

If \(m\) divides both \(F_n\) and \(F_{n+1}\) then \(m = 1\).

\( \boxed{ \forall m \in \mathbb{Z} \quad m \mid F_n \land m \mid F_{n+1} \quad \implies \quad m = 1 } \)

Proof by induction on \(n\)

It suffices to show that

\( \begin{aligned} & P(1) \quad \land \quad \forall k \ge 2 \quad \left( \bigwedge_{i=1}^{k-1} P(i) \right) \implies P(k) \\ & \text{where} \quad P(i) : \quad m \mid F_i \land m \mid F_{i+1} \implies m = 1 \\ \end {aligned} \)

Base Case

Suppose \(m \mid F_1\) and \(m \mid F_2\) which are both \(1\). Then there is an integer \(k\) such that

\( m \mid 1 \iff mk = 1 \implies m = \pm 1 \\ \)

Induction Step

We want to show that

\( \begin{aligned} \forall k \ge 2 \quad \left( \bigwedge_{i=1}^{k-1} P(i) \right) \implies P(k) \\ \end {aligned} \)

Induction Hypothesis

\( \begin{aligned} \exists k \ge 2 \quad \left( \bigwedge_{i=1}^{k-1} P(i) \right) \\ \end {aligned} \)

Thus we assume that

\(P(k-1) : \quad m \mid F_{k-1} \land m \mid F_k \implies m = 1\)

Suppose \(m \mid F_k\) and \(m \mid F_{k+1}\). Then there are integers \(s\) and \(t\) such that \(ms = F_k\) and

\(mt = F_{k+1} = F_k + F_{k-1} = ms + F_{k-1}\)

\(F_{k-1} = mt - ms = m(t - s) \iff m \mid F_{k-1}\)

Thus \(m = 1\).

\(\blacksquare\)

Golden Ratio#

Two quantities \(a\) and \(b\) with \(a \gt b \gt 0\) are in the golden ratio if their ratio is the same as the ratio of their sum \(a + b\) to the larger of the two quantities \(a\).

\( \begin{aligned} \frac{a + b}{a} = \frac{a}{b} = \varphi \end {aligned} \)

where the constant \(\varphi\) denotes the golden ratio. Suppose \(b = 1\). Then

\( \begin{aligned} \frac{a + 1}{a} = a = \varphi \quad \implies \quad \frac{\varphi + 1}{\varphi} = \varphi \quad \iff \quad \varphi^2 = \varphi + 1 \end {aligned} \)

Thus the constant \(\varphi\) satisfies the quadratic equation

\( \begin{aligned} x^2 = x + 1 \quad \iff \quad x^2 - x - 1 = 0 \quad \iff \quad x = \frac{1 \pm \sqrt{5}}{2} = \frac{-\underset{(-1)}{b} \pm \sqrt{\underset{(-1)}{b^2} - 4 \underset{(\phantom{-}1)}{a} \underset{(-1)}{c}}}{2 \underset{(\phantom{-}1)}{a}} \end {aligned} \)

and is an irrational number with a value of

\( \begin{aligned} && \varphi &= \frac{1 + \sqrt{5}}{2} = \phantom{-} 1.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ -\varphi^{-1} &= -\frac{2}{1 + \sqrt{5}} = -\frac{2 (1 - \sqrt{5})}{(1 + \sqrt{5})(1 - \sqrt{5})} = & \psi &= \frac{1 - \sqrt{5}}{2} = -0.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ \end {aligned} \)

Thus the golden ratio \(\varphi\) and its negative reciprocal \(\psi = -\varphi^{-1}\) are the roots of the quadratic equation \(x^2 - x - 1 = 0\).

(It is also the case that \(-\varphi\) and \(\varphi^{-1}\) are the roots of the quadratic equation \(x^2 + x - 1 = 0\).)

\( \begin{aligned} \varphi + \psi = \varphi - \frac{1}{\varphi} &= \frac{1 \textcolor{#0096FF}{+ \sqrt{5}}}{2} + \frac{\phantom{-} 1 \textcolor{#0096FF}{- \sqrt{5}}}{2} =& 1 \\ \varphi - \psi = \varphi + \frac{1}{\varphi} &= \frac{\textcolor{#0096FF}{1} + \sqrt{5}}{2} + \frac{\textcolor{#0096FF}{-1} + \sqrt{5}}{2} =& \sqrt{5} \\ \end {aligned} \)

Thus

\( \begin{aligned} -\frac{1}{\varphi} &= 1 - \varphi & \quad \iff \quad \frac{1}{\varphi} &= \varphi - 1 \quad \iff \quad & \varphi &= 1 + \frac{1}{\varphi} & \quad \iff \quad \varphi^2 = \varphi + 1 \\ \phantom{-} \psi &= 1 + \frac{1}{\psi} & \quad \iff \quad \frac{1}{\psi} &= \psi - 1 \quad \iff \quad & -\frac{1}{\psi} &= 1 - \psi & \quad \iff \quad \psi^2 = \psi + 1 \end {aligned} \)

That is

\( \begin{aligned} & \varphi^{-1} &&= \varphi - 1 &&= 0.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ & \varphi^0 && &&= 1 \\ \hline & \varphi &&= \varphi^0 + \varphi^{-1} &&= 1.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ & \varphi^2 &&= \varphi^{\phantom{0}} + \varphi^0 &&= 2.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ & \vdots \\ & \varphi^n &&= \varphi^{n-1} + \varphi^{n-2} \\ \end {aligned} \)

and

\( \begin{aligned} & \psi^{-1} &&= \psi - 1 &&= -1.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ & \psi^0 && &&= \phantom{-} 1 \\ \hline & \psi &&= \psi^0 + \psi^{-1} &&= -0.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ & \psi^2 &&= \psi^{\phantom{0}} + \psi^0 && \\ & \vdots \\ & \psi^n &&= \psi^{n-1} + \psi^{n-2} \\ \end {aligned} \)

Binet’s Formula#

\( \begin{aligned} F_n = a \varphi^n + b \psi^n \end {aligned} \)

for some constants \(a\) and \(b\).

\( \begin{aligned} F_0 &= a \phantom{\varphi} + b \phantom{\psi} = 0 \quad \iff \quad a = -b \\ F_1 &= a \varphi + b \psi = 1 \quad \iff \quad a = \frac{1}{\varphi - \psi} \\ \end {aligned} \)

Thus

\( \boxed{ \begin{aligned} F_n = \frac{\varphi^n - \psi^n}{\varphi - \psi} = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}} \end {aligned} } \)

\( \begin{aligned} F_n &= (\varphi^n - \psi^n)/\sqrt{5} \\ \hline F_0 &= (\varphi^0 - \psi^0)/\sqrt{5} &&= 0 \\ F_1 &= \underbrace{(\varphi\phantom{^1} - \psi\phantom{^1})}_{\sqrt{5}}/\sqrt{5} &&= 1 \\ F_2 &= (\varphi^2 - \psi^2)/\sqrt{5} \\ &= (\varphi + 1 - \psi - 1)/\sqrt{5} \\ &= \underbrace{(\varphi - \psi)/\sqrt{5}}_{F_1} + \underbrace{(1 - 1)/\sqrt{5}}_{F_0} &&= 1 \\ F_3 &= (\varphi^3 - \psi^3)/\sqrt{5} \\ &= ((\varphi + 1) \varphi - (\psi + 1) \psi)/\sqrt{5} \\ &= (\varphi^2 + \varphi - \psi^2 - \psi)/\sqrt{5} \\ &= \underbrace{(\varphi^2 - \psi^2)/\sqrt{5}}_{F_2} + \underbrace{(\varphi - \psi)/\sqrt{5}}_{F_1} &&= 2 \\ F_4 &= (\varphi^4 - \psi^4)/\sqrt{5} \\ &= ((\varphi + 1) \varphi^2 - (\psi + 1) \psi^2)/\sqrt{5} \\ &= (\varphi^3 + \varphi^2 - \psi^3 - \psi^2)/\sqrt{5} \\ &= \underbrace{(\varphi^3 - \psi^3)/\sqrt{5}}_{F_3} + \underbrace{(\varphi^2 - \psi^2)/\sqrt{5}}_{F_2} &&= 3 \\ \end {aligned} \)

\( \begin{aligned} F_n + F_{n-1} \\ \frac{\varphi^n - \psi^n}{\sqrt{5}} + \frac{\varphi^{n-1} - \psi^{n-1}}{\sqrt{5}} \\ \frac{(\varphi^n + \varphi^{n-1}) - (\psi^n + \psi^{n-1})}{\sqrt{5}} \\ \frac{(\varphi + 1) \varphi^{n-1} - (\psi + 1) \psi^{n-1}}{\sqrt{5}} \\ \frac{\varphi^2 \varphi^{n-1} - \psi^2 \psi^{n-1}}{\sqrt{5}} \\ \frac{\varphi^{n+1} - \psi^{n+1}}{\sqrt{5}} \\ F_{n+1} \end {aligned} \)

\( \begin{aligned} F_n &= \frac{\varphi^n - \psi^n}{\sqrt{5}} \\ \varphi^n &= F_n (\varphi - \psi) + \psi^n && \varphi - \psi = \sqrt{5} \\ &= F_n \varphi + \psi^n - F_n \psi \\ &= F_n \varphi + \psi^n - \psi \left( \frac{\varphi^n - \psi^n}{\sqrt{5}} \right) \\ &= F_n \varphi + \frac{\psi^n \sqrt{5} - \psi (\varphi^n - \psi^n)}{\sqrt{5}} \\ &= F_n \varphi + \frac{\psi^n (\varphi - \psi) - \varphi^n \psi + \psi^{n+1}}{\sqrt{5}} \\ &= F_n \varphi + \frac{\varphi \psi^n - \psi^{n+1} - \varphi^n \psi + \psi^{n+1}}{\sqrt{5}} \\ &= F_n \varphi + \frac{\varphi \psi^n - \varphi^n \psi}{\sqrt{5}} \\ &= F_n \varphi + \frac{\varphi \psi (\psi^{n-1} - \varphi^{n-1})}{\sqrt{5}} && \varphi \psi = -1 \\ &= F_n \varphi + \frac{\varphi^{n-1} - \psi^{n-1}}{\sqrt{5}} \\ &= F_n \varphi + F_{n-1} \\ \end {aligned} \)

Thus

\( \boxed{ \begin{aligned} \varphi^n = F_n \varphi + F_{n-1} \end {aligned} } \)

https://www.youtube.com/watch?v=MQPo2iaP6v4

Figures#

  • [ w ] 1786-1856 Binet, Jacques

  • [ w ] 1842-1891 Lucas, Édouard

Terms#

  • [ w ] Binet’s Formula

  • [ w ] Fibbinary Number

  • [ w ] Fibonacci Coding

  • [ w ] Fibonacci Cube

  • [ w ] Fibonacci Sequence

  • [ w ] Golden Ratio

  • [ w ] Linear Recurrence with Constant Coefficients

  • [ w ] Lucas Number

  • [ w ] Lucas Sequence

Contents