The Fibonacci numbers, given by $f_0 = 1$, $f_1 = 1$ and $f_n = f_{n-1} + f_{n-2}$, for $n \geq 2$ have many interesting properties. Many of these interesting properties can be easily proven combinatorially by interpreting the Fibonacci numbers as the number of ways,to tile a $1\times n$ board with squares ($1\times 1$ tiles) and dominoes ($1\times 2$ tiles). This interpretation has been generalized to interpret recurrence relations with nonnegative integer coecients and initial conditions. Specially, $g_n = \sum_{i = 1}^{k} a_ig_{n-i}$ with the $a_i$s non-negative integers can be interpreted as the number of ways to tile a board of length $n$ with tiles of length $1$ through $k$, where tiles of length $i$ are given one of $a_i$ colors, and the rst tile is given a certain number of phases depending on the $a_i$ the initial conditions, and the length. Can you generalize this?
Fibonacci identity
5
$\begingroup$
fibonacci-numbers
-
9*Generalize*... but in which direction, for which purpose? – 2011-08-17
1 Answers
4
I recall much work along such lines, which is confirmed by a quick web search, e.g.
The Combinatorialization of Linear Recurrences
Linear Recurrences Through Tilings and Markov Chains
-
0good. The second one is little better than others. – 2011-08-17