Fibonacci Series: Introduction

Based on popular requests, I'm going to start a new series of posts called the Fibonacci Series (HA!)

It will explore a number of combinatorial interpretations of the Fibonacci series, and the elegance with which we could prove some Fibonacci-related theorems, using purely combinatorial arguments and minimal algebra.

Definition

A sequence $F_n$ is defined by $F_0 = 1, F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$. This sequence is called the Fibonacci sequence. The first few terms of the sequence is (starting with $F_0$): 1,1,2,3,5,8,13,21,...

Suppose there is a stair with $n$ steps, and one can climb it using "steps" or using "hops" where each step ascends the person by 1 step of stair, and each hop ascends the person by 2 steps.

For a stair with 2 steps, there are 2 ways one can climb it. By using 2 steps, or a hop. For a stair with 3 steps, there are 3 ways: step-hop, hop-step, or step-step-step. For 4 steps, there are 5 ways: 4 steps, step-step-hop, step-hop-step, hop-step-step, hop-hop.

Theorem: In general, for a stair with $n$ steps, there are exactly $F_n$ ways to climb it.

Proof:
Proof by induction.

The first action that one can take could be a step or a hop. If the first action is a step, then the climber must ascend the remaining $n-1$ steps with combinations of steps and hops. There are $F_{n-1}$ such ways.

If the first action is a hop, then the climber must ascend the remaining $n-2$ steps, and there are $F_{n-2}$ ways to do so.

These two cases are mutually exclusive, so in total there are $F_{n-1} + F_{n-2}$ ways to climb. This is exactly the recursive equation for the Fibonacci series, and since the first few terms agree, we conclude that in general the number of ways to climb an $n$-step stair is $F_n$.

Exercise:

There are many more possible combinatorial interpretations of the Fibonacci sequence. For the rest of the series, we are going to use the stair-climbing interpretation, but the following interpretations are just as useful.

1. Prove that $F_{n+1}$ is the number of binary numbers with $n$ digit such that there are no two consecutive zeroes.

2. Prove that $F_{n+1}$ is the number of subset from the set $\{ 1, 2, \dots, n \}$ without two consecutive numbers.

3. Prove that $F_{n-2}$ is the number of ways to tile a $1 \times n$ board with tiles of length 2 or longer.

4. Prove that $F_{n-1}$ is the number of ways to tile a $1 \times n$ board with tiles that have odd length.

5. Prove that $F_n$ is the number of permutation $(a_1, \dots, a_n)$ of $\{ 1, \dots, n \}$ such that for each $i$, $|a_i - i| \leq 1$.

6. Prove that $F_{2n+1}$ is the number of ternary numbers with $n$ digits where a 0 is never followed by a 2.