# Proof by Induction

• Apr 26th 2011, 04:21 AM
ananas1301
Proof by Induction
Hey guys,

ive got a question to solve:
It goes like this:
Using mathematical Induction, prove that

SUM(r=1->n) of (r+1)2^r-1 = n(2^n)

Now the basic step is easy so im not gonna bother typing it here now but later on:

I get that:

(Let P(k) be true so:)
Sum(r=1->k) of (r+1)2^r-1 = k(2^k)

Now prove that P(k+1) is true:

Sum(r=1->k+1) of (r+1)2^r-1 = (k+1)(2^(k+1))

The Lefthandside of the equation above says:
Sum(r=1->k+1) of (r+1)2^r-1
We can expand this to be
Sum(r=1->k) of (r+1)2^r-1 + ((k+1)+1)2^(k+1)-1
Using our assumption of the beginnig we can say now that:

k(2^k) + ((k+1)+1)2^(k+1)-1 must equal this if i havenīt done any mistakes: (k+1)(2^(k+1)), doesnīt it.

But somehow i canīt get that,
if some could just show me the last step then iīd be fine with that.

Hope i`ve expressed my self correctly in that question. (Couldnīt really get used to the commands quick menu; sorry)

Cheers guys
• Apr 26th 2011, 05:04 AM
topsquark
Quote:

Originally Posted by ananas1301
k(2^k) + ((k+1)+1)2^(k+1)-1 must equal this if i havenīt done any mistakes: (k+1)(2^(k+1)), doesnīt it.

So far so good. :)

Now
http://latex.codecogs.com/png.latex?... = (2k + 2)2^k
What can you do with this?

-Dan
• Apr 26th 2011, 05:15 AM
ananas1301
This is how far I just got a minute ago as well;

but I am stuck there and canīt get it to be (k+1)(2^(k+1)).

Would it be fine ich I just state an example, where I replace the k with a fixed value!?

(2k+2)2^k has to be fromed to look like that: (k+1)(2^(k+1))
• Apr 26th 2011, 05:50 AM
poirot
Quote:

Originally Posted by ananas1301
Would it be fine ich I just state an example, where I replace the k with a fixed value!?

That reveals a fatal misunderstanding of proof by induction. You have to show, if the result is true for a general particular integer k, it is true for k +1.
(2k+2)2^k =2.2^k(k+1)=(k+1)2^(k+1).
• Apr 26th 2011, 06:03 AM
ananas1301
Quote:

Originally Posted by poirot
That reveals a fatal misunderstanding of proof by induction. You have to show, if the result is true for a general particular integer k, it is true for k +1.
(2k+2)2^k =2.2^k(k+1)=(k+1)2^(k+1).

Thatīs what I thought as well, it is just not the point of the induction.

I donīt get that step you have done
(2k+2)2^k =2.2^k(k+1)=(k+1)2^(k+1)

I know i could just write that down, but i want to understand it as well.

Can you explain it in more detail please?

Would be really nice, thank you

EDIT:

No i got it now.

The last step was fairly easy but i just didnīt really know what that dot between the two twos was meant to be.

Anyway thank you!!!
• Apr 26th 2011, 06:48 AM
poirot
its the european sign for multiplication