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:


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...)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.