Fascinating Fibonaccis

The Fibonacci sequence is a sequence that starts with two ones and each term after the two ones is obtained by adding the two preceding terms: f_n: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...... The explicit formula for the nth term of the Fibonacci sequence is:

\[ f_n = \dfrac{1}{\sqrt{5}}\left[ \left( \dfrac{1+\sqrt{5}}{2} \right)^n - \left( \dfrac{1-\sqrt{5}}{2} \right)^n \right] \]

PROOF: Let \(\phi = \dfrac{1+\sqrt{5}}{2} \) (the Golden Ratio) and \( -\dfrac{1}{\phi} = \dfrac{1-\sqrt{5}}{2} \) (the negative inverse of the Golden Ratio). Then \(\phi^2 = \dfrac{3+\sqrt{5}}{2} \) or \( 1+ \phi\). And \( \left(-\dfrac{1}{\phi}\right)^2 = \dfrac{3-\sqrt{5}}{2} = 1 - \dfrac{1}{\phi} \).

Since the Golden Ratio φ and its conjugate are the roots of the equation \(x^2= x+1 \), the result above is not unexpected. The following sequences emerge from the powers of φ and 1/φ:

Powers of φ	Powers of –1/φ
\(\phi\)	\(-\dfrac{1}{\phi}\)
\(\phi^2 = 1 + \phi\)	\(\left(-\dfrac{1}{\phi}\right)^2 = 1 - \dfrac{1}{\phi}\)
\(\phi^3 = \phi(1+\phi) = \phi + \phi^2 = 1 + 2\phi\)	\(\left(-\dfrac{1}{\phi}\right)^3 = -\dfrac{1}{\phi}\left(1-\dfrac{1}{\phi}\right) = -\dfrac{1}{\phi}+\dfrac{1}{\phi^2} = 1- \dfrac{2}{\phi}\)
\(\phi^4 = \phi(1+2\phi) = 2 + 3\phi \)	\(\left(-\dfrac{1}{\phi}\right)^4 = -\dfrac{1}{\phi}\left(1-\dfrac{2}{\phi}\right) =2 -\dfrac{3}{\phi}\)
\(\phi^5 = \phi(2+3\phi) = 3 + 5\phi \)	\(\left(-\dfrac{1}{\phi}\right)^5 = -\dfrac{1}{\phi}\left(2-\dfrac{3}{\phi}\right) = 3 -\dfrac{5}{\phi}\)
....	....
\( \phi^n = f_{n-1} + f_{n}\phi \)	\( \left(-\dfrac{1}{\phi}\right)^n = f_{n-1} - f_{n}\cdot\dfrac{1}{\phi} \)

Using mathematical induction we can prove \( \phi^n = f_{n-1} + f_{n}\phi \). We have already proved \( \phi^n = f_{n-1} + f_{n}\phi \) works for 1 ≤ n ≤ 5 because the Fibonacci numbers appear in the powers of φ. We only need to prove \( \phi^n = f_{n-1} + f_{n}\phi \) works for n + 1.

(i) \( \phi^{n+1} = \phi\cdot\phi^n = \phi(f_{n-1} + f_n\phi) = \) \( f_{n-1}\phi + f_n\phi^2 = f_{n-1}\phi + f_n(1 + \phi) = \) \(f_{n-1}\phi + f_n + f_n\phi = f_n + (f_{n-1} + f_n)\phi \)

But, since \( f_n = f_{n-1} + f_{n-2} \) according to the definition of the Fibonacci sequence, we can also write that as \( f_{n+1} = f_{n} + f_{n-1} \). Therefore,

(ii) \( \phi^{n+1} = f_n + (f_{n-1} + f_n)\phi = f_n + f_{n+1}\phi \)

Using the same reasoning for –1/φ, it can be proved that: \( \left(-\dfrac{1}{\phi}\right)^{n+1} = f_{n} + f_{n+1}\cdot\dfrac{1}{\phi}\) by mathematical induction.

Now, f_n, the nth term of the Fibonacci sequence, can be written as \( \frac{1}{\sqrt{5}}f_n\sqrt{5}\). We can show that \( \phi - \dfrac{1}{\phi} = \sqrt{5} \), and making the substitution, we have:

(iv) \( f_n = \dfrac{1}{\sqrt{5}}f_n\left(\phi - \dfrac{1}{\phi} \right) = \dfrac{1}{\sqrt{5}}\left(f_n\phi - f_n\cdot\dfrac{1}{\phi} \right) \)

Now adding and subtracting f_n–1 we have:

(v) \( f_n = \dfrac{1}{\sqrt{5}}\left( f_{n-1} + f_n\phi - f_{n-1} - f_n\cdot\dfrac{1}{\phi} \right) = \dfrac{1}{\sqrt{5}}\left[ (f_{n-1} + f_n\phi) - \left(f_{n-1} + f_n\cdot\dfrac{1}{\phi}\right) \right] \)

(iv) \( f_n = \dfrac{1}{\sqrt{5}}\left[ \phi^n - \left(-\dfrac{1}{\phi}\right)^n \right] \) or \( f_n = \dfrac{1}{\sqrt{5}}\left[ \left( \dfrac{1+\sqrt{5}}{2} \right)^n - \left( \dfrac{1-\sqrt{5}}{2} \right)^n \right] \)

The Ratio Limit

The division of two large consecutive Fibonacci numbers approximates the Golden Ratio or its reciprocal; therefore, the limit of dividing two consecutive Fibonacci numbers is the Golden Ratio or its reciprocal.

\[\lim_{n \to \infty } \frac{f_{n+1}}{f_n} = \phi \] and \[\lim_{ \to \infty } \frac{f_{n}}{f_{n+1}} = \frac{1}{\phi} \]

PROOF

Let \(\displaystyle x = \lim_{n \to \infty } \frac{f_{n+1}}{f_n} = \phi \). Then,

(i) \(\displaystyle x = \lim_{n \to \infty } \frac{f_n + f_{n-1}}{f_n} \)

(ii) \(\displaystyle x = 1 + \lim_{n \to \infty } \frac{f_{n-1}}{f_n} \)

Since \(\displaystyle \lim_{n \to \infty } f(n)^{-1} = \left[ \lim_{n \to \infty } f(n) \right]^{-1} \), we can also state the following: \(\displaystyle \lim_{n \to \infty } \frac{f_{n-1}}{f_n} = \left[ \lim_{n \to \infty } \frac{f_{n+1}}{f_n} \right]^{-1} \). Since \(\displaystyle x = \lim_{n \to \infty } \frac{f_{n+1}}{f_n} \), it follows that \(\displaystyle \left[ \lim_{n \to \infty } \frac{f_{n+1}}{f_n} \right]^{-1} = \frac{1}{x} \). Substitution yields:

(iii) \(x = 1 + \dfrac{1}{x} \)

And the solutions of equation (iii) are φ and –1/φ. Since –1/φ is negative, φ is the only solution. The same reasoning can be applied to prove \(\displaystyle \lim_{n \to \infty } \frac{f_{n}}{f_{n+1}} = \frac{1}{\phi} \).

Mirror Fibonacci Numbers

The powers of φ and –1/φ work for all integral exponents n greater than or equal to 1. But, if we can define the nth Fibonacci number for negative values of n, we can extend the powers of φ and –1/φ for negative integral exponents. According to the definition of the Fibonacci sequence, \(f_{n+2} = f_{n+1} + f_n\). Solving for f_n we have \( f_n = f_{n+2} - f_{n+1} \). Thus, we can use this formula to find f_n for negative values of n or the Mirror Fibonacci sequence.

f₀ = f₂ – f₁ = 1 – 1 = 0

f_–1 = f₁ – f₀ = 1 – 0 = 1

f_–2 = f₀ – f_–1 = 0 – 1 = –1

f_–3 = f_–1 – f_–2 = 1 – (–1) = 2

f_–4 = f_–2 – f_–3 = –1 – 2 = –3

f_–5 = f_–3 – f_–4 = 2 – (–3) = 5

f_–6 = f_–4 – f_–5 = –3 – 5 = –8

f_–7 = f_–5 – f_–6 = 5 – (–8) = 13..........

Thus, the Fibonacci sequence for negative values of n is the Fibonacci sequence of positive values of n with alternating signs. We can see that f_–n = f_n for odd values of n and f_–n = –f_n for even values of n. Using this Mirror Fibonacci sequence we can find \(\phi^{-n}\) and \(\left(-\frac{1}{\phi}\right)^{-n}\).

FIBONACCI PATTERNS

Patterns occurring in the Fibonacci can be proven by mathematical induction.

(1) \(f_n^2 + f_{n+1}^2 = f_{2n+1} \)

(2) \(f_n^2 - f_{n-2}^2 = f_{2n-2} \)

(3) \(\sum_{i=1}^{n}f_i = f_{n+2} - 1 \)

(4) \(f_n^2 - 1 = f_{n+1}\cdot f_{n-1} \)

(5) \(f_n^2 - f_{n-1}^2 = f_{n+1}\cdot f_{n-2} \)

(6) \(\sum_{i=1}^{n}f_i^2 = f_n\cdot f_{n+1} \)

The sum of 10 consecutive Fibonacci numbers is always evenly divisible by 11:

(7) \(\displaystyle \frac{f_n + f_{n+1} + f_{n+2} + f_{n+3} + f_{n+4} + f_{n+5} + f_{n+6} + f_{n+7} + f_{n+8} + f_{n+9}}{11} = f_{n+6} \)

Every 3rd Fibonacci number is divisible by 2.

Every 4th Fibonacci number is divisible by 3.

Every 5th Fibonacci number is divisible by 5.

Every 6th Fibonacci number is divisible by 8.

Every 7th Fibonacci number is divisible by 13.

Every 8th Fibonacci number is divisible by 21.

Every nth Fibonacci number is divisible by f_n.

Generalized Fibonacci Sequence

The Fibonacci Sequence begins with two 1’s. We can generalize the sequence by beginning the sequence with arbitrary numbers, a₀ and a₁. Therefore, the general sequence is:

F_n = {a₀, a₁, a₀ + a₁, a₀ + 2a₁, 2a₀ + 3a₁, 3a₀ + 5a₁, 5a₀ + 8a₁, 8a₀ + 13a₁, …..}

We see the Fibonacci sequence appearing again in the general sequence. Therefore, we can express F_n as \(F_n = a_0 f_{n-2} + a_1 f_{n-1} \).

Just as the ratio of two consecutive Fibonacci numbers approaches a limit at infinity, the ratio of two consecutive general Fibonacci numbers approaches a limit. More amazing is that the limit is φ and independent of a₀ and a₁. The proof is quite simple.

(i) \(\displaystyle \lim_{n \to \infty } \frac{F_{n+1}}{F_n} = \lim_{n \to \infty } \frac{a_0 f_{n-1} + a_1 f_n}{a_0 f_{n-2} + a_1 f_{n-1}} \)

We divide both the numerator and denominator by \( \frac{1}{f_{n-1}}\) in (i).

(ii) \(\displaystyle \lim_{n \to \infty } \frac{a_0 + a_1\cdot\frac{f_n}{f_{n-1}}}{a_0\cdot\frac{f_{n-2}}{f_{n-1}} + a_1} = \frac{a_0 + a_1\phi}{a_0\cdot\frac{1}{\phi} + a_1} = \frac{a_0\phi + a_1\phi^2}{a_0+ a_1\phi} = \phi \)