# Prove $h(n)\leq h (\lfloor n/2 \rfloor) +1$ where $h(k)$ denotes the $k$th harmonic number

Can someone tell me how to prove that the harmonic numbers

$$h(n) = \sum_{k = 1}^n \frac{1}{k}$$

satisfy the inequality

$$h(n) \leq h(\lfloor n/2\rfloor) + 1\,?$$

• Yes, use induction. Think about the inductive step..., what is it? Sep 5, 2015 at 15:10
• Is it solved as a floor function??
– user268192
Sep 5, 2015 at 16:31

$\begin{array}\\ H(2n) &=\sum_{k=1}^{2n} \frac1{k}\\ &=\sum_{k=1}^{n} \frac1{k}+\sum_{k=n+1}^{2n} \frac1{k}\\ &=H(n)+\sum_{k=n+1}^{2n} \frac1{k}\\ &<H(n)+\sum_{k=n+1}^{2n} \frac1{n} \qquad \text{ since }\frac1{n} > \frac1{k} \text{ for } k > n \\ &=H(n)+n \frac1{n}\\ &=H(n)+1\\ \end{array}$

Also note that

$\begin{array}\\ H(2n) &=H(n)+\sum_{k=n+1}^{2n} \frac1{k}\\ &>H(n)+\sum_{k=n+1}^{2n} \frac1{2n} \qquad \text{ since }\frac1{2n} \le \frac1{k} \text{ for } k \le 2n \\ &=H(n)+n \frac1{2n}\\ &=H(n)+\frac12\\ \end{array}$

(added in response to a comment)

$\begin{array}\\ H(2n+1) &=\sum_{k=1}^{2n+1} \frac1{k}\\ &=\sum_{k=1}^{n} \frac1{k}+\sum_{k=n+1}^{2n+1} \frac1{k}\\ &=H(n)+\sum_{k=n+1}^{2n+1} \frac1{k}\\ &<H(n)+\sum_{k=n+1}^{2n+1} \frac1{n+1} \qquad \text{ since }\frac1{n+1} > \frac1{k} \text{ for } k > n+1 \\ &=H(n)+(n+1) \frac1{n+1}\\ &=H(n)+1\\ \end{array}$

• what about the floor function?? we have to show it as a floor function ??
– user268192
Sep 5, 2015 at 16:30
• That's why I did 2n instead of n. Sep 5, 2015 at 16:49
• so is it like for 2n we dnt need floor function?
– user268192
Sep 5, 2015 at 16:57
• Exactly. I view this as going from $n$ to $2n$ to ... $2^kn$, not the other way (i.e., successive divisions by 2). Sep 6, 2015 at 10:21
• This is only half of the solution (the easiest one). One also needs to prove that h(2n+1)⩽h(n)+1 for every nonnegative integer n.
– Did
Oct 17, 2015 at 19:59