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?

  • $\begingroup$ 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. $\endgroup$ – Gandhi Aug 17 '11 at 9:44
  • 9
    $\begingroup$ Generalize... but in which direction, for which purpose? $\endgroup$ – Did Aug 17 '11 at 9:55

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

Classical q-Series Identities via Tilings

A Tiling Approach to Eight Identities of Rogers

  • $\begingroup$ good. The second one is little better than others. $\endgroup$ – Gandhi Aug 17 '11 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.