# Math Help - Proof by Induction

1. ## 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

2. 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
$k(2^k) + (k + 2)2^k = (k + k + 2)2^k = (2k + 2)2^k$
What can you do with this?

-Dan

3. 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))

4. 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).

5. 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!!!

6. its the european sign for multiplication