Let b_n be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for b_n?
A. b_n = b_{n-1} + b_{n-2}, b_1 = 1, b_2 = 2
B. b_n = b_{n-1} + b_{n-2}, b_1 = 2, b_2 = 3
C. b_n = 2*b_{n-1}, b_1 = 1
D. b_n = b_{n-1} + 2*b_{n-2}, b_1 = 1
Answer: The recurrence is b_n = b_{n-1} + b_{n-2} with b_1 = 2 and b_2 = 3, which is option B.
Establish base cases by enumeration: 1-bit strings: '0' (valid) and '1' (valid) => b_1 = 2. 2-bit strings: '00','01','10' are valid; '11' is excluded => b_2 = 3.
Derive recurrence by splitting on the last bit: Case 1 — last bit is 0: the first n-1 bits form any valid (n-1)-bit string, giving b_{n-1} strings. Case 2 — last bit is 1: to avoid '11', the (n-1)-th bit must be 0, so the first n-2 bits form any valid (n-2)-bit string, giving b_{n-2} strings. Together: b_n = b_{n-1} + b_{n-2}.