Problem 0: Complete the Canvas quiz "PSet 5 - Canvas".

Problem (14 points): Our goal is to find the smallest $k$ so that can $k'$ cents postage for any integer $k' \ge k$ with 4-, 9- and 15-cent stamps. ($k$ and $k'$ are restricted to be integers throughout the prompts given below.)

• Prove that if you can make $k$ cents postage with some combination of 4-, 9-, and 15-cent stamps that includes at least 2 4-cent stamps, then you can make $k+1$ cents postage.
• Prove that if you can make $k$ cents postage with some combination of 4-, 9-, and 15-cent stamps that includes at least 2 9-cent stamps, then you can make $k+1$ cents postage.
• Prove that if you can make $k$ cents postage with some combination of 4-, 9-, and 15-cent stamps that includes at least 1 15-cent stamp, then you can make $k+1$ cents postage.
• Prove that if you have $k$ cents postage for some $k \ge 14$, then you must have either 1) at least 2 4-cent stamps; 2) at least 2 9-cent stamps; or 3) at least 1 15-cent stamp.
• Find the smallest $k$ so that you can make $k'$ cents postage for any $k' \ge k$ with 4-, 9-, and 15-cent stamps.
• For your chosen $k$, prove that you can make $k'$ cents postage for any $k' \ge k$ with some combination of 4-, 9-, and 15-cent stamps.

Problem (10 points): Prove by induction that $\sum_{i=1}^{n} (2i+3) = n(n+4)$ for all integers $n \ge 0$ (do not use the result shown in class that $\sum_{i=1}^n i = \frac{n(n+1)}{2}$).

Problem (10 points): Prove by induction that for any positive odd integer $n$, $2n^2 + 6$ is a multiple of 8. (This is easy to prove directly, but the objective here is to practice induction, so make use of the relationship between what the inductive hypothesis tells you something about and what you want to come to a conclusion about.)

Problem (10 points): Define a sequence by $a_0 = 4$, $a_1 = 16$, and $a_n = 2a_{n-1} + a_{n-2} - 2$ for $n \ge 2$. Prove by strong induction that $a_n \equiv 4 \pmod{6}$ for all integers $n \ge 0$.