- Give a combinatorial proof of the following identities.
**1. Pascal’s recursion.**Show that for any natural numbers $n$ and $k$, we have $$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.$$**2. A Fibonacci identity.**Let $F_n$ be the $n$th Fibonacci number, which can be defined as the number of ways to climb an $n$-stair staircase from stair $1$ to stair $n$ using steps of size $+1$ or $+2$ at each step. Prove that $$F_0+F_1+F_2+\cdots+F_n=F_{n+2}-1.$$**3. Catalan numbers.**Let $C_n$ by the $n$th Catalan number, defined as the number of Dyck paths (that stay weakly above the diagonal) in an $n\times n$ grid. (Note that $C_0=1$.) Show that the Catalan numbers satisfy the recurrence $$C_{n+1}=C_0C_n+C_1C_{n-1}+C_2C_{n-2}+\cdots + C_nC_0.$$