1

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

CloudN9ne
  • 349
  • In principle we need induction. In practice, it comes down to the fact that for example $1+\frac{1}{2}+\cdots+\frac{1}{8}\ge 1+\left(\frac{1}{2}\right)+\left(\frac{1}{4}+\frac{1}{4}\right)+\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}\right)$. – André Nicolas Apr 09 '14 at 16:19
  • I see, I'll try to work on it, thank you. – CloudN9ne Apr 09 '14 at 16:26
  • The sum from $\frac{1}{9}$ to $\frac{1}{16}$ is also $\gt$ the sum of $8$ copies of $\frac{1}{16}$, which is $\frac{1}{2}$. And the sum from $\frac{1}{17}$ to $\frac{1}{32}$ is greater than the sum of $16$ copies of $\frac{1}{32}$, so $\gt \frac{1}{2}$. and so on. – André Nicolas Apr 09 '14 at 16:30

1 Answers1

0

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.

user141998
  • 111