Read: Section 4.3.
Turn in: 4.19, 4.22, 4.23, 4.27
- Please prove each of these using induction even if you know another way!
- You should use strong induction for 4.27 with $P(n)$ defined to be $a_n = 2^n-1$. For the base step, you should verify that $P(1)$ and $P(2)$ are true. For the inductive step, you are assuming $P(1), P(2),\ldots, P(k)$ are all true, and you’ll use those—together with the crucial fact that for all $n$, $a_n = 3a_{n-1} - 2a_{n-2}$ (in particular, this holds for $n = k+1$)—to prove that $P(k+1)$ is also true.
Honor & Glory: clearly present a solution to 4.24(a,b)
Extra practice: 4.18, 4.20
