# Prove by Induction that $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\ldots+\frac{1}{2^n}\leq n$

The question asks to prove by induction that for every integer, $n\geq3$. We have the sequence: $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^n}\leq n$$

So from here, I started with a base case scenario where $n=1$. Plugging $n$ into the sequence, we get that $$\frac{1}{2}\leq 1$$ which is indeed a true assumption. From here, the induction hypothesis is that the theorem is true for $n=k$. Rewriting this and plugging in $k$, we get: $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^k}\leq k$$

Since the whole sequence is less than or equal to $k$, we can take $k$ to represent the whole sequence. So, now we also assume that $n=k+1$ is also true, by doing so, we arrive at the sequence:$$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^k}+\frac{1}{2^{k+1}}\leq k+1.$$

Rewriting this with $k$, we get that the sequence would then look like this: $$k+\frac{1}{2^{k+1}}\leq k+1.$$

After this step, I seem to not be able to continue further. Are there any tips on how I can continue to prove this?

• What is $\frac13$ doing in your sum?
– A.Γ.
Oct 9 '17 at 22:42
• I'll try this when I get home. Do note though that between (1/2^k) and (1/2^k+1) there is quite a number of other fractions, given the sequence you have given Oct 9 '17 at 22:50
• @A.Γ. I'm not so sure, this is how the question was posed. Perhaps it should be $\frac{1}{4}$ instead of $\frac{1}{3}$ considering it is $\frac{1}{2^n}$? Oct 9 '17 at 22:50
• @wsh_97: I think you are ok, the sum just gets more terms in them. Oct 9 '17 at 22:50
• Unless the denominators are all integers up to 2^k. The 3 there confuses me as well because it's no power of 2 Oct 9 '17 at 22:52

Ok, so you want to show that $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4} + \frac{1}{5} + \dots+\frac{1}{2^n}\leq n$$ for all $n\geq 3$. I assume that the $3$ is there because the sum actually has $2^n$ terms. If $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{2^k}\leq k$$ for some $k$, you then want to show that $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{2^{k+1}-1} + \frac{1}{2^{k+1}}\leq k +1$$ But \begin{align} \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{2^{k+1}-1} + \frac{1}{2^{k+1}}&\leq k + \overbrace{\frac{1}{2^{k} + 1} + \dots +\frac{1}{2^{k+1}}}^{2^k \text{ terms}} \\ &\leq k + \frac{2^{k}}{2^{k} +1} \\ &\leq k + 1 \end{align}

• I understand that from $\leq k+ \frac{2k}{2^k+1}$, but what happens to $\frac{2^k}{1}$? How did that get removed from the RHS? Oct 9 '17 at 22:58
• Did you check the $n=1$ case?
– bof
Oct 9 '17 at 23:00
• @bof: You are right. Let's just assume that $n\geq 2$. Oct 9 '17 at 23:04
• @wsh_97: I don't understand. All you use is that $\frac{2^k}{2^k + 1} \leq 1$. Oct 9 '17 at 23:06
• You mean $n\ge3$?
– bof
Oct 9 '17 at 23:16

You want to show that $\sum_{i=1}^{2^n} \dfrac1{i} \le n$.

Suppose this is true for $n$.

Then you want to show that $\sum_{i=1}^{2^{n+1}} \dfrac1{i} \le n+1$.

You know that $\sum_{i=1}^{2^n} \dfrac1{i} \le n$.

Therefore $\sum_{i=1}^{2^{n+1}} \dfrac1{i} =\sum_{i=1}^{2^{n}} \dfrac1{i}+\sum_{i=2^n+1}^{2^{n+1}} \dfrac1{i} \le n+\sum_{i=2^n+1}^{2^{n+1}} \dfrac1{i}$.

To make this $\le n+1$, it will be enough if $\sum_{i=2^n+1}^{2^{n+1}} \dfrac1{i} \le 1$.

But $\sum_{i=2^n+1}^{2^{n+1}} \dfrac1{i} \lt \sum_{i=2^n+1}^{2^{n+1}} \dfrac1{2^n} =2^n\dfrac1{2^n} =1$ and we are done.