1
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ What is $\frac13$ doing in your sum? $\endgroup$
    – A.Γ.
    Oct 9 '17 at 22:42
  • $\begingroup$ 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 $\endgroup$ Oct 9 '17 at 22:50
  • $\begingroup$ @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}$? $\endgroup$
    – wsh_97
    Oct 9 '17 at 22:50
  • $\begingroup$ @wsh_97: I think you are ok, the sum just gets more terms in them. $\endgroup$
    – Thomas
    Oct 9 '17 at 22:50
  • $\begingroup$ Unless the denominators are all integers up to 2^k. The 3 there confuses me as well because it's no power of 2 $\endgroup$ Oct 9 '17 at 22:52
2
$\begingroup$

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} $$

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – wsh_97
    Oct 9 '17 at 22:58
  • $\begingroup$ Did you check the $n=1$ case? $\endgroup$
    – bof
    Oct 9 '17 at 23:00
  • $\begingroup$ @bof: You are right. Let's just assume that $n\geq 2$. $\endgroup$
    – Thomas
    Oct 9 '17 at 23:04
  • $\begingroup$ @wsh_97: I don't understand. All you use is that $\frac{2^k}{2^k + 1} \leq 1$. $\endgroup$
    – Thomas
    Oct 9 '17 at 23:06
  • $\begingroup$ You mean $n\ge3$? $\endgroup$
    – bof
    Oct 9 '17 at 23:16
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.