# Fibonacci identity

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?

• Thank you for editing. there are still some minor mistakes there in my typing. f_n = f_(n-1) + f_(n-2) and after sigma, a_ig_(n-i) is required. If possible, edit. Thank you. – Gandhi Aug 17 '11 at 9:44
• Generalize... but in which direction, for which purpose? – Did Aug 17 '11 at 9:55