The Fibonacci Sequence

Try this

Keep $L = 6$ and drag the cut $m$ from $1$ to $5$ . The total stays $13$ , but the sizes of the two piles change. Do the two products in the formula always match the sizes of the two piles?
Look at the second pile (the tilings that straddle the cut). The darker pair of lying dominoes always covers columns $m$ and $m + 1$ . Take it away and you are left with two shorter strips.
Drag $m$ to $1$ . What does the equation become? You should recognize it: it is the Fibonacci recurrence $F_{L + 1} = F_{L} + F_{L - 1}$ .
Take $L = 7$ , $m = 3$ . Both products on the right contain the same factor $F_{4} = 3$ . So $F_{8}$ is a multiple of $F_{4}$ — and that is no coincidence.

The Fibonacci sequence ${F_{n}}$ : $F_{1} = F_{2} = 1$ , $F_{n + 2} = F_{n + 1} + F_{n}$ . The number of ways to tile a $2 \times n$ strip with $1 \times 2$ dominoes is exactly $F_{n + 1}$ : look at the right end — one upright domino leaves $2 \times (n - 1)$ , two lying dominoes leave $2 \times (n - 2)$ . Put the observations above together and you get an “addition formula”:

F_{p + q} = F_{p} F_{q + 1} + F_{p - 1} F_{q} .

Predict first

A 2×8 strip has $F_{9} = 34$ tilings. Cut after column $4$ . How many tilings have a clean cut (no lying domino crosses the cut)?

tilings

Choose an answer first; then you can see the result.

Why

“Count it twice”: count the same set of tilings once as a whole, then again split into two piles by what happens at the cut.

The addition formula: one cut through the strip

Step 1 / 6

What we count
A 2×7 strip has $F_{8} = 21$ tilings. Draw a dashed line after column $m$ and ask: is the tiling broken or joined at this line?

$F_{8} = 21$
The clean-cut pile
The straddling pile
Add the two piles
Take m = 1
Take p = q

One more step leads to the most beautiful property of the Fibonacci sequence: to find the gcd of two terms, find the gcd of their indices.

Divisibility and the gcd

Step 1 / 4

First: a multiple index gives a multiple
Induct on $k$ . $k = 1$ is clear. If $F_{n} ∣ F_{k n}$ , put $p = k n$ , $q = n$ in the addition formula: both terms contain the factor $F_{n}$ .

$F_{(k + 1) n} = F_{k n} F_{n + 1} + F_{k n - 1} F_{n}$
Neighboring terms are coprime
One “subtraction” on the indices
The Euclidean algorithm, moved to the indices

Squares into a rectangle

Squares of side $1, 1, 2, 3, 5, \dots$ , each glued onto the long side of the figure so far, always fit together exactly into a rectangle. Adding a square turns the sides of the figure from $F_{n - 1}, F_{n}$ into $F_{n}, F_{n + 1}$ — that is the recurrence. Count the area:

F_{1}^{2} + F_{2}^{2} + \dots + F_{n}^{2} = F_{n} F_{n + 1} .

The last readout is the ratio of neighboring terms,

F_{n + 1} / F_{n}

. Increase

n

one step at a time: it jumps back and forth across

φ = \frac{1 + 5}{2}

, getting closer each time.

Predict first

The ratios $\frac{F _{n + 1}}{F _{n}}$ are $\frac{1}{1}, \frac{2}{1}, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \dots$ . How does the sign of their difference from $φ \approx 1.618$ behave?

Always below

φ

Always above

φ

Below, above, below, … alternating

Choose an answer first; then you can see the result.

Remove one condition

Break it

Counterexample lab: remove one condition

Conclusion: $G_{1}^{2} + \dots + G_{n}^{2} = G_{n} G_{n + 1}$ : the squares make a rectangle

The first two Fibonacci numbers are both $1$ : the second square exactly covers one side of the first, and from then on every square fits exactly.

Practice

Exercise 1Basic

Find $F_{1} + F_{2} + \dots + F_{10}$ .

Exercise 2Basic

In how many ways can a $2 \times 9$ strip be tiled with $1 \times 2$ dominoes?

Exercise 3Advanced

Find the greatest common divisor of $F_{24}$ and $F_{36}$ .

Exercise 4Challenge

Prove that $F_{n + 1}^{2} - F_{n} F_{n + 2} = (- 1)^{n}$ for every positive integer $n$ .

Try this

Why

The addition formula: one cut through the strip

Divisibility and the gcd

Squares into a rectangle

Remove one condition

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

The number of tilings is off from the Fibonacci index by one

Treating a necessary condition as a sufficient one