Let a sequence X0; X1; X2; : : : be de ned in the following way:
X0=1
X1=2 (1)
Xn = 3Xn 1 + 2Xn 2:
Compute the rst 10 terms of this sequence. (2 points)
Prove that this sequence is strictly increasing, i.e., 8n 0 : Xn+1 Xn. (2 points)
Prove that 8n 0 : Xn 4n. What are the base cases? What is the inductive step? (5 points)
The above result suggests that this sequence grows in the worst case exponentially, i.e., Xn = O(4n). Consider trying to tighten this bound in the following way: what are the smallest values and such that the above proof still works for 8n 0 : Xn n? Give the tightest bounds on Xn you can. (10 points)
What is the tightest lower bound on Xn you can achieve in this way? Characterize the long term / asymptotic behavior of Xn as best you can. (5 points)
Consider the following sequence Y0; Y1; : : : de ned in the following way:
Y0
= 1
Y1
=
2
1
3
Yn =
Yn 1
+
Yn 2
:
4
4
6) Compute the rst 10 terms of this sequence (out to ten decimal places). (3 points)
7) Prove that this sequence satis es 8n 0 : 1 Yn 2. (3 points)
8) Prove that the following holds for all n 0:
Yn+1 Yn =
3
n
:
4
What is your base case? What is your inductive step? (10 points)
9) Argue that
n 1
3
k
Yn = 1 + k=0
4
:
X
Hint: What does the previous problem say about Y1? What does it say about Y2; Y3? (7 points)
10) What is the limit of Yn as n ! 1? (3 points)
(2)
(3)
(4)
Bonus: Show that regardless of the initial value of Y0 and Y1, that Yn converges to a constant in the limit. What is the limit? What part of the above results generalize, and which do not?
Bonus 2: Generalize the above results to arbitrary Y0; Y1, and Yn = pYn 1 + (1 p)Yn 2 for 0 < p < 1.
1
