Induction proof: $\sum_{k=1}^n k^32^k \leq n^32^{n+1}$

Question

Having trouble solving the induction proof for:

$$\sum_{k=1}^n k^32^k \leq n^32^{n+1}$$

EDIT: supposed to be $k^32^k$

Why induction? Rather use $$\sum_{k=1}^n k^32^k\leqslant\sum_{k=1}^n n^32^k=n^3\sum_{k=1}^n 2^k=n^3(2^{n+1}-2)\leqslant n^32^{n+1}.$$ — Did, Mar 09 '16 at 21:10

jameselmore · Answer 1 · 2016-03-09T20:46:44.257

1

Hint: $$\sum_{k=1}^{n+1}k^3 2^k = \sum_{k=1}^nk^32^k + (n+1)^3 2^{n+1} \leq n^32^{n+1} + (n+1)^3 2^{n+1} = \dots$$

edited Mar 09 '16 at 20:46

answered Mar 09 '16 at 20:35

jameselmore

5,207

score 0 · Answer 2 · answered Mar 09 '16 at 20:37

For $n=1$ the claim is clear.

Suppose $\sum_{k=1}^nk^22^k\leq n^32^{n+1}$. Now

\begin{align} \sum_{k=1}^{n+1}k^22^k&=\sum_{k=1}^nk^22^k+(n+1)^22^{n+1}\\&\leq n^32^{n+1}+(n+1)^22^{n+1}\\ &=(n^3+(n+1)^2)2^{n+1}\\ &=(n^3+n^2+2n+1)2^{n+1}\\ &\leq(n^3+3n^2+3n+1)2^{n+2}\\ &=(n+1)^32^{(n+1)+1} \end{align}

And the proof is complete.

Induction proof: $\sum_{k=1}^n k^32^k \leq n^32^{n+1}$

2 Answers2