Math 2.0

Number theory Theorem

Harmonic numbers grow like log n

Builds on Harmonic numberNatural logarithmIntegral of 1/xMonotone convergence theorem for sequencesAsymptotic equivalence

Statement

Let Hn=∑k=1n1kH_n = \sum_{k=1}^{n} \frac{1}{k} be the harmonic numbers. Then the limit lim⁡n→∞(Hn−ln⁡n)\lim_{n \to \infty} (H_n - \ln n) exists, and it lies in [0,1][0, 1]. In particular, Hn∼ln⁡nH_n \sim \ln n as n→∞n \to \infty.

Remarks

Let an=Hn−ln⁡na_n = H_n - \ln n. Since ln⁡(n+1)−ln⁡n=∫nn+1dtt\ln(n + 1) - \ln n = \int_n^{n+1} \frac{dt}{t} lies between 1n+1\frac{1}{n+1} and 1n\frac{1}{n}, the sequence ana_n decreases. Also an≥Hn−ln⁡(n+1)≥0a_n \ge H_n - \ln(n + 1) \ge 0. The monotone convergence theorem gives the limit. It is the Euler–Mascheroni constant γ\gamma. The symbol ∼\sim is asymptotic equivalence. Mathlib states the limit as Real.tendsto_harmonic_sub_log.

Reading path

To understand this page from the ground up, read these 69 pages in order. The foundations come first.

  1. Big O notation definition
  2. Harmonic number definition
  3. Limit point of a set definition
  4. Local maximum definition
  5. Partition of an interval definition
  6. Sequence definition
  7. Strictly monotone function definition
  8. Little o notation definition
  9. Limit of a function definition
  10. Local minimum definition
  11. Mesh of a partition definition
  12. Riemann sum definition
  13. Real sequence definition
  14. Subsequence definition
  15. Asymptotic equivalence definition
  16. Continuity at a point definition
  17. Derivative definition
  18. One-sided limit definition
  19. Riemann integrable function definition
  20. Bounded sequence definition
  21. Geometric sequence definition
  22. Limit of a sequence definition
  23. Monotone sequence definition
  24. Series definition
  25. Continuous function definition
  26. Epsilon-delta definition of continuity statement
  27. Fermat's theorem on stationary points statement
  28. Sum of a finite geometric series statement
  29. Monotone convergence theorem for sequences statement
  30. Convergent sequence definition
  31. Every sequence has a monotone subsequence statement
  32. Squeeze theorem statement
  33. Cauchy product definition
  34. Partial sum definition
  35. Power series definition
  36. Intermediate value theorem statement
  37. Composition of continuous functions is continuous statement
  38. One-sided limits of a monotone function exist statement
  39. Bolzano–Weierstrass theorem statement
  40. The sequence r^n tends to zero for |r| < 1 example
  41. Radius of convergence definition
  42. Convergent series definition
  43. Boundedness theorem statement
  44. Chain rule statement
  45. Continuity of the inverse of a strictly monotone continuous function statement
  46. A series of nonnegative terms converges iff its partial sums are bounded statement
  47. Absolute convergence definition
  48. Sum of a series definition
  49. Extreme value theorem statement
  50. Derivative of an inverse function statement
  51. Comparison test statement
  52. Geometric series example
  53. Cauchy product of absolutely convergent series statement
  54. Rolle's theorem statement
  55. Ratio test statement
  56. Mean value theorem statement
  57. Ratio formula for the radius of convergence statement
  58. Second fundamental theorem of calculus statement
  59. A function with positive derivative is strictly increasing statement
  60. The exponential series has infinite radius of convergence statement
  61. Exponential function definition
  62. Exponential of a sum statement
  63. The exponential function is positive statement
  64. The exponential function is its own derivative statement
  65. The exponential function is strictly increasing statement
  66. Natural logarithm definition
  67. Derivative of the logarithm statement
  68. Integral of 1/x statement
  69. Harmonic numbers grow like log n statement

Where this leads

5 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Harmonic_number, Harmonic numbers for real and complex values
  2. Web https://en.wikipedia.org/wiki/Euler%27s_constant, Analysis
About this page
Tag05S2GSPMGA
URIm2://05S2GSPMGA
Kindstatement, theorem
WritingW0 stub
MSC11B83, 26A12
StatusThis copy of the site has no build data. Run m2 status 05S2GSPMGA.
UsesHarmonic number, Natural logarithm, Integral of 1/x, Monotone convergence theorem for sequences, Asymptotic equivalence

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by