Proof by induction of summation inequality: $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots+\frac1{2^n}\ge 1+\frac{n}2$ Prove by induction the summation of $\frac1{2^n}$ is greater than or equal to $1+\frac{n}2$.
We start with $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots+\frac1{2^n}\ge 1+\frac{n}2$$ for all positive integers. 
I have resolved that the following attempt to prove this inequality is false, but I will leave it here to show you my progress. In my proof, I need to define P(n), work out the base case for n=1, and then follow through with the induction step. Strong mathematical induction may be used.
This is equivalent to $$\sum_{k=0}^n\frac1{2^k}\ge 1+\frac{n}2\;.$$
Let $P(n)$ be summation shown above. 
Base case for $n=1$, the first positive integer, 
$$\sum_{k=0}^1\frac1{2^k}=\frac1{2^0}+\frac1{2^1}=1+\frac12=\frac32\ge 1+\frac12=\frac32\;,$$
so base case is true.
Induction step: Assume $P(n)$ is true and implies $P(n+1)$. Thus 
$$\sum_{k=0}^{n+1}\frac1{2^k}\ge\frac1{2^{n+1}}+\sum_{k=0}^n\frac1{2^k}\ge 1+\frac{n+1}2\;.$$
This can be written as 
$$\sum_{k=0}^{n+1}\frac1{2^k}\ge \frac1{2^{n+1}}+1+\frac{n}2\ge 1+\frac{n+1}2\;.$$
I work the math out but I get stuck contradicting my statement. Please show your steps hereafter so I can correct my mistakes.
 A: I think that your notation is rather badly confused: I strongly suspect that you’re supposed to be showing that $$\sum_{k=1}^{2^n}\frac1k\ge 1+\frac{n}2\;,\tag{1}$$ from which one can conclude that the harmonic series diverges. The basis step for your induction should then be to check that $(1)$ is true for $n=0$, which it is: $$\sum_{k=1}^{2^n}\frac1k=\frac11\ge 1+\frac02\;.$$
Now your induction hypothesis, $P(n)$, should be equation $(1)$, and you want to show that this implies $P(n+1)$, which is the inequality $$\sum_{k=1}^{2^{n+1}}\frac1k\ge 1+\frac{n+1}2\tag{2}\;.$$ You had the right idea when you broke up the bigger sum into the old part and the new part, but the details are way off:
$$\begin{align*}\sum_{k=1}^{2^{n+1}}\frac1k&=\sum_{k=1}^{2^n}\frac1k+\sum_{k=2^n+1}^{2^{n+1}}\frac1k\\
&\ge 1+\frac{n}2+\sum_{k=2^n+1}^{2^{n+1}}\frac1k\tag{3}
\end{align*}$$
by the induction hypothesis $P(n)$. Now look at that last summation in $(3)$: it has $2^{n+1}-2^n=2^n$ terms, and the smallest of those terms is $\dfrac1{2^{n+1}}$, so $$\sum_{k=2^n+1}^{2^{n+1}}\frac1k\ge 2^n\cdot\frac1{2^{n+1}}=\frac12\;.$$ If you plug this into $(3)$, you find that $$\sum_{k=1}^{2^{n+1}}\frac1k\ge 1+\frac{n}2+\frac12=1+\frac{n+1}2\;,$$ which is exactly $P(n+1)$, the statement that you were trying to prove.
You’ve now checked the basis step and carried out the induction step, so you can conclude that $(1)$ is true for all $n\ge 0$.
A: The base case looks okay. For the inductive step, you want to assume $P(n)$ is true, and you need to show that $P(n) \rightarrow P(n+1)$. Your wording suggests that you are assuming that implication.
So, you assume for all $k \geq 1$
$$\sum\limits_{i=0}^{k} \frac{1}{2^i} \geq 1 + \frac{k}{2}.$$
Then we have the following when $n = k + 1$
$$\sum\limits_{i=0}^{k+1} \frac{1}{2^i} = \frac{1}{2^{k+1}} + \sum\limits_{i=0}^{k} \frac{1}{2^i} \geq \frac{1}{2^{k+1}} + 1 + \frac{k}{2}.$$
We know that $\frac{1}{2^{k+1}} > \frac{1}{2}$, so we have
$$\sum\limits_{i=0}^{k+1} \frac{1}{2^i} \geq \frac{1}{2^{k+1}} + 1 + \frac{k}{2} > 1 + \frac{k+1}{2}.$$
Thus, for all $n \geq 1$, $P(n) \rightarrow P(n+1)$, so the hypothesis holds.
A: Hint:
$$\sum_{k=0}^n\frac1{2^k}=\frac{2^{n+1}-1}{2^n}$$
