Collection of Maths Problems

Harmonic number

Task number: 3856

• Variant

  For \(n=2^m\) prove: \(1+\frac{m}{2} \leq H_n \leq 1+m\).

• Solution

  By induction on \(m\) we get:

  For \(m=1\) i.e. when \(n=2\) it holds that: \(1+ \frac12 \le 1+\frac12 \le 1+1\).

  The upper bound:

  \( H_{2^{m+1}}=H_{2{\cdot} 2^m}=H_{2^m}+\sum\limits_{i=2^m+1}^{2^{m+1}}\frac{1}{i} \le m+1 + 2^m\frac{1}{2^m+1} \le m+2\)

  The lower bound:

  \( H_{2^{m+1}}=H_{2{\cdot} 2^m}=H_{2^m}+\sum\limits_{i=2^m+1}^{2^{m+1}}\frac{1}{i} \ge 1+\frac{m}2 + 2^m \frac{1}{2^{m+1}} \ge 1+\frac{m+1}2\)

• Variant

  Prove a more general estimate: \(\frac{1}{2}\log_2 n \leq H_n \leq 2+ \log_2 n\).

• Hint

  Shorten or extend the series appropriately and use the previous estimate.

• Solution

  For the upper bound, we first extend the series to the nearest power of two, i.e. we determine \(m=\lceil \log_2 n\rceil\) and estimate as:

  \(H_n \leq H_{2^m} \leq 1+m = 1+ \lceil \log_2 n\rceil \leq 2+ \log_2 n\).

  For the lower bound, we first shorten the series to the nearest power of two, i.e. we determine \(m=\lfloor \log_2 n\rfloor\) and estimate as:

  \(H_n \geq H_{2^m} \geq 1+\frac{m}{2} = 1+ \frac{1}{2} \lfloor \log_2 n\rfloor \geq \frac{1}{2} \log_2 n\).

• Variant

  Improve the general estimate onto: \(\ln n \leq H_n \leq 1+ \ln n\).

• Hint

  Interpolate the sequence by a suitable function and use the Riemann integral.

• Solution

  Through the sequence \(\frac1i\) for \(i=1,…,n\) we interpolate the function \(\frac1x\). This function is decreasing.

  The area under this function (Riemann integral) on the interval \(\langle i, i+1\rangle\) ins included in the rectangle \(\langle i, i+1\rangle \times\langle 0, f(i)\rangle\), of area \(\frac{1}{i}\).

  For the lower estimate, we estimate the sum of the series, i.e. the area of \( n \) consecutive rectangles by the Riemann integral of the function \( \frac{1}{x} \) on the interval \( \langle 1, n + 1 \rangle \):

  \(H_n \ge \int_1^{n+1} \frac1x dx=\left[\ln x \right]_1^{n+1} = \ln (n+1)> \ln n\)

  Analogously, the area under this function on the interval \(\langle i-1, i\rangle\) includes the rectangle \(\langle i-1, i\rangle \times\langle 0, f(i)\rangle\), of area \(\frac{1}{i}\).

  For an upper bound we exclude the first element and estimete the sum of the rest of the series, i.e. the area of \(n-1\) consecutive rectangles by the Riemann integral of the function \(\frac{1}{x}\) on the interval \(\langle 1, n\rangle\):

  \(H_n \le 1 + \int_1^{n} \frac1x dx= 1+\left[\ln x \right]_1^{n}= 1+ \ln n\)

  Observe that this estimate is consistent with the estimate from the previous variant, as: \(\frac{1}{2}\log_2 n=\log_4 n \le \ln n \le \log_2 n\).