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?
 A: 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}
$$
A: 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.
