5. The Fibonacci sequence is the sequence f-(fo.fi./. . . .)=(0, 1, 1, 2, 3, 5,

Question

5. The Fibonacci sequence is the sequence f-(fo.fi./. . . .)=(0, 1, 1, 2, 3, 5, 8, 13, 21.34. 55. . . .) which is defined by fo = 0, f1 = 1, fn = fn-1+fn-2 for all n 22 In this problem, we find a formula for the Fibonacci sequence, so that we can calculate fn without having to find all of the previous terms first. We say that a Gibonacci sequence (generalized Fibonacci sequence) Is any sequence a = (ao, a1,a2,..) which satisfies an = an-1 +an-2 for all n 2. Let W denote the set of all Gibonacci sequences. Then W is a subspace of R. (You do not need to turn in a proof of this fact, but you should be able to prove it.) Let 2 is the famous Golden Ratio. Note that By the quadratic formula, and-1/p are both solutions to 2-+ 1, and therefore to r" = rn-1 +n-2 for any n. It follows that a=(1,, 2, . . . . ) and b=(1.-Up, (-Up)*.(-Up). . . . ) are both Gibonacci sequences. Now that we have two Gibonacci sequences with known formulas, we will use a change- of-basis matrix to write f in terms of a and b, and thus find a formula for f (a) Let f (0.1, 1.2.3, ) be the Fibonacci sequence, and let g be the Gibonacci sequence g = (1,0, 1, 1, 2, ). Prove that B-(f.g) is a basis for W (b) With a and b defined as above, prove that B-a, b is a basis for W (c) Find the transition matrix . Hint: It's easier to find Per

Explanation / Answer

I. The Binet Formula:

fn = (1+5)/2 - (1-5)/2

2

where (1+5)/2 is the golden ratio

From the sequence, we know that f3 = 2.

Using Binet's Formula,

f3 = (1+5)/2 - (1-5)/2

5

= (1+3 5+15 +5 5) - (1-3 5+15 -5 5)

8 8

5

= 2

II. f1 + f2 +...+ fn-1 + fn = fn+2 -1.

Proof:

f1 = f3 - f2, (f3 = f1 + f2),

f2 = f4 - f3,

f3 = f5 - f4,

.......................

fn-1 = fn+1 - fn,

fn = fn+2 - fn+1,

By adding each of these terms, we get the desired result.

Example:

f1 + f2 + f3 = f5 - 1

1 + 1 + 2 = 4 = 5 - 1.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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