Proving the harmonic number For $n \in \mathbb N^{+}, H_n = \sum_{i=1}^n \frac{1}{i}$ is called the $n$-th harmonic number.
(a) Prove: $$\forall{n \in \mathbb N}: 1+ \frac n2 \le H_{2^n} $$
This is one of my homework questions and I do not know how to even begin. I was perhaps thinking of using induction to prove this. Any help would be appreciated.
So according to the reponse I should use induction...
Base Case: $n = 1$
$$1 + \frac{1}{2} \leq 1 + \frac{1}{2}$$ 
Base case holds...
Inductive Step: $n \geq 1$
Still working on this

Proof By Induction:
Base Case: $n=1$ is trivial
IH: $1 + \frac{n}{2} \leq H_{2^n}$
General Case: $$H_{2^{n+1}} = H_{2^n} + \frac{1}{2^n + 1} + ... + \frac{1}{2^{n+1}}$$ There are $2^n$ terms in $\frac{1}{2^n + 1} + ... + \frac{1}{2^{n+1}}$ and each term in the sum can be lower bounded by $\frac{1}{2^{n+1}}$. These facts along with the IH are enough to conclude.
