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

- Prove the following using only the rules of natural deduction for predicate logic with equality, the Peano Axioms, and the recursive definitions of the symbols given in the lecture notes. You can Your proof should be written in the semiformal proof style using any of the shortcuts we went over. You can use any of the theorems about natural numbers that appear at the end of section 7.5 in the lecture notes. All quantified variables represent natural numbers. You cannot use any negative signs or subtraction in your proofs because we have not yet defined those. Feel free to ask an instructor for help if you get stuck.
**1. Row sum in Pascal’s triangle.** $$ \sum_{k=0}^n {n \choose k}=2^n$$
**2. Factorial vs. Exponential Growth.** For all natural numbers $n\geq 4$, $$2^n\lt n!$$
**3. A Fibonnaci binomial theorem?** Suppose $n$ is a natural number. Then $$\sum_{k=0}^n \binom{n}{k}\cdot F_k = F_{2n}$$