Sums, Approximations, and Asymptotics II the product into a sum: lnn!=ln(1·.2.3……m) In 1+In 2+In3+.+Inn This sum is rather nasty, but we can still get bounds by the integration method. A picture can be extremely helpful in working out the proper bounding functions and limits of integration. y=In(a+1) In 3 In 4 In this case, we get the bounds lndr≤hnn!≤/ln(x+1)dx rhnx-x.≤mn!≤(x+1)hn(x+1)-(x+1 nlnn-n+1≤lnn!≤(n+1)ln(m+1)-(m+1)+ Finally, we exponentiate to get bounds on n ≤/n+1)n+1 This gives some indication how big n! is: about(n/e) n. This estimate is often good enough. If you need a little more accuracy, you can add one more term to get Stirlings uLe n!≈v2rn Stirlings formula is worth committing to memory. We'll often use it to rewrite expres- lot better than the expression on the right. But thats just an artifact of notation. If youe o sions involving n!. Now, one might object that the expression on the left actually looks tually wanted to compute n! youd need n-1 multiplications. However, the expression the right is a closed form; evaluating it requires only a handful of basic operations, regardless of the value of n. Furthermore, when n! appears inside a larger expression,� � � � � � � � � � � � � � Sums, Approximations, and Asymptotics II 7 the product into a sum: ln n! = ln(1 · 2 · 3 · · · n) = ln 1 + ln 2 + ln 3 + . . . + ln n This sum is rather nasty, but we can still get bounds by the integration method. A picture can be extremely helpful in working out the proper bounding functions and limits of integration. - 6 y = ln x y = ln(x ln n + 1) ln 3 ln 4 0 1 2 3 4 n In this case, we get the bounds: n n ln x dx ≤ ln n! ≤ ln(x + 1) dx 1 0 n ln n! ≤ (x + 1) ln(x + 1) − (x + 1) 1 ≤ n x ln x − x 0 n ln n − n + 1 ln ≤ n! ≤ (n + 1) ln(n + 1) − (n + 1) + 1 Finally, we exponentiate to get bounds on n!. n n+1 n n + 1 e n! ≤ e e · ≤ e · This gives some indication how big n! is: about (n/e)n . This estimate is often good enough. If you need a little more accuracy, you can add one more term to get Stirling’s Formula: √ 2πn n n n! ≈ e Stirling’s formula is worth committing to memory. We’ll often use it to rewrite expres￾sions involving n!. Now, one might object that the expression on the left actually looks a lot better than the expression on the right. But that’s just an artifact of notation. If you ac￾tually wanted to compute n!, you’d need n − 1 multiplications. However, the expression on the right is a closed form; evaluating it requires only a handful of basic operations, regardless of the value of n. Furthermore, when n! appears inside a larger expression