Read: Start of Section 4.4.
Turn in: 4.28, 4.32 or 4.34, 4.37
- Please prove the problems from Section 4.3 using induction even if you know another way!
- For 4.34, let $b_n$ be the number of binary strings of length $n$ that never have two consecutive 1’s. (Binary strings were defined in Problem 4.33.) Your goal is to prove that $b_n = f_{n+2}$ for all $n\ge 1$, where $f_{n+2}$ comes from the Fibonacci sequence defined in Problem 4.29. To prove this by induction, you should start by verifying that $b_1 = f_{3}$ as the base step. For the inductive step, consider two cases: strings of length $k+1$ that end in a 0 and strings of length $k+1$ that end in a 1.
Extra practice: 4.29, 4.31–4.34
