Proof of an inequality with natural numbers

[Andraz Cepic]

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]

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]

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.

 

[Andraz Cepic]

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!