The Combinatorial Derivation of the Fibonacci Sequence

Recall from The Fibonacci Sequence page that the Fibonacci sequence $\{ f_n \}$ is defined to be the infinite sequence recursively defined by $f_1 = 1$, $f_2 = 1$, and for $n \geq 3$ we have that:

(1)

\begin{align} \quad f_n = f_{n-1} + f_{n-2} \end{align}

By itself, the statement of the Fibonacci sequence does not show the elegance of the sequence. We will now derive this famous sequence in terms of compositions which we define below.

Definition: A Composition of the positive integer $n$ is an ordered sum using at least one positive integer.

For example, consider the number $n = 3$. The compositions of $n = 3$ are $1 + 1 + 1 = 3$, $1 + 2 = 3$, $2 + 1 = 3$, and $3 = 3$ - that is, there are precisely $4$ compositions of $n = 3$.

Now suppose for each positive integer $n$ that we only want to consider the compositions of $n$ whose summands are either $1$ or $2$. Let $f_n$ be the number of these composiions.

For $n = 1$ there is only $f_1 = 1$ such composition, namely $1 = 1$.

For $n = 2$ there are $f_2 = 2$ compositions of this form: $1 +1 = 2$ and $2 = 2$.

For $n = 3$ we have that there are $f_3 = 3$ compositions of this form: $1 + 1 + 1 = 3$, $1 + 2 = 3$, and $2 + 1 = 3$.

For $n = 4$ we have that there are $f_4 = 5$ compositions of this form: $1 + 1 + 1 + 1 = 4$, $1 + 1 + 2 = 4$, $1 + 2 + 1 = 4$, $2 + 1 + 1 = 4$, and $2 + 2 = 4$.

As you might have already noticed - it appears that $f_n$ generates the Fibonacci sequence, that is we might suspect that for $n \geq 3$ that:

(2)

\begin{align} \quad f_n = f_{n-1} + f_{n-2} \end{align}

We will give a combinatorial proof of this equality.

Theorem 1: Let $n$ be a positive integer and let $f_n$ be equal to the number of compositions of $n$ whose summands are either $1$ or $2$. Then for each $n \geq$, $f_n = f_{n-1} + f_{n-2}$.

• Proof: Let $n \geq$ be a positive integer and let $f_n$ be the number of compositions whose summands are either $1$s or $2$s.

• Consider the ordered sum $1 + x = n$. We must therefore have $x = n - 1$. We know that there are precisely $f_{n-1}$ compositions summands of $1$s or $2$s so there must be $f_{n-1}$ ordered summands of $1$s or $2$s that start with $1$.

• Now consider the ordered sum $2 + x = n$. We must therefore have $x = n - 2$. We know that there are precisely $f_{n-2}$ compositions whose summands of $1$s or $2$s so there must be $f_{n-2}$ ordered summands of $1$s or $2$s that start with $2$.

• Since we restrict the ordered sums of $n$ to start with either $1$s or $2$s then we see that we have considered all cases for the number of compositions of $n$ whose summands are $1$s or $2$s and neither of the two cases share any compositions of $n$ of this form in common. Therefore:

(3)

\begin{align} \quad f_n = f_{n-1} + f_{n-2} \quad \blacksquare \end{align}

Note that in the proof above, we do no consider the ordered sums $x + 1 = n$ because then the composition of $x = n - 1$ starts with either $1$ or $2$ and we will be either over counting in the first case or over counting in the second case. The same reasoning holds for not considering the ordered sums $x + 2 = n$.