# Solution check: summation inequality proof by induction

I'm not sure if what I've done works or if it's proof enough. (I need to prove that the inequality is true $\forall n \in \mathbb{N}$).

$\sum_{i=n}^{2n} \frac{i}{2^i} \leq n$

$P(1)$ works. I assume the inequality to be true for $n$.

$(\sum_{i=n}^{2n} \frac{i}{2^i}) + 1\leq n + 1$

$(\sum_{i=n}^{2n} \frac{i}{2^i}) + \frac{2n+1}{2^{2n + 1}}\leq (\sum_{i=n}^{2n} \frac{i}{2^i}) + 1\leq n + 1$

I'm stuck.

To be proved: $\displaystyle \sum_{i=n}^{2n} \frac{i}{2^i} \leq n$

Base case: $n=1$, $\displaystyle \sum_{i=1}^{2} \frac{i}{2^i}=1 \leq 1$ which works.

Assume that for some $n$, $\displaystyle \sum_{i=n}^{2n} \frac{i}{2^i} \leq n$

Consider, for $n+1$, $\displaystyle \sum_{i=n+1}^{2(n+1)} \frac{i}{2^i} \leq n+1$

$\displaystyle \sum_{i=n+1}^{2n+2} \frac{i}{2^i} \leq n+1$

$\displaystyle \sum_{i=n}^{2n} \frac{i}{2^i}+\frac{2n+1}{2^{2n+1}}+\frac{2n+2}{2^{2n+2}}-\frac{n}{2^{n}} \leq n+1$

Consider now the inequality:

$\frac{2n+1}{2^{2n+1}}+\frac{2n+2}{2^{2n+2}}-\frac{n}{2^{n}}≤1$

Prove this inequality to be true, and in conjunction with the assumption and the base case the inductive proof will be complete.

EDIT: To be neat and tidy, you might want to, following your original line of thinking, say:

Assume that for some $n$, $\displaystyle \sum_{i=n}^{2n} \frac{i}{2^i} \leq n$

Then, $\displaystyle \sum_{i=n}^{2n} \frac{i}{2^i} +1 \leq n+1$

But, $\frac{2n+1}{2^{2n+1}}+\frac{2n+2}{2^{2n+2}}-\frac{n}{2^{n}}≤1$

And so, $\displaystyle \sum_{i=n}^{2n} \frac{i}{2^i} +\frac{2n+1}{2^{2n+1}}+\frac{2n+2}{2^{2n+2}}-\frac{n}{2^{n}} \leq n+1$

Therefore, $\displaystyle \sum_{i=n+1}^{2(n+1)} \frac{i}{2^i} \leq n+1$.

Then, you can make the proper conclusion statement regarding induction (the inequality holds for base case $n=1$, and so holds for...)