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:

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.

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!

Hello, Beginner_gurl!

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

Quote:

---

Using induction prove the following formula:

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

---

You've already established the Base Case: S1.

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


Add (k+1)·F2k+2 to both sides:

. . F2 + 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 Sk+1.

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


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

Add and subtract F2n+1: .k·F2k+1 - F2k + k·F2k+2 + F2k+2 + F2k+1 - F2k+1

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

Factor: .k·(F2k+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·F2k+3 + F2k+3 - F2k+2

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


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

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

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

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.

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

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


Add (k+1)·F2k+2 to both sides:

. . F2 + 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 Sk+1.

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


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

Add and subtract F2n+1: .k·F2k+1 - F2k + k·F2k+2 + F2k+2 + F2k+1 - F2k+1

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

Factor: .k·(F2k+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·F2k+2 + F2k+3 - F2k+2

And therefore: . (k+1)·F2k+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.

Quote:

---

Originally Posted by Soroban

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

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

---

There's a slight typo!

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

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