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\,?$$

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

1 Answer 1


$\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} $

  • $\begingroup$ what about the floor function?? we have to show it as a floor function ?? $\endgroup$
    – user268192
    Sep 5, 2015 at 16:30
  • $\begingroup$ That's why I did 2n instead of n. $\endgroup$ Sep 5, 2015 at 16:49
  • $\begingroup$ so is it like for 2n we dnt need floor function? $\endgroup$
    – user268192
    Sep 5, 2015 at 16:57
  • $\begingroup$ Exactly. I view this as going from $n$ to $2n$ to ... $2^kn$, not the other way (i.e., successive divisions by 2). $\endgroup$ Sep 6, 2015 at 10:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Did
    Oct 17, 2015 at 19:59

You must log in to answer this question.