Proving the Induction Step: \sum_{j=1}^{k+2} j \cdot 2^j = (k+2)\cdot 2^{k+4}+2

[jonroberts74]

Homework Statement

prove by induction $$\sum_{j=1}^{n+1} j \cdot 2^j = n \cdot 2^{n+2}+2; n \ge 0$$2. The attempt at a solution

P(0)

$$\sum_{j=1}^{0+1} j \cdot 2^j = 0 \cdot 2^{0+2}+2$$

$$2+2$$

here is where I need some help

is P(k)

$$\sum_{j=1}^{k+1} j \cdot 2^j = (k+1) \cdot 2^{k+3}+2$$ ??

then

P(k+1) $$\sum_{j=1}^{k+2} j \cdot 2^j = (k+2)\cdot 2^{k+4}+2$$

 

[LCKurtz]

Homework Statement

prove by induction $$\sum_{j=1}^{n+1} j \cdot 2^j = n \cdot 2^{n+2}+2; n \ge 0$$





2. The attempt at a solution

P(0)

$$\sum_{j=1}^{0+1} j \cdot 2^j = 0 \cdot 2^{0+2}+2$$

$$2+2$$

here is where I need some help

is P(k)

$$\sum_{j=1}^{k+1} j \cdot 2^j = (k+1) \cdot 2^{k+3}+2$$ ??

No. Copy your original problem (the first equation above) exactly with $n = k$.

 

[jonroberts74]

No. Copy your original problem (the first equation above) exactly with $n = k$.

$$\sum_{j=1}^{k} j \cdot 2^j = (k) \cdot 2^{k+2}+2$$ why this when the sum goes to n+1??

 

[LCKurtz]

What part of "copy it exactly" don't you understand?

 

[jonroberts74]

I see what I did wrong in my reply. it was a simple mistake, hostility doesn't help. I'll figure it out. thanks

 

[Fredrik]

You want to prove that for all non-negative integers n, we have $\sum_{j=1}^{n+1} j \cdot 2^j = n \cdot 2^{n+2}+2$. For each non-negative integer n, let P(n) be the statement $\sum_{j=1}^{n+1} j \cdot 2^j = n \cdot 2^{n+2}+2$. Let the scope of the $\forall$ symbol ("for all") be the set of non-negative integers. The result that you want to prove can now be stated as
$$\forall n~P(n)$$ To prove this is to prove all of the infinitely many statements P(0), P(1), P(2),... The idea behind induction proofs is that you can do that in a finite number of steps. All you have to do is to prove the following two statements:
\begin{align}
&P(0)\\
&\forall k~\big(P(k)\Rightarrow P(k+1)\big)
\end{align} When you get to the second step, you don't really have to think about what P(k) or P(k+1) is. You just use the definition. It's appropriate to think of P as a kind of "function" that takes integers to statements.

I would recommend that you always write down a definition of P(k) for all the relevant k when you start an induction proof. You know that your definition is OK if it turns the statement that you want to prove into $\forall n~P(n)$. The theorem has to be a statement of this form, if induction is to be used.

 

[LCKurtz]

What part of "copy it exactly" don't you understand?

I see what I did wrong in my reply. it was a simple mistake, hostility doesn't help. I'll figure it out. thanks

It isn't hostility. It is my expressing frustration with with your carelessness in executing an extremely simple task.

 

[jonroberts74]

It wasn't carelessness. I've been working on my schoolwork for 16 hours a days for the past month. It was a simple mistake. I appreciate the help.

 

[LCKurtz]

So, after you wrote down P(k) and P(k+1), were you able to show P(k) implies P(k+1)?

 

[jonroberts74]

so p(k) is

$$\sum_{j=1}^{k+1} = k \cdot 2^{k+2} +2$$

so p(k+1)

is

$$\sum_{j=1}^{k+2} = (k+1) \cdot 2^{k+3}+2$$

shifting the index

$$\displaystyle{\sum_{j=1}^{k+2}}j 2^j=\displaystyle{\sum_{j=1}^{k+1}}j 2^j+(k+2) \cdot 2^{k+2}$$

correct?

now

$$\displaystyle{\sum_{j=1}^{k+1}}j 2^j+(k+2)2^{k+2}=(k \cdot 2^{k+2}+2) + (k+2)2^{k+2}$$

$$= k \cdot 2^{k+2}+k \cdot 2^{k+2} + 2 \cdot 2^{k+2} + 2$$

$$=2\cdot k \cdot 2^{k+2} + 2 \cdot 2^{k+2} + 2$$

$$= (2k+2)2^{k+2}+2$$

$$= (k+1)2^{k+3} + 2$$

??

 

[LCKurtz]

I don't think you need the ??'s at the end. I think you know it is correct.