# Thread: Help with induction for Fibonacci Numbers

1. ## Help with induction for Fibonacci Numbers

Can anyone please help? I don't know if I am doing it right. I am stuck in the inductive step.

Using induction please prove the following formula:

u2 + 2 u4 + 3u6 +...+ n u2n = n u(2n+1) - u2n

where the numbers to the the right of the letter u are subscripts.

So far I proved

Base Case: n = 1

LHS: 1 *u2(1) = 1*u2 = 1*1 =1
RHS: 1* u(2(1)+1) - u2(1) = 1*u3 -u2 = u3-u2 = 2-1 =1

I.H.= Assume for all n to be true
u2 + 2 u4 + 3u6 +... + n u2n = n u(2n+1) - u2n

I.S. Prove for n+1

u2 +2 u4+3 u6+.. +n u2n + (n+1) u2(n+1) = (n+1) u(2(n+1)+1) - u2(n+1)

By I.H. then,

n u(2n+1) - U2n + (n+1) u2(n+1)

and then I get stuck....

2. Originally Posted by Beginner_gurl
Using induction please prove the following formula:

u2 + 2 u4 + 3u6 +...+ n u2n = n u(2n+1) - u2n

...

I.H.= Assume for all n to be true
u2 + 2 u4 + 3u6 +... + n u2n = n u(2n+1) - u2n

I.S. Prove for n+1

u2 +2 u4+3 u6+.. +n u2n + (n+1) u2(n+1) = (n+1) u(2(n+1)+1) - u2(n+1)

By I.H. then,

n u(2n+1) - U2n + (n+1) u2(n+1)
n*u_{2n+1} - u_{2n} + (n + 1)*u_{2(n+1)} = (n + 1)*u_{2(n+1)+1} - u_{2(n+1)}

Rewriting and rearanging these terms, we get:
n(u_{2n+1} + u_{2n+2}) + u_{2n+2} - u_{2n} = nu_{2n+3} + u_{2n+3} - u_{2n+2}

Now we need to try to break these up:

Recall that u_{k} + u_{k+1} = u_{k+2}, we will use this to rewrite many of the above Fibonacci Numbers.

n(u_{2n+1} + u_{2n+2}) + u_{2n+2} - u_{2n} = nu_{2n+3} + u_{2n+3} - u_{2n+2}
nu_{2n+3} + u_{2n+1} + u_{2n} - u_{2n} = nu_{2n+3} + u_{2n+1} + u_{2n+2} - u_{2n+2}
nu_{2n+3} + u_{2n+1} = nu_{2n+3} + u_{2n+1}

Q.E.D.

3. Recall that u_{k} + u_{k+1} = u_{k+2}
How do you prove something like this, without running intio the same kind of trouble Gurl did?

For Fibonacci numbers, and generally recursive sequences, you should use the transfinite induction scheme:

a) Prove for the first term.
b) Suppose true for all terms up to n>1.
c) Prove for n.

Good luck!

4. Hello, Beginner_gurl!

This is a wicked one . . . I had to do Olympic-level gymnastics.

Using induction prove the following formula:

. . F
2 + 2·F4 + 3·F6 + ... + n·F2n .= .n·F2n+1 - F2n

You've already established the Base Case: S
1.

Assume S
k: .F2 + 2·F4 + 3·F6 + ... + k·F2k .= .k·F2k+1 - F2k

2k+2 to both sides:

. . F
2 + 2·F4 + 3·F6 + ... + k·F2k + (k+1)·F2k+2 .= .k·F2k+1 - F2k + (k+1)·F2k+2

The left side is the LHS of S
k+1.

We must show that the right side equals the RHS of S
k+1: .(k+1)·F2k+3 - F2k+2

The right side is: .k·F
2k+1 - F2k + (k+1)·F2k+2 .= .k·F2k+1 - F2k + k·F2k+2 + F2k+2

2n+1: .k·F2k+1 - F2k + k·F2k+2 + F2k+2 + F2k+1 - F2k+1

We have: .k·F
2k+1 + k·F2k+2 + F2k+1 + F2k+2 - F2k - F2k+1

Factor: .k·(F
2k+1 + F2k+2) + (F2k+1 + F2k+2) - (F2k + F2k+1)
. . . . . . . .\_________/ . - . \_________/ . - .\_______/
. . . . . . . .
This is F2k+3 . . . . . This is F2k+3 . . . .This is F2k+2

Then we have: .k·F
2k+3 + F2k+3 - F2k+2

And therefore: . (k+1)·F
2k+3 - F2k+2 . . . . . There!

. . Kids, don't try this at home . . .

Edit: corrected the goof . . . thanks, ec!

5. ## Thanks

I see the light................................thank you!!!!!

6. Originally Posted by Rebesques
How do you prove something like this, without running intio the same kind of trouble Gurl did?

For Fibonacci numbers, and generally recursive sequences, you should use the transfinite induction scheme:

a) Prove for the first term.
b) Suppose true for all terms up to n>1.
c) Prove for n.

Good luck!
This doesn't have to be proven. The Fibonacci Numbers are defined in this way.

7. Originally Posted by Soroban
Hello, Beginner_gurl!

This is a wicked one . . . I had to do Olympic-level gymnastics.

You've already established the Base Case: S
1.

Assume S
k: .F2 + 2·F4 + 3·F6 + ... + k·F2k .= .k·F2k+1 - F2k

2k+2 to both sides:

. . F
2 + 2·F4 + 3·F6 + ... + k·F2k + (k+1)·F2k+2 .= .k·F2k+1 - F2k + (k+1)·F2k+2

The left side is the LHS of S
k+1.

We must show that the right side equals the RHS of S
k+1: .(k+1)·F2k+3 - F2k+2

The right side is: .k·F
2k+1 - F2k + (k+1)·F2k+2 .= .k·F2k+1 - F2k + k·F2k+2 + F2k+2

2n+1: .k·F2k+1 - F2k + k·F2k+2 + F2k+2 + F2k+1 - F2k+1

We have: .k·F
2k+1 + k·F2k+2 + F2k+1 + F2k+2 - F2k - F2k+1

Factor: .k·(F
2k+1 + F2k+2) + (F2k+1 + F2k+2) - (F2k + F2k+1)
. . . . . . . .\_________/ . - . \_________/ . - .\_______/
. . . . . . . .
This is F2k+3 . . . . . This is F2k+3 . . . .This is F2k+2

Then we have: .k·F
2k+2 + F2k+3 - F2k+2

And therefore: . (k+1)·F
2k+3 - F2k+2 . . . . . There!

. . Kids, don't try this at home . . .
I go through all the work of proving it and you come along and make it look more pretty.

Good job once again.

8. Originally Posted by Soroban

Then we have: .k·F
2k+2 + F2k+3 - F2k+2

And therefore: . (k+1)·F
2k+3 - F2k+2 . . . . . There!
There's a slight typo!

9. The Fibonacci Numbers are defined in this way.
Yeap! So its ok.

ps. Is it easier to solve with the trans-induction? Or am I making things difficult?

10. Originally Posted by ecMathGeek
I go through all the work of proving it and you come along and make it look more pretty.

Good job once again.
Don't you hate it when he does that. Soroban has some technique of finding the simplest, prettiest way to do a problem, and then he tops it off with his formatting skills that don't even require LaTex.

It's all good though. Seeing him solve stuff gives me ideas to solve other stuff