### The Prove it! Math Academy summer program will not be offered in 2021. Big changes are in the works to provide our unique curriculum and high-quality resources to a wider audience of math enthusiasts in 2022. Check this site for updates or follow us on Facebook for announcements.

- 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.$$