Prove the following combinatorially:
$$F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$$
So, I know that the Fibonacci number counts the number of ways to cover a $1 \times n$ rectangle with checkers (covering a single square) and dominoes (covering two squares). I believe that will come up somewhere in the explanation, but I am having difficulty seeing how to show that the RHS counts the same as the Fibonacci number.
EDIT: I think I have got it figured out. If we say that the LHS is the way to cover a nx1 rectangle with checkers and dominoes, then the floor of n/2 is the max amount of dominoes you could have. In this case, i represents the number of dominoes in that particular solution, hence why you have n-i positions. Then you figure out how many unique solutions there are when you have i dominoes, adding up all the solutions with the different number of dominoes.
Define $$G_n = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$$ so that we have $$G_1=1,G_2=2$$ and \begin{align*} G_{n}+G_{n+1}&=\binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}\cdots +\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}\cdots\\ &=\binom{n+1}{0}+\left(\binom n0+\binom{n}{1}\right)+\left(\binom{n-1}{1}+\binom{n-1}{2}\right)+\left(\binom{n-2}{2}+\binom{n-2}{3}\right)+\cdots\\ &=\binom{n+2}{0}+\binom{n+1}{1}+\binom{n}{2}+\cdots\\ &=G_{n+2} \end{align*} And so, $G_{n}$ is $n+1$-th Fibonacci number.
Edit: Just realized that you wanted a combinatorial proof- that one is actually easier.
Try proving that the number of $(n+1)$ length binary strings with no consecutive $1$'s relate to the Fibonacci numbers.
Now count the number of binary $(n+1)$ length strings that contain exactly $k$ $1$'s.