I'll put links here if anyone wants to provide solutions to the midterm.
Contents
Midterm Problem 1
Call An the number of binary strings of size n without double zeroes. We can put each of the strings in An in one of three separate groups:
- Strings that begin with 10 or 11 (ie begin with 1): 1|(n-1 digits)
- Strings that begin with 01: 01|(n-2 digits)
- Strings that begin with 00: 00|(n-2 digits)
Clearly the third group has no members. Further if the entire string is assumed to have no double zeroes, then the (n-1 digits) and (n-2 digits) have no double zeroes either. Thus there are An-1 strings in the first group and An-2 strings in the second group.
Thus, An=An-1+An-2, and since A0=1, A1=2, this defines the recurrence relation.
