Sums, Approximations, and Asymptotics II ret the upper bound 111 1+Inn So even though there is no closed-form for the n-th harmonic sum, we now know that the harmonic numbers grow logarithmically n(n+1)≤Hn≤1+ There is a refinement to the integration method we've just employed, called Euler. Maclaurin summation, which yields a sequence of terms that correct errors in the inital estimate. This technique gives an absurdly accurate formula for harmonic numbers An=Inn+y+ 2n12n2120m4 The second term is Euler's constant, y=0.577215664.. This is probably the third most important mathematical constant behind e and T. It is somewhat mysterious; for example no one knows whether y is rational or irrational, though if it equals a ratio of integers, then the denominator must be at least 10242,080. In the final term of the formula above E(n) denotes some number between 0 and 1. You'll never need this kind of precision in this course or, probably, anywhere else 2 The factorial Function One of the most common elements in messy mathematical expressions is the factorial function n!=1.2.3…(n-1) Factorial comes up particularly often in combinatorics and probability, which happen to be the major topics in the remainder of 6.042. Within a few weeks, you are going to have factorials coming out your ears a good way to deal with any product is to covert it into a sum by taking a logarithm l(I(4)=∑m) k=1 Then summing tools and exponentiate at the end to undo the effect the log. Let,'s use this strategy to get bounds on n!. First, we take a logarithm to make� � � � 6 Sums, Approximations, and Asymptotics II get the upper bound: 1 1 1 1 Hn = + + + . . . + 1 � 2 3 n n 1 ≤ 1 + dx 1 x = 1 + ln n So even though there is no closed­form for the n­th harmonic sum, we now know that the harmonic numbers grow logarithmically: ln(n + 1) ≤ Hn ≤ 1 + ln n There is a refinement to the integration method we’ve just employed, called Euler￾Maclaurin summation, which yields a sequence of terms that correct errors in the inital estimate. This technique gives an absurdly accurate formula for harmonic numbers: 1 1 �(n) Hn = ln n + γ + + 2n − 12n2 120n4 The second term is Euler’s constant, γ = 0.577215664 . . .. This is probably the third most important mathematical constant behind e and π. It is somewhat mysterious; for example, no one knows whether γ is rational or irrational, though if it equals a ratio of integers, then the denominator must be at least 10242,080 . In the final term of the formula above, �(n) denotes some number between 0 and 1. You’ll never need this kind of precision in this course or, probably, anywhere else. 2 The Factorial Function One of the most common elements in messy mathematical expressions is the factorial function: n! = 1 2 3 · · · · ·(n − 1) · n Factorial comes up particularly often in combinatorics and probability, which happen to be the major topics in the remainder of 6.042. Within a few weeks, you are going to have factorials coming out your ears. A good way to deal with any product is to covert it into a sum by taking a logarithm: n n ln f(k) = ln f(k) k=1 k=1 Then we can apply all our summing tools and exponentiate at the end to undo the effect of the log. Let’s use this strategy to get bounds on n!. First, we take a logarithm to make