Let G1 and G2 be two arbitrary positive real values with G1 ?G2 . We define a se

Question

Let G1 and G2 be two arbitrary positive real values with G1 ?G2 . We define a sequence {Gn} by the same recursive formula as the Fibonacci sequence {Fn}={1,2,3,5,8,...}, Gn+1 = Gn +Gn?1 for n?3, but whose initial values are now arbitrary (G1 and G2 ). Define the sequence {rn} by rn = Gn+1/Gn

Prove the following:

(a) Find and prove a formula for Gn in terms of G1 , G2 , and Fn (Fibonacci numbers). HINT: Calculate the first few terms of Gn to observe a pattern.

(b) Find and prove a recursive formula for rn . HINT: Use the recursive formula for Gn (divide the formula by Gn ).

Explanation / Answer

(a)

G1 = G1

G2 = G2

G3 = G2 + G1

G4 = G3 + G2 = 2G2 + G1

G5 = G4 + G3 = 3G2 + 2G1

G6 = G5 + G4 = 5G2 + 3G1

G7 = G6 + G5 = 8G2 + 5G1

It looks as though the coefficients of G2 and G1 are themselves Fibonacci numbers. So it looks like for n >= 3 we have

Gn = F(n-1) G2 + F(n-2) G1

(assuming that F1 = 1 and F2 = 1)

Proof: We have that G3 = (1)(G2) + (1)(G1) = F2 G2 + F1 G1 = F(3-1) G2 + F(3-2) G1. So the base case is true. Now assume that

Gk = F(k-1) G2 + F(k-2) G1 for all k <=n. We show the formula holds for n+1.

G(n+1) = Gn + G(n-1) = F(n-1) G2 + F(n-2) G1 + F(n-2) G2 + F(n-3) G1 = [F(n-1) + F(n-2)] G2 + [F(n-2) + F(n-3)] G1

= Fn G2 + F(n-1) G1 = F((n+1)-1) G2 + F((n+1) - 2) G1

So the formula is proven by induction.

(b) r_1 = G2/G1

r_2 = G3/G2 = (G2 + G1) / G2 = 1 + G1/G2 = 1 + 1/r_1

r_3 = G4 / G3 = G3 + G2 / G3 = 1 + G2/G3 = 1 + 1/r_2

So for n >=2, we have

r_n = G_(n+1) / G_n = [G_n + G_(n-1)] / G_n = 1 + [ G_(n-1)/G_n] = 1 + 1/r_(n-1)

So this is our recursive formula.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.