Fibonacci Sequence

The Fibonacci sequence is an integer sequence defined by a simple linear recurrence relation. The sequence appears in many settings in mathematics and in other sciences. In particular, the shape of many naturally occurring biological organisms is governed by the Fibonacci sequence and its close relative, the golden ratio.

The Fibonacci numbers appear as numbers of spirals in leaves and seedheads as well.

The Fibonacci numbers are the terms of a sequence of integers in which each term is the sum of the two previous terms with

\[\begin{array} &F_1 = F_2 = 1, &F_n = F_{n-1} + F_{n-2}.\end{array}\]

The first few terms are

\[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots.\]

Let \( \phi = \frac{1+\sqrt{5}}2 \) be the golden ratio. Let \( {\overline \phi} = \frac{-1}{\phi} = \frac{1-\sqrt{5}}2. \) Then

\[{ F }_{ n }= \frac { \phi^n-{\overline \phi}^n }{ \sqrt { 5 } } .\]

The formula (often called Binet's formula) comes from a general result for linear recurrence relations, but it can be proved directly by induction. Let \( G_n = \frac { \phi^n-{\overline \phi}^n }{ \sqrt { 5 } } \). The goal is to prove that \( F_n=G_n\) by induction on \(n \). The base cases are \( G_1 = G_2 = 1 \), which is clear. Now suppose \( G_k=F_k \) for all \( k<n\), where \( n \) is at least \( 3 \). Then

\[ \begin{align} F_n &= F_{n-1}+F_{n-2} \\&= G_{n-1}+G_{n-2} & \text{(inductive hypothesis)} \\ &= \frac1{\sqrt{5}} \Big(\phi^{n-1}-{\overline{\phi}}^{n-1}\Big)+\frac1{\sqrt{5}}\Big(\phi^{n-2}-{\overline{\phi}}^{n-2}\Big) \\ &= \frac1{\sqrt{5}} \Big(\phi^{n-1}+\phi^{n-2}-{\overline\phi}^{n-1}-{\overline\phi}^{n-2}\Big) \\ &= \frac1{\sqrt{5}} \Big(\phi^n-{\overline\phi}^n\Big) = G_n, \end{align} \]

where the last line comes from the fact that \( \phi\) and \(\overline\phi\) are the two roots of the equation \( x^2=x+1\). \(_\square\)

Note that for \( n \ge 1 \), the term \( \frac{{\overline\phi}^n}{\sqrt{5}} \) is small, certainly between \( -0.3 \) and \( 0.3\). So \( F_n \) is the nearest integer to \( \frac{\phi^n}{\sqrt{5}} \).

We have

\[\frac{\phi^{10}}{\sqrt{5}} = 55.0036\ldots, \quad \frac{\phi^{11}}{\sqrt{5}} = 88.9977\ldots,\]

so \( F_{10} = 55 \) and \( F_{11} = 89\).

The ratios of successive Fibonacci numbers should therefore be roughly

\[\displaystyle \phi =\lim _{ n\rightarrow \infty }{ \frac { { F }_{ n+1 } }{ { F }_{ n } } } = \frac{1+\sqrt5}{2}.\]

This can be proved easily using Binet's formula.

We have

\[ \begin{align} \frac{F_{n+1}}{F_n} &= \frac{\phi^{n+1}-{\overline{\phi}}^{n+1}}{\phi^n-{\overline{\phi}}^n} \\ &= \frac{\phi-\frac{{\overline{\phi}}^{n+1}}{\phi^n}}{1-\frac{{\overline{\phi}}^n}{\phi^n}}, \end{align} \]

and the terms \( \frac{{\overline{\phi}}^{n+1}}{\phi^n} \) and \( \frac{{\overline{\phi}}^n}{\phi^n} \) approach \( 0 \) as \( n \to \infty \), because the numerator approaches \( 0 \) and the denominator approaches \( \infty \).

Therefore, the limit is \( \frac{\phi}1 = \phi \). \(_\square\)

The Fibonacci sequence appears as the numerators and denominators of the convergents to the simple continued fraction

\[ [1,1,1,\ldots] = 1+\frac1{1+\frac1{1+\frac1{\ddots}}}. \]

This continued fraction equals \( \phi,\) since it satisfies \( x = 1+\frac1{x} \) (and it is greater than 1).

The \( n^\text{th}\) convergent to this continued fraction is \( \frac{F_{n+1}}{F_n} \), so this gives another proof that \( \lim\limits_{n\to\infty} \frac{F_{n+1}}{F_n} = \phi \).

Like the Catalan numbers, the Fibonacci numbers count many types of combinatorial objects. Here are four examples.

(1) \( F_n \) is the number of compositions of \( n-1 \) consisting of \( 1\)s and \( 2\)s. (A composition of \(n-1\) is an expression of \( n-1\) as a sum of parts, where the order of the parts matters.) For instance,

\[ \begin{align} 5 &= 1+1+1+1+1\\&=1+1+1+2\\&=1+1+2+1\\&=1+2+1+1\\&=2+1+1+1 \\&=1+2+2\\&=2+1+2\\&=2+2+1, \end{align} \]

so \( F_6 = 8. \)

(2) \( F_n \) is the number of ways to tile a \( 2\times (n-1)\) board with \( 1\times 2\) dominoes.

(3) \( F_n \) is the number of binary sequences of length \( n-2\) with no consecutive \( 0\)s.

(4) \( F_n \) is the number of subsets of \( \{ 1,2,\ldots,n-2\} \) that do not contain any pair of consecutive numbers.

To see that the Fibonacci numbers count these objects, let the number of objects equal \( G_n \) and show that \( G_n=G_{n-1}+G_{n-2}\). Then verify that \( F_1=G_1\) and \( F_2 = G_2 \), and the proof is complete.

For instance, to prove (4), start with \( G_1=1, G_2 =1, G_3= 2, G_4 = 3 \), and then suppose \( S \) is a subset of \( \{1,2,\ldots,n-2\}\) without any consecutive numbers in it. There are \( G_{n-1} \) such sets \( S\) that don't contain \( n-2 \). If \( S \) contains \( n-2\), then it doesn't contain \( n-3\), so \( S \) is obtained by taking a subset of \( \{1,2,\ldots,n-4\} \) and throwing in \( n-2\). So there are \( G_{n-2}\) such sets \( S\). This proves that \( G_n = G_{n-1}+G_{n-2},\) as desired.

There are quite a few identities relating different Fibonacci numbers. For instance,

\[ F_n^2-F_{n-1}F_{n+1} = (-1)^{n+1}, \]

which has the useful corollary that consecutive Fibonacci numbers are coprime.

As is typical, the most down-to-earth proof of this identity is via induction. It is clear for \( n = 2,3 \), and now suppose that it is true for \( n \). Then

\[ \begin{align} F_{n+1}^2-F_nF_{n+2} &= F_{n+1}^2-F_n(F_n+F_{n+1})\\ &= F_{n+1}(F_{n+1}-F_n) - F_n^2 \\ &= F_{n+1}F_{n-1}-F_n^2 \\ &= -(-1)^{n+1} = (-1)^{n+2}, \end{align} \]

so it is true for \( n+1\). \(_\square\)

The proofs of the rest of these identities are similar.

(1) \( F_mF_n + F_{m-1}F_{n-1} = F_{m+n-1}\)

• (1a) \( F_{2n-1}=F_{n-1}^2+F_n^2 \)
• (1b) \( F_{2n} = F_n(F_{n-1}+F_{n+1}) \)

(2) \( F_1+F_2+F_3+\cdots+F_n = F_{n+2}-1 \)
(3) \( F_1+F_3+F_5+\cdots+F_{2n-1} = F_{2n} \) and \( F_2+F_4+F_6+\cdots+F_{2n}=F_{2n+1}-1 \)
(4) \( F_{n+1} = \sum\limits_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} \)

The generating function of the Fibonacci numbers is

\[ \sum_{n=1}^\infty F_n x^n = \frac{x}{1-x-x^2}. \]

This follows from the expansion:

\[\begin{align} \big(1-x-x^2\big)\big(F_1x + F_2x^2 + F_3x^3 + \cdots\big) &= F_1x + (F_2-F_1)x^2+(F_3-F_2-F_1)x^3+(F_4-F_3-F_2)x^4+ \cdots \\ &= x+0x^2+\sum_{k=3}^\infty (F_k-F_{k-1}-F_{k-2})x^k \\ &= x.\ _\square \end{align}\]

Identity (1) above can be used to show that if \( a|b \), then \( F_a|F_b\). In fact, more is true:

\[ \text{gcd}(F_a,F_b) = F_{\text{gcd}(a,b)}. \]

This follows from (1) and a process similar to the Euclidean algorithm; write \( a = bq+r, \, 0 \le r < b, \) and then

\[ \begin{align} \text{gcd}(F_a,F_b) &= \text{gcd}(F_{bq+r},F_b) \\ &= \text{gcd}(F_{bq}F_{r+1}+F_{bq-1}F_r,F_b) \\ &= \text{gcd}(F_{bq-1}F_r,F_b) &&\qquad (\text{because } F_b|F_{bq}) \\ &= \text{gcd}(F_r,F_b), &&\qquad \big(\text{because gcd} (F_{bq-1},F_{bq})=1\big) \end{align} \]

and so on.

We have \( \text{gcd}(F_{10},F_{15}) = \text{gcd}(55,610)=5=F_5. \)

Note that this discussion implies that if \( F_p \) is prime, then \( p \) is prime or \( p =4 \). The converse is not true \((F_2 = 1, F_{19} = 37 \cdot 113), \) and in fact it is not known whether there are infinitely many primes \( p \) such that \( F_p \) is prime.

A Zeckendorf representation of a positive integer is an expression of the integer as a sum of (at least one) distinct non-consecutive Fibonacci numbers. For instance, \( 41 = 34+5+2 \) is a Zeckendorf representation of \( 41 \).

Every positive integer has exactly one Zeckendorf representation.

To show first that there cannot be more than one representation, use the identities in item (3) above to see that the sum of any non-consecutive Fibonacci numbers of which the largest is \( F_n \) cannot be larger than \( F_{n+1} \) \((\)note that \( F_1 \) and \( F_3 \) are consecutive Fibonacci numbers since \( F_1 = F_2). \) Then suppose that there are two Zeckendorf representations of an integer, and subtract out all the common Fibonacci numbers in the two sums. Then the resulting two sums are still equal, and consist of two disjointed sets of Fibonacci numbers. Suppose the largest Fibonacci number in the first sum is \( F_a \) and the largest Fibonacci number in the second sum is \(F_b\); suppose without loss of generality that \( a < b \). Then the first sum is less than \( F_{a+1} \) but the second sum is clearly \( \ge F_b \), so they cannot be equal.

To see that a Zeckendorf representation always exists, proceed by induction. The base case is clear \((1=1,2=2),\) and now suppose the result holds for all \( k < n \). Let \( F_a \) be the largest Fibonacci number less than or equal to \( n \). If \( F_a = n,\) then that is a Zeckendorf representation, so suppose \( F_a < n \). Then \( n-F_a \) has a Zeckendorf representation \( F_{b_1}+F_{b_2} + \cdots + F_{b_k} \) by the inductive hypothesis, so \( n =F_a + F_{b_1}+F_{b_2}+\cdots+F_{b_k} \). The \( b_i \) are non-consecutive, and furthermore all of the \( b_i \) are less than \( a-1, \) because if \( n-F_a \ge F_{a-1}, \) then \( n \ge F_a + F_{a-1} = F_{a+1}, \) which contradicts the minimality of \( a \). So this is a Zeckendorf representation. \(_\square\)

The proof implies that the Zeckendorf representation can be found by always taking the largest Fibonacci number less than \( n,\) subtracting it out, and repeating the process.

This theorem has applications in coding theory.