Use induction to prove the following:
$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^n}\geq1+\frac{n}{2}$
What would the base case be? Would it still be $n=0$
so $\frac{1}{1}+\frac{1}{2}\geq 1+\frac{0}{2}$, which holds true.
then how would you prove for $n$ and $n+1$ to prove the proof with induction?
On
Base case for $n = 0$: $\frac{1}{1} \geq 1$
Inductive step: Assume $\displaystyle \sum_{k = 1}^{2^n} \frac{1}{k} \geq 1 + \frac{n}{2}$
Then, after substituting the inductive step, what we want to prove is $\displaystyle \sum_{k = 2^n + 1}^{2^{n+1}} \frac{1}{k} \geq \frac{1}{2}$
This is clear to show by a comparison:
$\displaystyle \sum_{k = 2^n + 1}^{2^{n+1}} \frac{1}{k} \geq 2^n \left( \frac{1}{2^{n+1}} \right) = \frac{1}{2}$
Yes, the base case here would be $n = 0$, and your assessment is correct, although there is no $\frac{1}{2}$ term in the $n = 0$ case.
For our inductive step (proving $n+1$ from $n$), consider that we know that $$\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{2^n} \ge 1 + \frac{n}{2}$$ and are trying to show: $$\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{2^{n+1}} \ge 1 + \frac{n+1}{2}.$$ We thus, subtracting, want to show that: $$ \frac{1}{2^{n}+1} + \cdots + \frac{1}{2^{n+1}} \ge \frac{1}{2} $$ Note that there are $2^{n+1} - (2^n + 1) + 1 = 2^n$ terms here, each of which is greater than or equal to $\frac{1}{2^{n+1}}$. Therefore we get that: $$ \frac{1}{2^{n}+1} + \cdots + \frac{1}{2^{n+1}} \ge 2^n\left(\frac{1}{2^{n+1}}\right) = \frac{1}{2}. $$ So we are done.