Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
Thank you so much for instant editing. – Gandhi Aug 17 '11 at 9:50
Generalize... but in which direction, for which purpose? – 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

share|cite|improve this answer
good. The second one is little better than others. – Gandhi Aug 17 '11 at 17:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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