### The Prove it! Math Academy residential summer program will not be offered in 2024. Big changes are in the works to provide our unique curriculum and high-quality resources to a wider audience of math enthusiasts. Check this site for updates and 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.$$