The number of digits in n! (Part 4)

When I was in school, I stared at this graph for weeks, if not months, trying to figure out an equation for the number of digits in n!. And I never could figure it out. However, even though I was not able to figure this out for myself, there is a very good approximation using Stirling’s approximation. The next integer after \log_{10} n! gives the number of digits in n!, and

\log_{10} n! \approx \displaystyle \frac{\left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \displaystyle \frac{1}{2} \ln (2\pi)}{\ln 10}

The graph below shows just how accurate this approximation really is. The solid curve is the approximation; the dots are the values of \log_{10} n!. Not bad at all… the error in the curve is smaller than the size of the dots.

stirling

The following output from a calculator shows just how close the approximation to log_{10} 69! is to the real answer. There are also additional terms to Stirling’s series that would get even closer answers.

stirling69-2

stirling69

As I mentioned earlier in this series, I’m still mildly annoyed with my adolescent self that I wasn’t able to figure this out for myself… especially given the months that I spent staring at this problem trying to figure out the answer.

First, I’m annoyed that I didn’t think to investigate \log_{10} n!. I had ample experience using log tables (after all, this was the 1980s, before scientific calculators were in the mainstream) and I should have known this.

Second, I’m annoyed that I didn’t have at the tips of my fingers the change of base formula

\log_{10} n! = \displaystyle \frac{\ln n!}{\ln 10}

Third, I’m annoyed that, even though I knew calculus pretty well, I wasn’t able to get at least the first couple of terms of Stirling’s series on my own even though the derivation was entirely in my grasp. To begin,

\ln n! = \ln (1 \cdot 2 \cdot 3 \dots \cdot n) = \ln 1 + \ln 2 + \ln 3 + \dots + \ln n

For example, if n = 10, then \ln 10! would be the areas of the 9 rectangles shown below (since $\ln 1 = 0$):

stirlingintegralThe areas of these nine rectangles is closely approximated by the area under the curve y = \ln x between x =1\frac{1}{2} and x = 10\frac{1}{2}. (Indeed, I chose a Riemann sum with midpoints so that the approximation between the Riemann sum and the integral would be very close.)

In general, for n! instead of 10!, we have

\ln n! \approx \displaystyle \int_{3/2}^{n+1/2} \ln x \, dx

This is a standard integral that can be obtained via integration by parts:

\ln n! \approx \bigg[ \displaystyle x \ln x - x \bigg]_{3/2}^{n+1/2}

\ln n! \approx \left[ \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n + \displaystyle \frac{1}{2} \right) - \left(n + \displaystyle \frac{1}{2} \right) \right] - \left[ \displaystyle \frac{3}{2} \ln \frac{3}{2} - \frac{3}{2} \right]

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n + \displaystyle \frac{1}{2} \right) - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

We can see that this is already taking the form of Stirling’s approximation, given above. Indeed, this is surprisingly close. Let’s use the Taylor approximation \ln(1+x) \approx x for x \approx 0:

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n \left[1 + \displaystyle \frac{1}{2n}\right] \right) - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \left[\ln n + \ln \left(1 + \displaystyle \frac{1}{2n} \right) \right] - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \left[\ln n + \displaystyle \frac{1}{2n} \right] - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n + \left(n + \displaystyle \frac{1}{2} \right) \displaystyle \frac{1}{2n} - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n +\displaystyle \frac{1}{2} + \frac{1}{4n} - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \left(\displaystyle \frac{3}{2} - \displaystyle \frac{3}{2} \ln \frac{3}{2} \right) + \displaystyle \frac{1}{4n}

By way of comparison, the first few terms of the Stirling series for \ln n! are

\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \displaystyle \frac{1}{2} \ln (2\pi) + \displaystyle \frac{1}{12n}

We see that the above argument, starting with an elementary Riemann sum, provides the first two significant terms in this series. Also, while the third term is incorrect, it’s closer to the correct third term that we have any right to expect:

\displaystyle \frac{3}{2} - \displaystyle \frac{3}{2} \ln \frac{3}{2} \approx 0.8918\dots

\displaystyle \frac{1}{2} \ln (2\pi) \approx 0.9189\dots

The correct third term of \displaystyle \frac{1}{2} \ln(2\pi) can also be found using elementary calculus, though the argument is much more sophisticated that the one above. See the MathWorld website for details.

Different definitions of e (Part 11): Numerical computation

In this series of posts, we have seen that the number e can be thought about in three different ways.

1. e defines a region of area 1 under the hyperbola y = 1/x.logarea2. We have the limits

e = \displaystyle \lim_{h \to 0} (1+h)^{1/h} = \displaystyle \lim_{n \to \infty} \left(1 + \frac{1}{n} \right)^n.

These limits form the logical basis for the continuous compound interest formula.

3. We have also shown that \frac{d}{dx} \left(e^x \right) = e^x. From this derivative, the Taylor series expansion for e^x about x = 0 can be computed:

e^x = \displaystyle \sum_{n=0}^\infty \frac{x^n}{n!}

Therefore, we can let x = 1 to find e:

e = \displaystyle \sum_{n=0}^\infty \frac{1}{n!} = \displaystyle 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + \dots

green line

Let’s now consider how the decimal expansion of e might be obtained from these three different methods.

1. Finding e using only the original definition is a genuine pain in the neck. The only way to approximate e is by trapping the value of e using various approximation. For example, consider the picture below, showing the curve y = 1/x and trapezoidal approximations on the intervals [1,1.8] and [1.8,2.6]. (Because I need a good picture, I used Mathematica and not Microsoft Paint.)

approx_e_lower

Each trapezoid has a (horizontal) height of h = 0.8. Furthermore, the bases of the first trapezoids have length \displaystyle \frac{1}{1} = 1 and \displaystyle \frac{1}{1.8}, while the bases of the second trapezoid of length \displaystyle \frac{1}{1.8} and \displaystyle \frac{1}{2.6}. Notice that the trapezoids extend above the hyperbola, so that

\displaystyle \int_1^{2.6} \frac{dx}{x} < \displaystyle \frac{0.8}{2} \left( 1 + \frac{1}{1.8} \right) + \frac{0.8}{2} \left( \frac{1}{1.8} + \frac{1}{2.6} \right)

\displaystyle \int_1^{2.6} \frac{dx}{x} < 0.9983 < 1

However, the number e is defined to be the place where the area under the curve is exactly equal to 1, and so

\displaystyle \int_1^{2.6} \frac{dx}{x} < \displaystyle \int_1^{e} \frac{dx}{x}

In other words, we know that the area between 1 and 2.6 is strictly less than 1, and therefore a number larger than 2.6 must be needed to obtain an area equal to 1.

Great, so e > 2.6. Can we do better? Sadly, with two equal-sized trapezoids, we can’t do much better. If the height of the trapezoids was h and not 0.8, then the sum of the areas of the two trapezoids would be

\displaystyle \frac{h}{2} \left( 1 + \frac{2}{1+h} + \frac{1}{1+2h} \right)

By either guessing and checking — or with the help of Mathematica — it can be determined that this function of h is equal to 1 at approximately h \approx 0.8019, thus establishing that e > 1 + 2h \approx 2.6039.

e_twotrapezoids

We can try to better with additional trapezoids. With four trapezoids, we can establish that e > 2.6845.

e_fourtrapezoids

With 100 trapezoids, we can show that e > 2.71822.

e_hundredtrapezoidsHowever, trapezoids can only provide a lower bound on e because the original trapezoids all extend over the hyperbola.

green lineTo obtain an upper bound on e, we will use a lower Riemann sum to approximate the area under the curve. For example, notice the following picture of 19 rectangles of width h = 0.1 ranging from x =1 to x = 2.9.

approx_e_upperThe rectangles all lie below the hyperbola. The width of each one is h = 0.1, and the heights vary from \frac{1}{1.1} to \frac{1}{2.9}. Therefore,

\displaystyle \int_1^{2.9} \frac{dx}{x} > \displaystyle 0.1 \left( \frac{1}{1.1}+ \frac{1}{1.2} + \dots + \frac{1}{2.9} \right)

\displaystyle \int_1^{2.9} \frac{dx}{x} > 1.0326 > 1

In other words, we know that the area between 1 and 2.9 is strictly greater than 1, and therefore a number smaller than 2.9 must be needed to obtain an area equal to 1. So, in a nutshell, we’ve shown that e < 2.9.

Once again, additional rectangles can provide better and better upper bounds on e. However, since rectangles do not approximate the hyperbola as well as trapezoids, we expect the convergence to be much slower. For example, with 100 rectangles of width h, the sum of the areas of the rectangles would be

h \displaystyle \left( \frac{1}{1+h} + \frac{1}{1+2h} + \dots + \frac{1}{1+100h} \right)

It then becomes necessary to plug in numbers for h until we find something that’s decently close to 1 yet greater than 1. Or we can have Mathematica do the work for us:

e_hundredrectanglesSo with 100 rectangles, we can establish that e < 2.7333. With 1000 rectangles, we can establish that e < 2.71977.

Clearly, this is a lot of work for approximating e. With all of the work shown in this post, we have shown that e = 2.71\dots, but we’re not yet sure if the next digit is 8 or 9.

In the next post, we’ll explore the other two ways of thinking about the number e as well as their computational tractability.

Day One of my Calculus I class: Part 6

In this series of posts, I’d like to describe what I tell my students on the very first day of Calculus I. On this first day, I try to set the table for the topics that will be discussed throughout the semester. I should emphasize that I don’t hold students immediately responsible for the content of this lecture. Instead, this introduction, which usually takes 30-45 minutes, depending on the questions I get, is meant to help my students see the forest for all of the trees. For example, when we start discussing somewhat dry topics like the definition of a continuous function and the Mean Value Theorem, I can always refer back to this initial lecture for why these concepts are ultimately important.

I’ve told students that the topics in Calculus I build upon each other (unlike the topics of Precalculus), but that there are going to be two themes that run throughout the course:

  1. Approximating curved things by straight things, and
  2. Passing to limits

I’ve then quickly used these themes to solve two completely different problems: (1) finding the speed of a falling object at impact and (2) finding the area under a parabola. I can usually cover these topics in less than 50 minutes, sometimes in 35 minutes. Again, because I’m not immediately holding my students responsible for the contents of this introduction, I feel freer to move a little quicker than I would otherwise in the hopes of showing the forest for all of the trees.

I then ask the obvious question: what do these two questions have to do with each other. One involves the distance-rate-time formula. The other involves the areas of rectangles. At first blush, these two questions seem completely unrelated. And at second blush. And at third blush.

I tell my class that these two apparently unrelated questions are indeed related by something called the Fundamental Theorem of Calculus. Somehow, the process of finding the area under a curve is intimately related to finding an instantaneous rate of change. I then make a bold, eye-catching statement: The Fundamental Theorem of Calculus is one of the greatest discoveries in the history of mankind, period. And, at the ripe old age of 17, 18, or 19 years old, my students are now privileged to understand this great accomplishment.

This ends my introduction to Calculus I. I’ll then begin the more mundane development of limits on the way to formally defining a derivative.

Day One of my Calculus I class: Part 5

In this series of posts, I’d like to describe what I tell my students on the very first day of Calculus I. On this first day, I try to set the table for the topics that will be discussed throughout the semester. I should emphasize that I don’t hold students immediately responsible for the content of this lecture. Instead, this introduction, which usually takes 30-45 minutes, depending on the questions I get, is meant to help my students see the forest for all of the trees. For example, when we start discussing somewhat dry topics like the definition of a continuous function and the Mean Value Theorem, I can always refer back to this initial lecture for why these concepts are ultimately important.

I’ve told students that the topics in Calculus I build upon each other (unlike the topics of Precalculus), but that there are going to be two themes that run throughout the course:

  1. Approximating curved things by straight things, and
  2. Passing to limits

We are now trying to answer the following problem.

Problem #2. Find the area under the parabola f(x) = x^2 between x=0 and x=1.

Using five rectangles with right endpoints, we find the approximate answer of 0.44. With ten rectangles, the approximation is 0.385. With one hundred rectangles (and Microsoft Excel), the approximation is 0.33835. This last expression was found by evaluating

0.01[ (0.01)^2 + (0.02)^2 + \dots + (0.99)^2 + 1^2]

At this juncture, what I’ll do depends on my students’ background. For many years, I had the same group of students for both Precalculus and Calculus I, and so I knew full well that they had seen the formula for \displaystyle \sum_{k=1}^n k^2. And so I’d feel comfortable showing my students the contents of this post. However, if I didn’t know for sure that my students had at least seen this formula, I probably would just ask them to guess the limiting answer without doing any of the algebra to follow.

Assuming students have the necessary prerequisite knowledge, I’ll ask, “What happens if we have n rectangles?” Without much difficulty, they’ll see that the rectangles have a common width of 1/n. The heights of the rectangles take a little more work to determine. I’ll usually work left to right. The left-most rectangle has right-most x-coordinate of 1/n, and so the height of the leftmost rectangle is (1/n)^2. The next rectangle has a height of (2/n)^2, and so we must evaluate

\displaystyle \frac{1}{n} \left[ \frac{1^2}{n^2} + \frac{2^2}{n^2} + \dots + \frac{n^2}{n^2} \right], or

\displaystyle \frac{1}{n^3} \left[ 1^2 + 2^2 + \dots + n^2 \right]

I then ask my class, what’s the formula for this sum? Invariably, they’ve forgotten the formula in the five or six weeks between the end of Precalculus and the start of Calculus I, and I’ll tease them about this a bit. Eventually, I’ll give them the answer (or someone volunteers an answer that’s either correct or partially correct):

\displaystyle \frac{1}{n^3} \times \frac{n(n+1)(2n+1)}{6}, or \frac{(n+1)(2n+1)}{6n^2}.

I’ll then directly verify that our previous numerical work matches this expression by plugging in n=5, n= 10, and n = 100.

I then ask, “What limit do we need to take this time?” Occasionally, I’ll get the incorrect answer of sending n to zero, as students sometimes get mixed up thinking about the width of the rectangles instead of the number of rectangles. Eventually, the class will agree that we should send n to plus infinity. Fortunately, the answer \displaystyle \frac{(n+1)(2n+1)}{6n^2} is an example of a rational function, and so the horizontal asymptote can be immediately determined by dividing the leading coefficients of the numerator and denominator (since both have degree 2). We conclude that the limit is 2/6 = 1/3, and so that’s the area under the parabola.

Day One of my Calculus I class: Part 4

In this series of posts, I’d like to describe what I tell my students on the very first day of Calculus I. On this first day, I try to set the table for the topics that will be discussed throughout the semester. I should emphasize that I don’t hold students immediately responsible for the content of this lecture. Instead, this introduction, which usually takes 30-45 minutes, depending on the questions I get, is meant to help my students see the forest for all of the trees. For example, when we start discussing somewhat dry topics like the definition of a continuous function and the Mean Value Theorem, I can always refer back to this initial lecture for why these concepts are ultimately important.

I’ve told students that the topics in Calculus I build upon each other (unlike the topics of Precalculus), but that there are going to be two themes that run throughout the course:

  1. Approximating curved things by straight things, and
  2. Passing to limits

I then applied these two themes to find the speed of a falling object at impact.

I now switch to a second, completely unrelated (or at least it seems completely unrelated) problem.

Problem #2. Find the area under the parabola f(x) = x^2 between x=0 and x=1.

I draw the picture and ask, “OK, what formula from geometry can we use for this one?” Stunned silence.

I say, “Of course you can’t do this yet. This is a curved thing. Back in high school geometry, you learned (with one exception) the areas of straight things. What straight things had area formulas in high school geometry?” I’ll always get rectangles and triangles as responses. Occasionally, someone will volunteer parallelogram or rhombus or kite.

So I ask the leading question, which of these shapes is easiest? Students always answer, “Rectangles.” Which then leads me to the next question: How can we approximate the area under a parabola with a bunch of rectangles?

Again, stunned silence. I let my students think about it for at least a minute, sometimes two minutes. Hopefully, one student will volunteer the answer that I want, though occasionally I’ll have to coax it out of them.

Eventually either a student volunteers (or else I tell the class) that we ought to use a bunch of thin rectangles. For starters, I’ll use five rectangles and a very rough sketch on the board.

RiemannSum

I’ll start with the right-most rectangle… what is its area? Students immediately see that the width is 1/5, but the length takes a little bit more thought. And I make my students figure it out without me giving them the answer. Eventually, someone notices that the height is simply f(1) = 1, so that the rightmost rectangle has an area of 0.2.

I then move to the rectangle that’s second to the right. This also has a width of 1/5, but the height is (0.8)^2 = 0.64. So the area is 0.128.

Eventually, we get that the sum of the areas is 0.008 + 0.032 + 0.072 + 0.128 + 0.2 = 0.44. Students can easily see that this is a decent approximation to the area under the parabola, but it’s a bit too large.

I then ask the same question that I had before: how can we get a better approximation? Students will usually volunteer either “More rectangles” or “Thinner rectangles,” which of course are logically equivalent. I then proceed with 10 equal-width rectangles. Occasionally, a student volunteers that perhaps we should use thinner rectangles only on the right side of the figure, which of course is a very astute observation. However, I tell my class that, for the sake of simplicity, we’ll stick with rectangles of equal width.

With ten rectangles (and I redraw the picture with ten thin rectangles), the approximation is quickly found to be

0.1 [ (0.1)^2 + (0.2)^2 + \dots + (0.9)^2 + 1^2] = 0.385

I like using ten rectangles, as that’s probably the largest number that can be handled in class without a calculator (until the very last step of adding up the areas).

By now, the class sees what the next steps are: take more and more rectangles. At this point, I’ll resort to classroom technology to make the process a little quicker. I personally prefer Microsoft Excel, though other software packages can be used for this purpose. For 100 rectangles, the class quickly sees that the sum of the rectangles is

0.01 [ (0.01)^2 + (0.02)^2 + \dots + (0.99)^2 +( 1.00)^2] = 0.33835

RiemannSum100

My class can see that the answer is still too large, but it’s certainly closer to the correct answer.

I’ll then tell the class that this is another example of passing to limits, the second theme of calculus. I’ll describe this more fully in the next post.