# Proof of an inequality with natural numbers

## Homework Statement

Prove that ##\forall n \in \mathbb{N}##
$$\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n - 1} \leq n \text{ .}$$

## Homework Equations

Peano axioms and field axioms for real numbers.

## The Attempt at a Solution

Okay so my first assumption was that this part in the middle was a partial series of a sequence, that looks something like
$$1+ \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n - 1} + \frac{1}{2^{n+1} - 1} \text{,}$$
so I tried to prove it using this, but I quickly spotted the elephant in the room that the ##\frac{1}{2}## is, since ##\nexists n \in \mathbb{N}## so that ##2^n - 1 = 2##.

Therefore I tried to come up with a reasonable sequence for which such an inequality could hold. Thus far I wrestled with
$$\sum\limits_{k=1}^{2^n -1} \frac{1}{k} + \sum\limits_{k=2^n}^{2^{n+1} - 1} \frac{1}{k}\text{,}$$
but the inequlaity has proven itself to be incredibly difficult to prove via induction.

My first try was to prove the right hand side, therefore to come to a contradiction with
\begin{gather*}
\sum\limits_{k=1}^{2^{n+1} - 1} \frac{1}{k}
\leq
n + \frac{1}{2^n} + \frac{1}{2^n + 1} + \ldots + \frac{1}{2^{n+1} - 1}
> n+1 \text{,}
\end{gather*}
or
$$\frac{1}{2^n} + \frac{1}{2^n + 1} + \ldots + \frac{1}{2^{n+1} - 1} > 1\text{,}$$
which is intuitively a contradiciton and I have gone so far as to even write a little program in c that calculated the left side for ##n = 1, 2, \ldots, 10##, where the result was obviously less than 1.

I have no idea how to prove this so far, but I am still trying and will do so until I run out of time and check this thread for hints and update you on the situation when necessary.

Orodruin
Staff Emeritus
Homework Helper
Gold Member
2021 Award
Therefore I tried to come up with a reasonable sequence for which such an inequality could hold. Thus far I wrestled with
$$\sum\limits_{k=1}^{2^n -1} \frac{1}{k} + \sum\limits_{k=2^n}^{2^{n+1} - 1} \frac{1}{k}\text{,}$$
but the inequlaity has proven itself to be incredibly difficult to prove via induction.
I suggest you look at the second sum and try to find a lower and upper bound for it. Your total sum is the sum of ##n## such sums.

Orodruin
Staff Emeritus
Homework Helper
Gold Member
2021 Award
To be a bit more specific, you can often get a hint from how it plays out for small ##n##. For example, for ##n = 1## you have ##2^1 - 1 = 1## and therefore
$$1/2 \leq 1 \leq 1.$$
For ##n = 2##, ##2^n-1 = 3## and you have
$$1 + (1/2 + 1/3) < 1 + (1/2 + 1/2) = 2$$
but also
$$1 + (1/2 + 1/3) > 1 + (1/3 + 1/3) = 1 + 2/3 > 1/2 + 1/2 = 2/2.$$
You should be able to work from here.

To be a bit more specific, you can often get a hint from how it plays out for small ##n##. For example, for ##n = 1## you have ##2^1 - 1 = 1## and therefore
$$1/2 \leq 1 \leq 1.$$
For ##n = 2##, ##2^n-1 = 3## and you have
$$1 + (1/2 + 1/3) < 1 + (1/2 + 1/2) = 2$$
but also
$$1 + (1/2 + 1/3) > 1 + (1/3 + 1/3) = 1 + 2/3 > 1/2 + 1/2 = 2/2.$$
You should be able to work from here.

I have, since posting the question, tried to find an upper bound and lower bound to the sequence, but I have TOTALLY failed when calculating the number of terms: ##2^{n+1} - 2^n = 2^n(2^n - 1)##, instead of ##2^{n+1} - 2^n = 2^n(2 - 1) = 2^n## confusing myself entirely and giving up trying to bound it. The correction then leads to
$$1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^{n+1} - 1} < n + \sum\limits_{k = 1}^{2^n} \frac{1}{2^n} = n+1 \text{,}$$
as desired. Moreover
$$1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^{n+1} - 1} > \frac{n}{2} + \sum\limits_{k = 1}^{2^n} \frac{1}{2^{n+1}} = \frac{n}{2} + \frac{1}{2} = \frac{n+1}{2} \text{,}$$
finishing off the proof!
##\square##

Thank you for helping me notice my mistake!