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$
$\endgroup$
2
-
$\begingroup$ Yes, use induction. Think about the inductive step..., what is it? $\endgroup$– Colm BhandalSep 5, 2015 at 15:10
-
$\begingroup$ Is it solved as a floor function?? $\endgroup$– user268192Sep 5, 2015 at 16:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
$\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} $
answered Sep 5, 2015 at 15:11
-
$\begingroup$ what about the floor function?? we have to show it as a floor function ?? $\endgroup$– user268192Sep 5, 2015 at 16:30
-
-
$\begingroup$ so is it like for 2n we dnt need floor function? $\endgroup$– user268192Sep 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$– DidOct 17, 2015 at 19:59