Show that for any $n\geq 0$, the Fibonacci numbers $f_{2n}$ satisfy $f_{2n}=\sum\limits_{k=0}^n\binom{n+k}{2k}$

Question

I understand that $f_{2n}$ can be represented by all the possible combinations of squares and dominoes for a $2n$ board.

But I don't understand how to simplify the right hand side in a way that I can intuitively explain that it does the same thing.

Answer 1

HINT: A tiling of a $1\times2n$ board by squares and dominoes must use an even number of squares. Suppose that it uses $2k$ squares.

• How many dominoes does it use?
• How many tiles does it use altogether?
• How many tilings of the board are there that use exactly $2k$ squares?

By the way, the Fibonacci numbers are usually indexed so that $f_0=0$ and $f_1=1$. In that indexing the number of tilings of a $1\times n$ board with squares and dominoes is $f_{n+1}$, and the sum in your question is $f_{2n+1}$.