The Golden Ratio, Fibonacci Numbers, and Other Recurrences

Fibonacci numbers have links to many different kinds of mathematics. They can be defined recursively as follows: F₀ = 0, F₁ = 1, and for n > 1, F_n = F_{n – 1} + F_{n – 2}. However, for convenience, we will sometimes define F₀ = 1, F₁ = 1, so that the math comes out more readable. It's a good idea to note which definition you're using, although F₀ = 0, F₁ = 1 is the typical one.

We can also interpret Fibonacci numbers in combinatorial terms; in effect, by counting certain tilings. It turns out that a Fibonacci number corresponds to the number of different ways in which we can tile an nx1 board width with squares and dominoes (2x1). For example, the number 4 can be expressed in terms of 1s and 2s in five ways: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, and 2 + 2. This can be visualized as different square and domino tilings of a board 4 units long.

The following table shows the number of different square and domino tilings possible for the first few positive integers, with F₀ = 1, F₁ = 1.

Notice that the number of tilings for a given integer, n, is the Fibonacci number F_n.

This link between Fibonacci numbers and tilings provides ingenious combinatorial proofs of a wide variety of relationships involving Fibonacci numbers. For example, suppose we sum the Fibonacci numbers from F₀ = 0 to F_n. The first sum is 0 + 1 = 1. Then, 1 + 1 = 2, 2 + 2 = 4, 4 + 3 = 7, 7 + 5 = 12, 12 + 8 = 20, 20 + 13 = 33, and so on. Each successive sum is one less than a Fibonacci number.

We can use square and domino tilings to prove combinatorially that the sum of the first n Fibonacci numbers equals F_n+1 – 1.

Such visualization and counting can play an important role in gaining insights into many aspects of mathematics.

Sequences and Tilings

We will start by looking at sequences that sum to n. Let F_n be the number of different sequences of 1’s and 2’s that sum to n. (F₀ = 1, F₁ = 1)

Example

F₄ = 5

1. = 2 + 2 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 1 + 1 + 1 + 1

F₀ = 1 0 = the empty sum F₁ = 1 1 = 1 F₂ = 2 2 = 1 + 1 2 F_n+1 = F_n + F_n-1, where F_n is the number of sequences beginning with a 1 and f_n-1 is the number of sequences beginning with a 2.

We have the Fibonacci numbers again, where F_{n + 1} = F_n + F_n-1,with F₀ = 1 and f₁ = 1.

We can also express the same representation visually as tiling.

We let F_n be the number of different ways to tile a 1 x n strip with squares and dominoes. There is:

1 way to tile a strip of length 0; 1 way to tile a strip of length 1;

2 ways to tile a strip of length 2;

and so on.

If F_n is the number of ways to tile a strip of length n, we have F_n-1 tilings that start with a square - just take the tilings of length n-1 and add a square to the beginning - and f_{n -2} tilings that start with a domino - just take the tilings of length n-2 and add a domino to the beginning. Altogether, we have F_n = f_n-1 + f_n-2.

Fibonacci Identities

The Fibonacci numbers have many unusual properties. The many properties that can be stated as equations are called Fibonacci identities. We can use the visual representation we described above to prove a couple of Fibonacci identities.

Examples

F_2n = F₁ + F₃ + F₅ + … + F_{2n - 1}

F_m+n = F_m F_n + F_m-1 F_n-1

(F_n)² = F_n-1 F_n+1 + (-1)ⁿ

Identity: F_m+n = F_m F_n + F_m-1 F_n-1

Proof:

F_m+n is the number of ways to tile m + n. m n

Number of tilings where no tile straddles the "fault line" = F_m F_n. (Tile the first m places, then the remaining n) m n

Number of tilings where a domino straddles the "fault line" = F_m-1 F_n-1. (Tile the first m-1 places, put a domino down, and then tile the remaining n-1).

* someone please fix the subscripts beyond this point *

Identity: (F_n)² = F_n-1 F_n+1 + (-1)ⁿ

Proof: n

F_n tilings of a strip of length n.

We have (F_n)² tilings of two strips of length n.

Draw a vertical "fault line" at the rightmost position (< n) possible without cutting any dominoes. Swap the tails at the fault line to map to a tiling of 2 ns to a tiling of an n+1 and an n-1.

We find that (F_n)² = F_n-1 F_n+1 + (-1)ⁿ.

Here are some other amazing properties of Fibonacci numbers:

*The product of any four consecutive Fibonacci numbers is the area of a Pythagorean triangle. *The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in 15,000, etc. *They are useful for converting miles to kilometers.

Polynomial Division

Suppose that we want to divide 1 by 1-x: .

Using “long division,” we get the answer 1 + x + x² + x³ + x⁴ + x⁵ + . . .

Recall that the geometric series is defined to be

Example:

Divide x by 1- x-x².

= 0x⁰+ 1x¹ + 1x² + 2x³ + 3x⁴ + 5x⁵ + 8x⁶ + . . . = F₀1 + F₁x¹ + F₂x² +F₃x³ + F₄x⁴ + F₅x⁵ + F₆x⁶ + . . .

We have the Fibonacci numbers again.

Going the other way (noting that F₀ = 0, F₁ = 1):

(1 – x– x2) ´ (F₀1 + F₁x¹ + F₂x² + … + F_n – 2 xⁿ – 2 + F_n – 1 xⁿ - 1 + F_n xⁿ + . . . = (F₀1 + F₁ x¹ + F₂ x² + … + F_n – 2 xⁿ – 2 + F_n – 1 xⁿ – 1 + F_n xⁿ + . . . – F₀ x¹ – F₁ x² – … – F_n – 3 xⁿ – 2 – F_n – 2 xⁿ – 1 – F_n – 1 xⁿ – . . . – – F₀ x² – . . . – F_n – 4 xⁿ – 2 – F_n – 3 xⁿ – 1 – F_n – 2 xⁿ – … = F₀1 + (F₁ – F₀) x1 = x Thus, F₀1 + F₁ x¹ + F₂ x² + … + F_n – 1 xⁿ – 1 + F_n xⁿ + . . . = x/(1 – x – x²).

Formal Power Series

Recall that a formal power series, or an infinite polynomial, is defined as:

PV =

How could someone have figured that out?

POLYA: When you want to find a solution to two simultaneous constraints, first characterize the solution space to one of them, and then find a solution to the second that is within the space of the first.

Here’s a technique to derive the formula for the Fibonacci numbers.

Fn is defined by two conditions: Base condition: F0 = 0, F1 = 1 Inductive condition: Fn = Fn – 1 + Fn – 2

Forget the base condition and concentrate on satisfying the inductive condition.

Consider solutions of the form: Fn = cn for some complex constant c. c must satisfy: cn – cn – 1 – cn – 2 = 0 iff cn – 2 (c2 – c1 – 1) = 0 iff c = 0 or c2 – c1 – 1 = 0 iff c = 0, c = f, or c = –(1/f) c = 0, c = f, or c = – (1/f)

So for all these values of c, the inductive condition is satisfied: cn – cn – 1 – cn – 2 = 0. Do any of them happen to satisfy the base condition as well? c0 = 0 and c1 = 1?

Insight: If two functions g(n) and h(n) satisfy the inductive condition then so does a g(n) + b h(n) for all complex a and b. g(n) – g(n – 1) – g(n – 2) = 0 ag(n) – ag(n – 1) – ag(n – 2) = 0 h(n) – h(n – 1) – h(n – 2) = 0 bh(n) – bh(n – 1) – bh(n – 2) = 0 (a g(n) + b h(n)) + (a g(n – 1) + b h(n – 1)) + (a g(n – 2) + b h(n – 2)) = 0 " a, b a fn + b (–1/f)n satisfies the inductive condition.

Set a and b to fit the base conditions. n = 0 : a + b = 0 n = 1 : a f1 + b (–1/f)1 = 1

We have two equalities in two unknowns (a and b). Now solve for a and b. This gives: a = 1/Ö5 and b = –1/Ö5. We have just proved Euler’s result.

Closed Form for Fibonacci Numbers

The Golden Ratio is defined to be the positive root of the equation

Then the n^th fibonacci number is given by F_n =

References

Coxeter, H. S. M. ``The Golden Section, Phyllotaxis, and Wythoff's Game.'' Scripta Mathematica 19, 135-143, 1953.

"Recounting Fibonacci and Lucas Identities" by Arthur T. Benjamin and Jennifer J. Quinn, College Mathematics Journal, Vol. 30, No. 5, 1999, pp. 359-366.