Proof of an inequality with natural numbers

  • #1

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.
 

Answers and Replies

  • #2
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,829
6,652
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.
 
  • #3
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,829
6,652
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.
 
  • #4
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!
 

Related Threads on Proof of an inequality with natural numbers

Replies
4
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
5K
Replies
4
Views
2K
  • Last Post
Replies
22
Views
1K
Replies
3
Views
2K
Replies
1
Views
2K
Replies
4
Views
2K
Top