Recall that the fibonacci sequence is defined as i know how

Recall that the fibonacci sequence is defined as ...

i know how to solve induction proofs but dont know about this one. can someone proof this step by step?

Problem 1.27 Recall that the Fibonacci sequence is defined as and fn fn-1 fn-2 for n 2 2 Prove by generalized mathematical induction that fn where 1 V5 is the golden ratio. (This is known as de Moivre\'s formula

Solution

An incorrect proof. Let’s start by asking what’s wrong with the following attempted proof that, in fact, fn = r^ n2 . (Not just that fn r ^n2 .) • Incorrect proof (sketch): We proceed by induction as before, but we strengthen P(n) to say “fn = r^ n2 .” The induction hypothesis is that P(1), P(2), . . ., P(n) are all true. We assume this and try to show P(n + 1). That is, we want to show fn+1 = r ^n1 . Proceeding as before, but replacing inequalities with equalities, we have

fn+1 = fn + fn1

= r ^(n2) + r^( n3)

= r ^n3 (r + 1)

= r ^(n3 )*r^ 2

= r ^n1 , where we used the induction hypothesis to go from the first line to the second, and we used the property of r that r^ 2 = r + 1 to go from the third line to the fourth. The last line is exactly the statement of P(n + 1).

The funny thing is: there’s nothing wrong with the parts of this “proof” that we wrote out explicitly. The problem came earlier: we don’t have a correct base case . In fact, the induction would have been fine if only the base case had been correct; but instead, we have a proof that starts out with an incorrect statement (the wrong base case), and so it fails completely.

An exact formula. Still, so much of this wrong argument seems to work that we’re tempted to try salvaging it. If we could just modify the formula a bit so it worked on the base cases of 1 and 2, everything else would be fine. So suppose instead of fn = r ^n2 (which is false), we tried proving fn = ar^n for some value of a yet to be determined. (Note that r^ n2 is just ar^n for the particular choice a = r 2 .) Could there be a value of a that works?

Unfortunately, no. We’d need to have 1 = f1 = ar and 1 = f2 = ar^2 . But by the definining property of r, we have

1 = f2 = ar^2 = a(r + 1) = ar + a.

Thus we have 1 = ar

1 = ar + a

which cannot be satisfed by any value of a.

But there one more trick we can still deploy. x ^2 = x + 1 is a quadratic equation, and it has two solutions: r = (1+ 5)/ 2 and s = (1 5)/ 2 . Any statement P(n) of the form fn = ar^n + bs^n (for any choices of a and b) would work just fine in the induction step: once we assume P(1), . . . , P(n) are all true, we can write

fn+1 = fn + fn1

= ar^n + bs^n + ar^n1 + bs^n1

= ar^n + ar^n1 + bs^n + bs^n1

= ar^n1 (r + 1) + bsn1 (s + 1)

= arn1 · r^ 2 + bsn1 · s^ 2

= ar^n+1 + bs^n+1 ,

where we used the induction hypothesis to go from the first line to the second, and we used the property of r and s that r^ 2 = r + 1 and s^ 2 = s + 1 to go from the fourth line to the fifth. The last line is exactly the statement of P(n + 1). So now we just need to see if the as-yet undetermined constants a and b can be chosen so that the base cases P(1) and P(2) work. To make these work, we need

1 = f1 = ar + bs

1 = f2 = ar^2 + bs^2 = a(r + 1) + b(s + 1)

Solving these two equations in the two unknowns a and b, we find that there is a solution: a = 1/ 5 and b = 1/ 5. Thus, we arrive at a formula for the Fibonacci numbers:

fn = 1 5 ((1 + 5)/ 2)) ^n 1 5(( 1 5)/ 2 )^n .