(New page: I'll put links here if anyone wants to provide solutions to the midterm. ==Midterm Problem 1== Call An the number of binary strings of size n without double zeroes. We can put each of th...) |
|||
| Line 18: | Line 18: | ||
==Midterm Problem 5== | ==Midterm Problem 5== | ||
==Midterm Problem 6== | ==Midterm Problem 6== | ||
| + | ==Midterm Problem 7== | ||
Revision as of 13:03, 31 October 2008
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.
