Read pages 19-22 (on induction)
Read pages 28-33 (on strings, languages)

1. Given alphabet {a, b}, how many strings are there
of length n?

2. Same as 1), but how many strings are there of
length at most n?

3. Use induction to prove that the nth Fibonacci number, f_n,
is greater than 2n, when n >= 6. Recall that f_0=1, f_1=1, f_2=
2, f_3 = 3, f_4= 5, f_5=8, f_6=13, and f_n = f_n-1 + f_n-2.

4. Use induction to prove that a set A={a1, a2, ..., an}
with at least one element has the same number of subsets 
with even cardinality as subsets with odd cardinality. 

5. A "tally" language is a subset of Sigma* where Sigma={1}.
For example A={1, 111, 11111, 1111111} is a tally language.
Let B be a tally language containing no string of length
more than n. 

a) What is the most number of strings that B can
contain? 

b) How many different such tally languages B can there be?

c) Are tally sets interesting? By that I mean, consider
a language X formed over a two-letter alphabet {0, 1}.
For example, let X consist of the set of primes numbers
in binary notation. Can we express X as a tally set?