# Proving an inequality without induction

• Jun 25th 2013, 02:42 PM
Ragnarok
Proving an inequality without induction
Hello, I have proved this statement using induction, but I am just wondering if you can do it without induction:

$\sum_{k=1}^n\frac{k}{2^k}<2$

for all $n\geq 1$.

I'm wondering if there is another way since I heard that induction is "not elegant". (Wondering)

Thanks!
• Jun 25th 2013, 04:11 PM
emakarov
Re: Proving an inequality without induction
Induction in general is very elegant. In this case, obviously, it requires strengthening the induction statement from $\sum_{k=1}^n\frac{k}{2^k}<2$ to $\sum_{k=1}^n\frac{k}{2^k}<2-E(n)$ for some positive expression E(n). This method illustrates the reason for the inequality and shows how close the sum gets to 2. I would say this is very illuminating way of proving the inequality. Which E(n) did you use?

Another way is a standard trick from generating functions. Let $f(x)=\sum_{k=0}^\infty\frac{x^k}{2^k} =\frac{2}{2-x}$. Then $f'(x)=\sum_{k=1}^\infty\frac{kx^{k-1}}{2^k}$ for $x<2$ (see Wikipedia), so $f'(1)=\sum_{k=1}^\infty\frac{k}{2^k}$.
• Jun 29th 2013, 06:46 PM
Soroban
Re: Proving an inequality without induction
Hello, Ragnarok!

Quote:

Hello, I have proved this statement using induction,
but I am just wondering if you can do it without induction:

. . . $\displaystyle\sum_{k=1}^n\frac{k}{2^k}<2$

We have: . . . . . $S \;=\;\frac{1}{2} + \frac{2}{2^2} + \frac{3}{2^3} + \frac{4}{2^4} + \hdots + \frac{n}{2^n}$

Multiply by $\tfrac{1}{2}:\;\frac{1}{2}S \;=\;\qquad \frac{1}{2^2} + \frac{2}{2^3} + \frac{3}{2^4} + \hdots + \frac{n-1}{2^n} + \frac{n}{2^{n+1}}$

Subtract: . . . . $\frac{1}{2}S \;=\;\underbrace{\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + \hdots + \frac{1}{2^n}}_{\text{geometric series}} - \frac{n}{2^{n+1}}$

. . The geometric series has a sum of: $1 - \tfrac{1}{2^n}$

We have: . $\frac{1}{2}S \;=\;\left(1 - \frac{1}{2^n}\right) - \frac{n}{2^{n+1}}$

. . . . . . . . $\frac{1}{2}S \;=\;\frac{2^{n+1} - 2 - n}{2^{n+1}}$

Multiply by 2: . $S \;=\;\frac{2^{n+1} - 2 - n}{2^n}$

. . . . . . . . . . . $S \;=\;\frac{2^{n+1}}{2^n} - \frac{2+n}{2^n}$

. . . . . . . . . . . $S \;=\;2 - \frac{n+2}{2^n}$

Since the fraction is positive, $S \:<\:2.$
• Jun 30th 2013, 10:45 AM
Ragnarok
Re: Proving an inequality without induction
Thank you both so much! I'm sorry I didn't get back to you sooner. emakarov, I tried to put my proof in the form you described and I couldn't - in fact, I couldn't even reproduce the proof. So maybe I got something wrong. I'm going to try again. Soroban, I love your answer, thank you so much.
• Jun 30th 2013, 03:04 PM
emakarov
Re: Proving an inequality without induction
I am not sure my method, which is supposed to work by proving $\sum_{k=1}^n k/2^k<2-E(n)$ for some E(n), is feasible. However, Soroban's final equality can be proved by induction.
• Jun 30th 2013, 03:05 PM
Ragnarok
Re: Proving an inequality without induction
Okay, I think I got it. Here's what I did for the inductive step:

$\sum_{k=1}^n\frac{k}{2^k}<2$

$\Longleftrightarrow\frac{1}{2^n}\sum_{k=1}^n2^{n-k}k<2$

$\Longleftrightarrow\sum_{k=1}^n2^{n-k}k<2^{n+1}$

$\Longleftrightarrow \left(\sum_{k=1}^n2^{n-k}k\right)+(n+1)<2^{n+1}+(n+1)$

Since $n+1<2^{n+1}$ (can be shown separately), we have $2^{n+1}+(n+1)<2\cdot 2^{n+1}=2^{n+2}$ and so

$\Longleftrightarrow\sum_{k=1}^{n+1}2^{n-k}k<2^{n+2}$

as required.

So what would be the $E(n)$ in this argument?
• Jun 30th 2013, 03:11 PM
Ragnarok
Re: Proving an inequality without induction
Oh, sorry, I forgot to put it back in the right form:

$\sum_{k=1}^{n+1}2^{n-k}k<2^{n+2}$

$\Longleftrightarrow \frac{1}{2^{n+1}}\sum_{k=1}^{n+1}2^{n-k}k<2$

$\Longleftrightarrow \sum_{k=1}^{n+1}\frac{k}{2^k}<2$

I hope that's right...
• Jun 30th 2013, 04:17 PM
Ragnarok
Re: Proving an inequality without induction
Mistake in that last bit...should be an $n+1$ in parts of it.