Consider the following:

	a1 = 1
	ai = 2afloor(a/2) + i


Problem 1: Use techniques from CMSC250 to prove that an>n.
Problem 2: Use techniques from CMSC250 to prove that an<n2.
Question: What does an actually equal?  We will see this in CMSC351.



Consider the following:

	a0 = 0
	a1 = 1
	ai = ai-1 + ai-2

Problem 1: Use techniques from CMSC250 to prove that an < 2n.
Question: Let's assume that an is less than xn for some positive integer x.  
          How could you use induction to solve for x?
             [Note: In class we briefly discussed the idea of 
                    computing Fibonacci numbers via a formula 
                    rather than iteration.  Solving this and
                    identifying its limitations is the key to 
                    continuing discussing that.]