Quiz 2: Solutions Whiteley, October 30, 9:00

1.    Consider the function defined by:  
             (i)  f(0) = 1,  f(1) = 2:
            (ii)  f(n) = f (n-2) + 2 f(n-1).
   a)  Prove, by induction, that  f(n) >= 2^n for all   n>= 0 .

       The property being proven is  P(n):  f(n) >= 2^n 
        Base cases:   f(0) = 1 >= 1 = 2^0;
                            f(1) = 2 >= 2 = 2^1.
       Induction step:  Assume that  for  all  i <=k,  f(i) >= 2^i.
                    Consider:  f(k+1) = f (k-1) + 2 f(k-2)  
                          >=  2^(k-1)  + 2 (2^k) >=  2 (2^k) = 2^(k+1).
        Therefore, by induction  f(n) >= 2^n  for all  n>=0.

NOTE:  You must use the second principle of induction, as the 
inductive step uses two smaller cases, not just one.  
In the same sense, you do need two base cases.

  b)  Is f(n) <= 3^n  for all  n>= 0?  [No proof is required here.]
   YES.
  This IS also provable by induction.  
   The base cases are obvious:  1 <= 1,   2<= 3.
   The inductive step comes down to:
     f(k+1) = f (k-1) + 2 f(k-2) <= 3^(k-1)  + 2 (3^k) 
                    = 3^(k-1)[1+ 6]   <= 3^(k-1)[9]  = 3^(k+1)

2.     Consider the subset  S  of strings of 0 s and  1 s generated 
  by the recursive definition:
    (i)   1 in S  and  0 in S;
    (ii)  if  \alpha  in S  then  1\alpha 1  in S  and   0\alpha 0 in S.

  a)  Prove that if  \beta in S , then the reversal of  \beta, obtained 
    by reversing the order of the symbols in the string, 
    written  r(\beta), is equal to  \beta .  [That is  \beta  is a  palindrome.] 

     By induction on the steps of the recusive construction:
     Base case:  If  \beta has length=1,  then  r(\beta) = \beta.
     Induction step.  Assume  r(\alpha) = \alpha  for all strings 
      in  S  of length  <= k .
      Let  \beta be a string  in  S  of length  k+1  
         Therefore  \beta= 1\alpha1   or   \beta= 0\alpha0.
         Now  r(1\alpha1) =  1 (r(\alpha)) 1 =  1\alpha1, 
            by the induction assumption.
         Similarly: r(0\alpha0) =  0 (r(\alpha)) 0 =  0\alpha0, 
      In either case,  \beta is a palindrome, as required.
    By induction, all strings  \beta  in S are palindromes.

  b)   List all strings in  S  of length  0, 1, 2, 3.
      Strings of length  0:  NONE
         The only such string is the empty string,  but it is not in  S.
      Strings of length  1:    1,    0   
      Strings of length  2:  NONE
         The recursive step adds two symbols to a smaller string, 
           and there were no strings of length  0.
      Strings of length  3.    111,    101,  010,  000.   

   A string which is a palindrome but is not in S:   
                  \lambda (the empty string)   OR
                   11,   00.

  c)   How would you change the definition of  S  so that the new set
    contains all palindromes of  0  s and  1  s. [No proof is required,
    just a revised  definition.]

        Add to step (i)   the empty string  \lambda in S.
   This will generate all the even palindromes.
        Almost a right answer:  Add  11,   00  in  S.
   This just misses the empty string, which is indeed a palindrome.