Induction proof for $ \sum\limits_{i=1}^n i^22^i = n^22^{n+1}-n2^{n+2}+3 \cdot2^{n+1}-6 $

Question

I am currently writing a proof for the following problem $$ \sum\limits_{i=1}^n i^22^i = n^22^{n+1}-n2^{n+2}+3*2^{n+1}-6 $$

By induction on $n\ge0$

My question isn't really about how to correctly prove this, but I am running into some trouble finishing the $(n+1)$ part of the proof. I have $$\sum\limits_{i=1}^{n+1} i^22^i=(n+1)^22^{n+2}-(n+1)2^{n+3}+3*2^{n+2}-6$$

So, I end up up with

$$\sum\limits_{i=1}^{n+1} i^22^i=\sum\limits_{i=1}^n i^22^i+(n+1)^22^{n+1}$$

I am really having trouble simplifying from this point in order to prove that $(n+1)$ holds. I am having trouble with the algebra to the point where I am starting to think I must be making some other kind of mistake.

Answer 1

Assume formula is true for $n=k$, i.e. $$\begin{align} \require{cancel}\sum_{i=1}^{k}i^22^i&=k^22^{k+1}-k2^{k+2}+3\cdot 2^{k+1}-6\\ &=(k^2-2k+3)2^{k+1}-6\end{align}$$ Adding the $(k+1)$-th term: $$\begin{align} \sum_{i=1}^{k+1}i^22^i&=\overbrace{ \left[( k^2-2k+3) 2^{k+1} -6 \right] } ^{\sum_{i=1}^k i^2 2^i} +\overbrace{(k+1)^22^{k+1}}^{(k+1)\text{-th term}}\\ &=\left[ (k^2-\cancel{2k}+3)+(k^2+\cancel{2k}+1)\right]2^{k+1}-6\\ &=(k^2+\color{red}{2})2^{k+2}-6\\ &=\left[\underbrace{k^2+\color{green}{2k}+\color{red}{1}}-2(\color{green}{k}+\color{red}{1})+\color{red}{3}\right]2^{k+2}-6\\ &=\left[(k+1)^2-2(k+1)+3\right]2^{k+2}-6\\ &=(\overline{k+1})^22^{\overline{k+1}+1}-(\overline{k+1})2^{\overline{k+1}+2}+3\cdot 2^{\overline{k+1}+1}-6\end{align}$$ i.e. formula is also true for $n=k+1$.

It is obvious that the formula is true for $n=1$.

Hence, by induction, formula is true for all positive integers $n$. $\quad \blacksquare$

Answer 2

Setting $n=m,$

$$S_m= \sum\limits_{i=1}^m i^22^i = m^22^{m+1}-m2^{m+2}+3\cdot2^{m+1}-6 $$

We need $$ S_{m+1}=\sum\limits_{i=1}^{m+1} i^22^i =(m+1)^22^{m+2}-(m+1)2^{m+3}+3\cdot2^{m+2}-6$$

$$T_{m+1}=S_{m+1}-S_m=2^{m+1}[2(m+1)^2-4(m+1)+6-\{m^2-2m+3\}]=\cdots=2^{m+1}(m+1)^2$$

Answer 3

Probably a good way to start would be to collect all the terms with powers of $2$, not forgetting that $2^{n+2}=2\times2^{n+1}$; then write the quadratic in terms of $(n+1)^2$ and $n+1$, because you know you need them there. Thus: $$\eqalign{n^22^{n+1}&{}-n2^{n+2}+3\times2^{n+1}-6+(n+1)^22^{n+1}\cr &=(n^2-2n+3+(n+1)^2)2^{n+1}-6\cr &=(n^2+2)2^{n+2}-6\cr &=((n+1)^2-2(n+1)+3)2^{n+2}-6\cr &=(n+1)^22^{n+2}-(n+1)2^{n+3}+3\times2^{n+2}-6\ .\cr}$$