I have a homework problem to prove the following via induction: $$\sum_{i=1}^n i^22^{n-i} = 2^{n+3}-2^{n+1}-n^2-4n -6$$ The base case is true. I generated the below using $s_k+a_{k+1}=s_{k+1}$: $$ 2^{k+3}-2^{k+1}-k^2-4k-6+(k+1)^22^{n-(k+1)}=2^{k+4}-2^{k+2}-(k+1)^2-4(k+1)-6 $$ which I've simplified down to:
$$ (k+1)^22^{n-(k+1)}=-2k-5 $$ However, I have no idea what to do with $n$ and I haven't been able to figure out what to Google to get a hint. So my questions are:
- What do you call it when you have $n$ on the left side of summation notation like this (i.e. what search terms might help)?
- Am I using the correct process, or am I way off track? (And/or have I made any errors in my simplification?)
- What do I do with $n$? I tried making $n=k+1$, which seemed logical to me, but it doesn't work out.
Thanks for any suggestions/hints you have!
I will assume that you have already performed the base case.
Assume this holds for $k \in \mathbb{N}.$ We see that
$$\sum_{i=1}^{k+1} i^2 2^{k+1 - i} = 2\sum_{i=1}^{k+1} i^2 2^{k-i}$$ $$=2\left((k+1)^2 2^{-1} + \sum_{i=1}^{k} i^2 2^{k-i}\right),$$ which by our inductive hypothesis $$=2\left((k+1)^2 2^{-1} + 2^{k+3} - 2^{k+1} - k^2 - 4k - 6\right)$$ $$=(k+1)^2 + 2^{(k+1)+3} - 2^{(k+1)+1} - 2k^2 - 8k - 12$$ $$=k^2 + 2k + 1 + 2^{(k+1)+3} - 2^{(k+1)+1} - 2k^2 - 8k - 12$$ $$=2^{(k+1)+3} - 2^{(k+1)+1} - k^2 - 6k - 11.$$
Hence, it suffices to show that
$$-k^2 - 6k - 11 = -(k+1)^2 - 4(k+1) - 6.$$
We see that $$-(k+1)^2 - 4(k+1) - 6 = -(k^2 + 2k + 1) - 4k -4 - 6 = -k^2 - 2k - 1 -4k -4 -6$$ $$=-k^2 - 6k - 11,$$
And thus our above statement holds for $k+1.$ Hence, by the principle of mathematical induction, our statement holds for all $n \in \mathbb{N}.$