Fibonacci Numbers

Section 2.3 Fibonacci Numbers

Fibonacci numbers are a classic topic in combinatorics. They count many different objects, and their history is discussed at length on their wikipedia page

en.wikipedia.org/wiki/Fibonacci_sequence

🔗

Definition 2.3.1.

Let \(F_0:=1\) and let \(F_1:=1\text{.}\) Define the sequence \(F_0,F_1,F_2,\ldots\) using these initial conditions and the recurrence

\begin{equation*} F_n = F_{n-1}+F_{n-2} \, . \end{equation*}

This sequence is called the Fibonacci sequence and the numbers in the sequence are called the Fibonacci numbers.

🔗

Checkpoint 2.3.2.

With your group, calculate the first 10 Fibonacci numbers.

🔗

The Fibonacci numbers arise throughout mathematics. One of the basic problems they solve is counting integer compositions.

🔗

Definition 2.3.3.

A composition of a positive integer \(n\) is an ordered sum

\begin{equation*} x_1+x_2+\cdots +x_k = n \end{equation*}

where each \(x_i\) is a positive integer. We call each \(x_i\) a part of the composition.

🔗

Example 2.3.4.

Each of \(1+3+5+2+1+1+2\) and \(10+5\) and \(5+10\) are compositions of \(15\text{.}\)

🔗

Checkpoint 2.3.5.

Systematically list all the compositions of \(n\) for \(n=1,2,3,4\text{.}\)

🔗

Let \(\comp(n,A)\) denote the set of compositions of \(n\) using parts from the set \(A\text{.}\) So, for example, the set of all compositions of \(n\) is \(\comp(n,\Z_{\geq 1})\text{.}\)

🔗

Checkpoint 2.3.6.

Systematically list all the compositions in \(\comp(n,\{1,2\})\) for \(n=1,2,3,4,5\text{.}\)

🔗

Theorem 2.3.7.

For all positive integers \(n\text{,}\) we have

\begin{equation*} |\comp(n,\{1,2\})|=F_n \, . \end{equation*}

🔗

Proof.

We use the technique of writing the set \(\comp(n,\{1,2\})\) as a disjoint union. Observe that \(\comp(n,\{1,2\})\) is equal to

\begin{equation*} \left\{ a+1:a\in\comp(n-1,\{1,2\}) \right\} \uplus \left\{ a+2:a \in \comp(n-2,\{1,2\}) \right\} \end{equation*}

and therefore

\begin{equation*} |\comp(n,\{1,2\})|=|\comp(n-1,\{1,2\})|+|\comp(n-2,\{1,2\})| \, . \end{equation*}

Since \(|\comp(1,\{1,2\})|=1\) and \(|\comp(2,\{1,2\})|=2\text{,}\) the number of compositions using parts from \(\{1,2\}\) has the same initial conditions as the Fibonacci numbers starting at \(F_1\) and satisfies the same recurrence. Thus, our proof is complete.

🔗

Checkpoint 2.3.8.

Discuss the proof above with your group. Does the disjoint union make sense? Use the lists of compositions that you generated to check this for small values of \(n\text{.}\)

🔗

Our final topic for Fibonacci numbers is a connection with binomial coefficients.

🔗

Theorem 2.3.9.

For each positive integer \(n\text{,}\) we have

\begin{equation*} F_n=|\comp(n,\{1,2\})|=\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k} \end{equation*}

🔗

Checkpoint 2.3.10.

Discuss with your group: how might you prove this? What strategy could you use? How could binomial coefficients be related to compositions using ones and twos?

🔗

Proof.

The number of compositions of \(n\) using \(k\) copies of \(2\) is given by \(\binom{n-k}{k}\text{.}\) Since every element of \(\comp(n,\{1,2\})\) uses at most \(\lfloor n/2 \rfloor\) parts equal to \(2\text{,}\) the sum counts all the compositions.

🔗

Checkpoint 2.3.11.

Discuss this proof. Does it make sense? Why or why not?

🔗

Checkpoint 2.3.12.

Rewrite the proof above using the strategy to express the set \(\comp(n,\{1,2\})\) as a disjoint union of sets of compositions with a fixed number of \(2\)’s.

🔗

Prev Top Next