Let G_1 and G_2 be two arbitrary positive real values with G_1 =< G_2. We define
ID: 2970959 • Letter: L
Question
Let G_1 and G_2 be two arbitrary positive real values with G_1 =< G_2. We define a sequence {G_n} by the same recursive formula as the Fibonacci sequence {F_n} = {1,2,3,5,8,...}, G_n+1=G_n + G_n-1 for n >= 3, but whose initial values are now arbitrary. Define the sequence {r_n} by r_n = G_n+1/G_n
b) Find and prove recursive formula for r_n. HINT: Use the recursive formula for G_n (divide the formula by G_n).
c) Prove that 3/2 =< r_n =< 2 for all n >= 3. HINT: Use part (b) and mathematical induction. For the base case, n=3, use the explicit value of r_3 and make appropriate estimates.
d) Prove that for each n>=3,
|r_n+1 - r_n | =< [(2/3)^2] |r_n - r_n-1|
HINT: Use part (c).
e) Prove that for each n >= 3
|r_n+1 - r_n | =< [(2/3)^2(n-3)] |r_4 - r_3|
HINT: Use part (d) and mathematical induction.
f) Prove that {r_n} is a Cauchy sequence using an epilison-N argument. HINT: Use part (e)
g) SInce every Cauchy sequence converges, it follows from part (f) that r_n converges to some limit r. Find the value of r and prove your answer. Does r depend on the values G_1 and G_2? HINT: Use part (b).
Explanation / Answer
We start with the result of part (b), which I did in a previous problem for you.
r_n = 1 + 1/r_(n-1)
(c) r_3 = G_4/G_3 = (G_3 + G_2) / G_3 = 1 + (G_2)/(G_3) = 1 + [G_2/(G_2 + G_1)]
Since 0 <= G_1 <= G_2, we have that
1 + [G_2/(G_2 + G_2)] <= r_3 <= 1 + [G_2/(G_2 + 0)]
or
1 + [G_2/(2G_2)] <= r_3 <= 1 + [G_2 / G_2]
3/2 <= r_3 <= 2
So the base case is done. Now suppose that 3/2 <= r_n <= 2 and consider r_(n+1)
r_(n+1) = 1 + 1/r_n
Since 3/2 <= r_n <= 2, we have that
1 + 1/(2) <= r_(n+1) <= 1 + 1/(3/2)
or
3/2 <= r_(n+1) <= 1 + 2/3 = 5/3 <=2
So the result is proven by induction.
(d)
|r_(n+1) - r_n| = | (1 - 1/r_n) - (1 - 1/r_(n-1))| = | [ r_(n-1) - r_n ] / (r_n * r_(n-1) ) ]
= [1 / (r_n * r_(n-1) )] * |r_n - r_(n-1) |
Now from part (c), we know that r_n and r_(n-1) are both at least 3/2, so the term out in front is at most 1/[ (3/2)^2], and we have
|r_(n+1) - r_n| <= 1/[ (3/2)^2] * |r_n - r_(n-1) | = [(2/3)^2] |r_n - r_(n-1)|
(e)
Show that for each n >= 3
|r_(n+1) - r_n | <= [(2/3)^2(n-3)] |r_4 - r_3|.
Base case: If n = 3, the two sides of the inequaltiy are equal, so the statement is true for n=3. Now assume that the inequality |r_(n+1) - r_n | <= [(2/3)^2(n-3)] |r_4 - r_3| holds, and consider |r_(n+2) - r_(n+1) |. From part (d), and then by the inductive hypothesis, we have
|r_(n+2) - r_(n+1) | <= [(2/3)^2] |r_(n+1) - r_n| <= [(2/3)^2] * [(2/3)^2(n-3)] |r_4 - r_3| = [(2/3)^2((n+1)-3)] |r_4 - r_3|
So we have proven the inequality for all n>=3 by induction.
(f) Fix eps > 0. Choose N such that 3 * [(2/3)^2(N-3)] |r_4 - r_3| < eps. (Note that 3 and |r4-r3| are just constants, and we know the sequence {(2/3)^k} has limit 0 as k goes to infinity, so we know such an N exists.
Then whenever m > n >= N, we have
|x_m - x_n| = |(x_m - x_(m-1)) + (x_(m-1) - x_(m-2)) + ... + (x_(n+1) - x_n)|
<= |(x_m - x_(m-1))| + |(x_(m-1) - x_(m-2))| + ... + |(x_(n+1) - x_n)|
<= [(2/3)^2((m-1)-3)] |r_4 - r_3| + [(2/3)^2((m-2)-3)] |r_4 - r_3| + ... + [(2/3)^2(n-3)] |r_4 - r_3| (by part e)
= [(2/3)^2(n-3)] |r_4 - r_3| * [1 + 2/3 + (2/3)^2 + ... + (2/3)^[2(m-1)-3 - 2(n-3)]
< [(2/3)^2(n-3)] |r_4 - r_3| * [1 + 2/3 + (2/3)^2 + ... ] (the bracketed terms are an infinite geometric series]
= [(2/3)^2(n-3)] |r_4 - r_3| * [1/(1-(2/3))]
= 3 * [(2/3)^2(n-3)] |r_4 - r_3| <= 3 * [(2/3)^2(N-3)] |r_4 - r_3| < eps
So {r_n} is Cauchy.
(g) We know the sequence {r_n} converges. Let's call the limit r. So we have that
r = lim r_n = lim (1 + 1/r_(n-1)) = 1 + 1/r (since lim r_n = lim r_n-1 = r)
Thus
r = 1 + 1/r
r - 1 - 1/r = 0
r^2 - r - 1 = 0
r = (1 +- sqrt{1 - 4*1*(-1)}) / 2
r = (1 +- sqrt 5)/2
Since r can't be negative, we take the positive root.
r = (1 + sqrt 5) / 2
r is phi or "the golden ratio". It does not depend on the initial values of the sequence.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.