1. **Problem statement:** Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps using strong induction. 2. **Base cases:** Check amounts 12, 13, 14, and 15 cents. - 12 = 3 \times 4 - 13 = 2 \times 4 + 1 \times 5 - 14 = 1 \times 4 + 2 \times 5 - 15 = 3 \times 5 All can be formed using 4-cent and 5-cent stamps. 3. **Inductive hypothesis:** Assume for all amounts $k$ where $12 \leq k \leq n$, postage can be formed using 4-cent and 5-cent stamps. 4. **Inductive step:** Show amount $n+1$ can be formed. Since $n+1 - 4 = n - 3 \geq 12$ (for $n \geq 15$), by the inductive hypothesis, $n+1 - 4$ cents can be formed. Adding one 4-cent stamp to that amount forms $n+1$ cents. 5. **Conclusion:** By strong induction, every amount $\geq 12$ cents can be formed using 4-cent and 5-cent stamps. --- 1. **Problem statement:** Define recursive algorithm and give two examples. 2. **Definition:** A recursive algorithm solves a problem by calling itself with smaller inputs until reaching a base case. 3. **Example 1:** Factorial function $n!$ defined as: $$ \text{factorial}(n) = \begin{cases} 1 & \text{if } n=0 \\ n \times \text{factorial}(n-1) & \text{if } n>0 \end{cases} $$ 4. **Example 2:** Fibonacci sequence defined as: $$ \text{fib}(n) = \begin{cases} 0 & \text{if } n=0 \\ 1 & \text{if } n=1 \\ \text{fib}(n-1) + \text{fib}(n-2) & \text{if } n>1 \end{cases} $$