Homework 7 -- Induction and Recursion

1. List five elements in each of the following sets.
   
   1. 1. 2 is in the set.
      2. If x is in the set, then so is 5x-1.
      3. Nothing else is in the set.
      

   2. 1. a and b are strings in the set.
      2. If string x is in the set, then so are strings ax and bxc.
      3. Nothing else is in the set.
      

   3. 1. 2 and 9 are in the set.
      2. If x and y are in the set, then so is x+y. NOTE: You can plug the same
      element into both x and y, so, for example, you can get 2+2.
      3. Nothing else is in the set.
      

2. Given the following recursive function, what is f(1)? f(2)? f(3)? f(4)? f(5)?
   f(1) = 1
   f(n) = f(n-1) * 10
   

3. Given the following recursive function, what is f(1)? f(2)? f(3)? f(4)? f(5)?
   f(1) = 1
   f(2) = 3
   f(n) = f(n-2) + f(n-1)

4. Do problems 7 and 11 on page 123 of your textbook.

5. Extra credit: +10. Do problem 10 on page 123.