0

Can someone please check this for me? Like the wordings and working. Thanks

The question is:

Use Mathematical Induction to prove that $$\sum_{i=1}^{n}i2^i=(n-1)2^{n+1}+2.$$

My answer:

$$\sum_{i=1}^{n}i2^i=(n-1)2^{n+1}+2.$$

My answer:

let $P(n)=\sum_{i=1}^{n}i2^i=(n-1)2^{n+1}+2.$

Basis Step: $P(1)$ true $1*2^1=(1-1)2^{1+1}+2$, which gives $2=2$.

Inductive Step: $P(k)$ true

$k*2^k=(k-1)2^{k+1}+2$

Then $P(k+1)$ true

$\begin{array}{rcl} k*2^k+k+1*2^{k+1}&=&k2^{k+2}+2\\ (k-1)2^{k+1}+2+(k+1)2^{k+1}&=&k2^{k+2}+2 \\ 2^{k+1} k-2^{k+1}+2^{k+1} k+2^{k+1}+2 &&\\ 2^{k+1} k+2^{k+1} k+2 &&\\ 2*2^{k+1} k+2 &&\\ 2^{k+2}k+2 &&\\ k2^{k+2}+2&=&\text{RHS} \end{array}$

$∴P(n)$ is true for all nonnegative integers $n$.

Teddy38
  • 3,309
Sean Paul
  • 45
  • Mainly ok, just some minor stylistic issues. You defined $P(n)$ to be $$P(n)=\sum_{i=1}^{n}i2^i=(n-1)2^{n+1}+2.$$ Maybe it should be made clear that $P(n)$ is the statement that $$\sum_{i=1}^{n}i2^i=(n-1)2^{n+1}+2$$ is true for $n$ and that the base case is $P(1)$ and the inductive case assumes $P(k)$ and proves $P(k+1)$. Like I said, just stylistic points. – Teddy38 Oct 10 '17 at 12:00

3 Answers3

0

Short way:

Induction: $$S_n=S_{n-1}+n2^n=\color{green}{((n-2)2^n+2)+n2^n=(n-1)2^{n+1}+2}$$

and basis:

$$S_0=0=(0-1)2^0+2.$$

  • I admit it is terse, but it focuses on the crux of the question, which is the green identity. –  Oct 10 '17 at 12:31
0

Your thinking is probably OK, but your presentation of it is a bit of a mess.

First of all you should be clearer that $P(n)$ is a statement. Using $=$-sign gives the impression that $P(n)$ is in fact numerical. Instead you could use colon in the definition:

$$P(n): \sum_{j=1}^n j2^j= (n-1)2^{n+1}+2$$

Then in the induction step you're missing summation signs. In addition you introduces the goal RHS prematurely in the chain of equations and drops equality signs. You're transformations should be a chain of equalities reaching to the RHS. That is given $P(k)$ then

$\begin{array}{rcl} \sum_1^{k+1} j2^j = \\ \sum_1^{k} j2^j + (k+1)2^{k+1} = \\ (k-1)2^{k+1}+2+(k+1)2^{k+1}&=& \\ 2^{k+1} k+2^{k+1} k+2 &=&\\ 2*2^{k+1} k+2 &=&\\ 2^{k+2}k+2 &=&k2^{k+2}+2\end{array}$

That is $P(k+1)$.

skyking
  • 16,654
0

Observe that $P(n)$ is not the sum but the proposition $$ \begin{align} P(n):&\quad \sum_{i=1}^{n}i2^i=(n-1)2^{n+1}+2\\ \text{For $n=1$ we have}\\ P(1):&\quad \sum_{i=1}^{1}i2^i=(1-1)2^{1+1}+2\Longrightarrow 2=2\;\text{true}\\ \text{assuming }P(n)\text{ is true we have}\\ P(n+1):&\quad \sum_{i=1}^{n+1}i2^i=(n+1-1)2^{n+1+1}+2\\ &\quad \color{red}{\sum_{i=1}^{n}i2^i}+(n+1)2^{n+1}=\color{red}{(n-1)2^{n+1}+2}+(n-1)2^{n+1}+2^{n+2}\\ &\quad (n+1)2^{n+1}=(n-1)2^{n+1}+2^{n+2}\\ &\quad (n+1)2^{n+1}=2^{n+1}(n-1+2)\\ &\quad (n+1)2^{n+1}=2^{n+1}(n+1)\\ \end{align} $$ and then $P(n+1)$ is true and then $P(n)$ is true for all $n$

alexjo
  • 14,976