Our top priority is always the safety and well-being of our students. Given the COVID-19 pandemic, we can no longer hold our in-person residential program for 2020 as originally planned. Instead, in order to do our part as we all navigate this crisis together, the Prove it! team will be offering a free online program this summer.

All spots are currently filled and we are no longer accepting additional applications. You can find information about additional summer math programs at the AMS website.

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