combinatorics - Prove the following equality: $sum_{k=0}^nbinom {n-k }{k} = F_n$

I need to prove that there is the following equality:

$$

\sum\limits_{k=0}^n {n-k \choose k} = F_{n}
$$
where $F_{n}$ is a n-th Fibonacci number.

The problem seems easy but I can't find the way to prove it. Could you give me any hints? I'm looking for a combinatorial proof.

Answer

Arthur Benjamin actuall wrote a book that seemed to me to be nothing other than combinatorial properties of Fibonacci and other similar numbers, called "Proofs that Really Count". I found it rather interesting. $F_n$ has one popular representation as a combinatorial object, and that is the number of sequences of 1s and 2s that sum to form $n-1$. This is $F_n$ because $F_1 = F_2 = 1$ and the number of ways to make $n-1$ is the number of sequences that sum to $n-3$ with a two at the end, and the number of ways to sum to $n-2$ with a 1 at the end. This can be recast with a number of other situations, like coloring sequences of tiles or placing dominoes, but it's the same idea.

Now this identity comes from counting the number of ways to form this sum that contain exactly $k$ $2s$ in the sequence. Summing this from $0$ to $n$ is the same as summing from $0$ to $[\frac{n}{2}]$ and is finding how many sequences with 1 two, 2 twos, and so on. This ends up being the total number of ways to make the sequence, although it comes out to be $F_{n+1}$ and not $F_n$, as the Fibonacci sequence is usually indexed at $1$ and not $0$ (hence why we are summing to $n-1$).