You are doing it correctly, but you need to manipulate that fibonacci expression. You can do that by looking at the non-inductive proof I gave. And following with the same reasoning.

Printable View

- May 28th 2006, 11:02 AMThePerfectHacker
You are doing it correctly, but you need to manipulate that fibonacci expression. You can do that by looking at the non-inductive proof I gave. And following with the same reasoning.

- May 28th 2006, 04:43 PMNatasha1Quote:

Originally Posted by**ThePerfectHacker**

- May 28th 2006, 05:40 PMNatasha1
Is this better???

Step 1: For n = 1, we have

Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

Since there is a such as,

Then proof it hold for . But the expression,

But,

Thus,

Thus, it hold true for .

Hence the equation holds true for n = k + 1 - May 29th 2006, 01:58 AMCaptainBlackQuote:

Originally Posted by**Natasha1**

.

Now:

,

so:

.

Which proves that if the statement is true for it is true for

.

RonL - May 29th 2006, 07:48 AMSoroban
Hello, Natasha!

An*inductive*proof requires some world-class acrobatics . . .

Quote:

I need to prove**by induction**that for the Fibonacci sequence:

. . . being a Fibonacci number

Verify . . . yes!

Assume is true: .

. . and we will try to prove

Since and

becomes:

Expand:

We have:

Factor:

. . . . . . . . . . .This is

An we have:

Multiply by

. . .*ta-DAA!*. . . This is