TAOCP 1.2.8 Fibonacci Numbers: reading guide

The Fibonacci sequence, its closed form in terms of the golden ratio, and a pile of identities. Knuth introduces generating functions here as the tool for deriving the closed form, a preview of 1.2.9.

Time About 5 hours this week

Why it matters

Fibonacci numbers show up in the worst case of Euclid's algorithm, Fibonacci heaps, AVL tree heights and Fibonacci hashing. It is also the cleanest first example of solving a recurrence.

Before you start

1.2.1 Mathematical Induction
1.2.6 Binomial Coefficients

How to approach it

Follow the generating-function derivation of the closed form line by line on paper. Then write a quick program checking several identities numerically for n up to 50.

Exercises

Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.

Traps

Floating-point closed forms break for large n; use integers when you code it.