Can someone show me a combinatorial proof for this identity? $$\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor} \binom{n-k}{k} = F_{n+1}$$
I've been trying to make sense of it using the domino tiling proof(would that even help?) but I don't understand combinatorial proofs at all.
You want to tile a $1\times n$ rectangle with monominoes and dominoes. If $k$ is the number of your dominoes, then show that you can do this job in $\binom{n-k}{k}$ ways. To show this, let $X(n,k)$ denotes the set of all tiling of the $1\times n$ block with exactly $k$ dominoes (and hence $n-2k$ monominoes), and let $Y(n,k)$ denote the set of all ways to choose exactly $k$ squares from an $1\times(n-k)$-block. Clearly $\big|Y(n,k)\big|=\binom{n-k}{k}$. Define the function $f:X(n,k)\to Y(n,k)$ given by removing the right square from each domino, and letting the left square of each domino be the chosen squares in $Y(n,k)$. Show that $f$ is a bijection.
Hence the number of all tilings is just $$\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}.$$ But it can be proven that the number of ways to tile a $1\times n$ block with monominoes and dominoes is precisely the $(n+1)$st Fibonacci number $F_{n+1}$. The proof is now complete.