How to show $\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+...+\frac{n}{2^n}<2$ using induction

Question

I´d like to show that $$\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+...+\frac{n}{2^n}+\frac{n+1}{2^{n+1}}<2$$ using the fact that $$\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+...+\frac{n}{2^n}<2$$

I guess the answer use transitivity of natural numbers and the inequality $$n+1<2^n$$ In this case, i can use it because i suppose it for natural n such that n>1. I'd like to have something like $$....+(n+1)<2(2^{n+1})$$ because you can divide both sides by $2^{n+1}$, and so, you get $$...+\frac{n+1}{2^{n+1}}<2$$

I´ve noticed that $$2^n+n+1<2^n+2^n=2^{n+1}<2(2^{n+1})$$ and it leads me to think $$...+n+1<2^n+n+1$$ i´ve tried dividing both sides ,of the inequality i´m assuming as a fact, by $2^n/2$ in order to get $2^n$

in the right hand of the inequality and then, add $n+1$ to both sides: $$(\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+...+\frac{n}{2^n})\frac{2^n}{2}+n+1<2(\frac{2^n}{2})+n+1=2^n+n+1$$ but at this part i get stuck because if i continue it doesn't lead me to what i´d like to show.

Please, help me. I hope someone here have already proved this before, because i don't find anything similar to this at any part of the web.

Answer 1

Hint: $$\begin{aligned} &\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+...+\frac{n}{2^n}+\frac{n+1}{2^{n+1}}\\ =&\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...+\frac{1}{2^n}+\frac{1}{2^{n+1}}\right) \\ &+\left(\frac{1}{4}+\frac{2}{8}+...+\frac{n-1}{2^n}+\frac{n}{2^{n+1}}\right)\\ \end{aligned}$$

Now try to show each bracket is less than $1$, the second bracket looks like a good candidate for the induction hypothesis.

Answer 2

In order to use induction in the way you tried, you may show a stronger inequality which implies the original one, such as $$\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\dots+\frac{n}{2^n}\leq 2-\frac{n+a}{2^n}$$ where $a$ is a non-negative constant to be determined.

The basic step: for $n=1$ is $\frac{1}{2}\leq 2-\frac{1+a}{2}$, that is $a\leq 2$.

Then, at the inductive step, for $n\geq 1$, $$\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\dots+\frac{n}{2^n}+\frac{n+1}{2^{n+1}}\leq \left(2-\frac{n+a}{2^n}\right)+\frac{n+1}{2^{n+1}}\stackrel{?}{\leq}2-\frac{n+1+a}{2^{n+1}}$$ and the last inequality simplifies to $a\geq 2$.

So $a=2$ works!!

Answer 3

If you can drop the method by induction you may also proceed as follows:

For $|x| < 1$ you have $$\frac{1}{1-x}= \sum_{n=0}^{\infty} x^n \Rightarrow \frac{1}{(1-x)^2}= \sum_{n=1}^{\infty} n \cdot x^{n-1} \Rightarrow \color{blue}{\frac{x}{(1-x)^2}= \sum_{n=1}^{\infty} n \cdot x^{n}}$$ For $x=\frac{1}{2}$ you have $$\color{blue}{\frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \cdots} = \frac{\frac{1}{2}}{\left(1-\frac{1}{2}\right)^2} \color{blue}{= 2} \Rightarrow \boxed{\sum_{n=1}^N \frac{n}{2^n}< 2} \mbox{ for all } N \in \mathbb{N}$$