The Fibonacci numbers
*F _{n}*
are defined recursively by the
relation

They describe, among other things, the number of ways
to tile a 2 × (*n*−1) checkerboard with 2 × 1 dominoes.

There’s only one way to tile a 2 × 1 board:

Two ways to tile a 2 × 2 board:

Three ways to tile a 2 × 3 board:

Five ways to tile a 2 × 4 board:

Eight ways to tile a 2 × 5 board:

Thirteen ways to tile a 2 × 6 board:

Twenty-one ways to tile a 2 × 7 board:

See also Graham, Knuth, and Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994.

Originally designed and rendered using *Mathematica* 3.0 and GifOMatic for NeXT.

© 1997–2020 Robert Dickau.

(With belated thanks to Steven Fairgrieve for some minor corrections.)

[ home ] || [ 2006-05-23 ]

www.robertdickau.com/fibboard.html