Saturday 24 January 2015

Mathematical Induction (summation): $sum^n_{k=1} k2^k =(n-1)(2^{n+1})+2$




I am stuck on this question from the IB Cambridge HL math text book about Mathematical induction. I am sorry about the bad formatting I am new and have no idea how to write the summation sign.



Using mathematical induction prove that the
$$\sum^n_{k=1} k2^k =(n-1)(2^{n+1})+2$$



[correction made]



I tried solving it and got stuck on the let $n=k+1$ part
So first I made $n=1$ and both sides equaled to $2$
then assume $n=k$ and got an expression which I don't know how to write here because of the formatting

then $n=K+1$



Thanks again


Answer



We need to prove that
$$
\sum_{k=1}^nk2^k=(n-1)(2^{n+1})+2
$$
Consider $P_1$ where $k=1$. Left Hand Side (LHS) and Right Hand Side (RHS) are evaluated as follows.
$$\sum_{k=1}^1k2^k=1\times2=2\quad\quad\quad\quad\quad\quad(1-1)(2^2)+2=2$$




Now, we assume that $P_m$ holds for some natural number $m$. (The trick here is that you will need to use this result later.)
$$
\sum_{k=1}^mk2^k=(m-1)(2^{m+1})+2
$$



It must be shown that $P_{m+1}$ holds too. Let us prove it. The RHS, which is relatively easier is
$$
\begin{align*}
[(m+1)-1](2^{m+2})+2&=m(2^{m+2})+2

\end{align*}
$$
What we need to do is to show that the LHS has this form:



$$
\begin{align*}
\sum_{k=1}^{m+1}k2^k&=\sum_{k=1}^mk2^k+(m+1)2^{m+1}\\
&=(m-1)(2^{m+1})+2+(m+1)2^{m+1}\\
&=(m-1)(2^{m+1})+(m+1)2^{m+1}+2\\&=(2m)(2^{m+1})+2\\
&=m(2^{m+2})+2

\end{align*}
$$
Since $P_1$ true, $P_m$ true $\rightarrow P_{m+1}$ true, by Mathematical Induction, $P_k$ true for $k=1, 2, \cdots$



Proven


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...