Proof that $\sum_{k=1}^n \frac{k}{2^k} < 2 $ for all $n \geq 1$

Question

I recently completed a variation of a problem I found from a mathematical olympiad which is as follows:

Prove that, for all $n \in \mathbb{Z}^+$, $n \geq 1$, $$\sum_{k=1}^n \frac{k}{2^k} < 2 $$

I would like to hear comments on my method of proving the inequality above as well as ways of improving it or making it more rigorous. Thank you!

Proof: We begin by noticing that the series above is a Riemann sum (or approximation by areas of rectangles) for the integral $$ \int_1^n \frac{x}{2^x} dx$$ where the right endpoints are taken, hence $$\sum_{k=1}^n \frac{k}{2^k} < \int_1^n \frac{x}{2^x} dx$$ for all $n$.

By evaluating the original integral, it can be shown that $$ \int_1^n \frac{x}{2^x} dx = \frac{n \ln 2 + 1}{2^n (\ln 2)^2} + \frac{\ln 2 + 1}{2 (\ln 2)^2}$$

As $n$ approaches infinity, the integral approaches the value $\frac{\ln 2 + 1}{2 (\ln 2)^2}$, which is less than $2$. Hence, it can be deduced that $$ \int_1^n \frac{x}{2^x} dx < 2$$ for a large enough $n$.

By inspection and calculation, it is obvious that $$ \int_1^n \frac{x}{2^x} dx < 2$$ when $n > 5, n \in \mathbb{Z}^+$. Hence, when $1 \leq n \leq 5$, the integral has a value that is greater than $2$.

However, it can be verified by calculation that for $1 \leq n \leq 5$, $$\sum_{k=1}^n \frac{k}{2^k} < 2 $$ Since the statement holds true for $1 \leq n \leq 5$ as well as for $n > 5$, where $n \in Z^+$, the statement must be true for all $n \geq 1$. Hence, the proof is complete.

Hope to hear your thoughts on this!

Answer 1

There are some major issues. First, when $n = 1$, the integral is trivially $0$, so you cannot make the claim that $$S(n) = \sum_{k=1}^n \frac{k}{2^k} < \int_{x=1}^n \frac{x}{2^x} \, dx$$ for all $n$. In fact, this inequality is never true. I suspect you intended $$S(n) < \int_{x=0}^n \frac{x}{2^x} \, dx = I(n)$$ but once again this is not true unless $n \ge 5$, and more worrisome is that as $n \to \infty$, $I(\infty) > 2$, so the bound is simply too loose to show that $S(n) < 2$, even if you attempt to patch the reasoning for small cases of $n$.

When we use an integral to bound a sum, the behavior of the summand that is converted to an integrand must be monotone, otherwise you cannot make the argument. If you study the graph of $y = 2^{-x} x$ on $[0, \infty)$, we see that it is increasing from $x = 0$ to $x = (\log 2)^{-1}$, then decreasing afterward. This makes your approach fundamentally problematic.

Instead, what I would recommend is either the direct evaluation of $S$, for which there are numerous methods. This can be accomplished by differentiation of geometric series, e.g. consider $$f(z) = \sum_{k=0}^\infty z^k = \frac{1}{1-z}, \quad |z| < 1,$$ hence $$z f'(z) = \sum_{k=1}^\infty kz^k = \frac{z}{(1-z)^2}.$$ Then $$S(n) < S(\infty) = \left[z f'(z) \right]_{z=1/2} = \frac{1/2}{(1-1/2)^2} = 2$$ with the first inequality a direct consequence of the fact that all terms in $S$ are positive.

Answer 2

As commented by Albus, the values can be found.

In fact, let $p \in (0,1)$, then

$$\sum_{k=1}^{n}kp^k\le \sum_{k=1}^{\infty}kp^k=p\sum_{k=1}^{\infty}kp^{k-1}=p\frac{d}{dp}\left(\sum_{k=1}^{\infty}p^k\right)=p\frac{d}{dp}\frac{p}{1-p}=\frac{p}{(1-p)^2}.$$

Therefore, when $p=1/2$, the R.H.S. of the above is $2$, which proves your inequality.

In general, you can use integration to estimate the partial sum, as you did in your post.

Answer 3

Note that no calculus is needed:

$$\begin{align*} \sum_{k=1}^n\frac{k}{2^k}&=\sum_{k=1}^n\sum_{\ell=1}^k\frac1{2^k}\\ &=\sum_{\ell=1}^n\sum_{k=\ell}^n\frac1{2^k}\\ &=\sum_{\ell=1}^n\frac{\frac1{2^{\ell}}-\frac1{2^{n+1}}}{1-\frac12}\\ &=\sum_{\ell=1}^n\left(\frac1{2^{\ell-1}}-\frac1{2^n}\right)\\ &=\sum_{\ell=0}^{n-1}\frac1{2^\ell}-\frac{n}{2^n}\\ &=\frac{1-\frac1{2^n}}{1-\frac12}-\frac{n}{2^n}\\ &=2\left(1-\frac1{2^n}\right)-\frac{n}{2^n}\\ &=2-\frac{n+2}{2^n}\\ &<2\,. \end{align*}$$

For the visually oriented this has a nice schematic representation:

$$\begin{array}{cccccc|c} \frac12&\frac14&\frac18&\frac1{16}&\cdots&\frac1{2^n}&2\left(\frac12-\frac1{2^{n+1}}\right)=1-\frac1{2^n}\\ &\frac14&\frac18&\frac1{16}&\cdots&\frac1{2^n}&2\left(\frac14-\frac1{2^{n+1}}\right)=\frac12-\frac1{2^n}\\ &&\frac18&\frac1{16}&\cdots&\frac1{2^n}&2\left(\frac18-\frac1{2^{n+1}}\right)=\frac14-\frac1{2^n}\\ &&&\frac1{16}&\cdots&\frac1{2^n}&2\left(\frac1{16}-\frac1{2^{n+1}}\right)=\frac18-\frac1{2^n}\\ &&&&\ddots&\vdots&\vdots\\ &&&&&\frac1{2^n}&2\left(\frac1{2^n}-\frac1{2^{n+1}}\right)=\frac1{2^{n-1}}-\frac1{2^n}\\\hline \frac12&\frac2{2^2}&\frac3{2^3}&\frac4{2^4}&\cdots&\frac{n}{2^n}&2\left(1-\frac1{2^n}\right)-\frac{n}{2^n}=2-\frac{n+2}{2^n} \end{array}$$

Instead of summing the columns to the left of the vertical line to get the terms of the summation and then adding, I’ve summed the rows of the triangular matrix, each of which is a geometric progression, to get the totals in the righthand column above the horizontal line, and then summed those row sums to get the desired total.

Answer 4

$$2S_n-S_n=\sum_{k=1}^nk2^{1-k}-\sum_{k=1}^nk2^{-k}=\sum_{k=0}^{n-1}(k+1)2^{-k}-\sum_{k=1}^nk2^{-k} \\=1-n2^{-n}+\sum_{k=0}^{n-1}2^{-k}<1+1.$$