Help with induction for Fibonacci Numbers

• Apr 22nd 2007, 08:23 PM
Beginner_gurl
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....:confused::eek:
• Apr 22nd 2007, 10:58 PM
ecMathGeek
Quote:

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.
• Apr 23rd 2007, 04:11 AM
Rebesques
Quote:

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? :p

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!
• Apr 23rd 2007, 04:47 AM
Soroban
Hello, Beginner_gurl!

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

Quote:

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!
• Apr 23rd 2007, 05:35 AM
Beginner_gurl
Thanks
I see the light................................thank you!!!!!:D
• Apr 23rd 2007, 06:26 AM
ecMathGeek
Quote:

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

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.
• Apr 23rd 2007, 06:29 AM
ecMathGeek
Quote:

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. :mad:

Good job once again.
• Apr 23rd 2007, 06:31 AM
ecMathGeek
Quote:

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!
• Apr 23rd 2007, 06:49 AM
Rebesques
Quote:

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

ps. Is it easier to solve with the trans-induction? Or am I making things difficult? :o
• Apr 23rd 2007, 07:37 AM
Jhevon
Quote:

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

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:D