Proving an inequality without induction

• Jun 25th 2013, 01: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:

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

for all $\displaystyle n\geq 1$.

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

Thanks!
• Jun 25th 2013, 03: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 $\displaystyle \sum_{k=1}^n\frac{k}{2^k}<2$ to $\displaystyle \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 $\displaystyle f(x)=\sum_{k=0}^\infty\frac{x^k}{2^k} =\frac{2}{2-x}$. Then $\displaystyle f'(x)=\sum_{k=1}^\infty\frac{kx^{k-1}}{2^k}$ for $\displaystyle x<2$ (see Wikipedia), so $\displaystyle f'(1)=\sum_{k=1}^\infty\frac{k}{2^k}$.
• Jun 29th 2013, 05: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 \displaystyle\sum_{k=1}^n\frac{k}{2^k}<2$

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

Multiply by $\displaystyle \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: . . . .$\displaystyle \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: $\displaystyle 1 - \tfrac{1}{2^n}$

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

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

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

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

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

Since the fraction is positive, $\displaystyle S \:<\:2.$
• Jun 30th 2013, 09: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, 02:04 PM
emakarov
Re: Proving an inequality without induction
I am not sure my method, which is supposed to work by proving $\displaystyle \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, 02:05 PM
Ragnarok
Re: Proving an inequality without induction
Okay, I think I got it. Here's what I did for the inductive step:

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

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

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

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

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

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

as required.

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

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

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

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

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