Approximation of log(n!)

Question

I just finished calculus 1 (derivative and integral) then I take another course on calculus 2. In the video the professor talks about the the series $$\frac{n!}{(\frac{n}{e})^n}$$

He shows the approximation of the numerator ($n!$) and the denominator ($(\frac{n}{e})^n$) he approximates $\log(n!)$ using $$\sum_{k=1}^n\log(k) \approx \int_1^n\log(x) \text{d}x$$

I'm very curious because I think the $\log(n!)$ is a step function. I tried it with graphing calculator here but it shows continuous function. Is the calculator wrong? Because $n!$ has whole number as a domain so $\log(n!)$ should also be a step function?

My second question is can we apply integral to a step function? What is the result different from continuous function, and how can we distinguish. For example when we have $f(x) = x^2$ and we want to do integral with the step domain (whole number) or all the domain?

Here is the video (you can go and view it at 2:30)

I'm a beginner in this field please explain a step by step and beginner friendly to me.

Answer 1

Firstly, $\log(n!)$ is not a step function, because it's not a function defined on (an interval of) the reals; it is defined on a discrete set. A step function, roughly speaking, is a function with a discrete range. This one is a function with a discrete domain.

Secondly, both $\displaystyle\sum_{k=1}^n\log k\;$ and $\displaystyle\int_1^n\log x\,\mathrm d\mkern1mu x\;$ are functions of $n$. Your professor is asserting that these two expressions are equivalent at $\infty$ (denoted $\sim_\infty$) in a very precise sense, not that their values are approximately the same (denoted $\;\approx$), which is not a mathematically defined notion.

The precise definition of equivalence here is that $$\lim_{n\to\infty}\frac{\displaystyle\sum_{k=1}^n\log k}{\displaystyle\int_1^n\log x\,\mathrm d\mkern1mu x}=1.$$

Thus one might say, very very roughly, that $\;\approx\;$ means ‘absolutely almost equal’, while $\;\sim\;$ means ‘comparatively almost equal’.

Answer 2

First question : It exists a function called the Gamma function that is a "non-step" factorial. This means it is a smooth curve that somehow extends the notion of factorial to any real (complex) numbers. In particular, for any positive integer, the value of the gamma function and the classic factorial function are the same (shifted by $1$). I give you some values : $$ \Gamma(1) = 0! = 1 \\ \Gamma(2) = 1! = 1 \\ \Gamma(3) = 2! = 2 \\ \Gamma(4) = 3! = 6 \\ \Gamma(3/2) = \frac{1}{2}! = \frac{\sqrt{\pi}}{2} $$ Many math softwares can evaluate non-integer factorial by using this gamma function !

Second question : Yes ! You simply cut the steps into a sum of integral. Think of the function floor $f(x) = \lfloor x \rfloor$. And let's say you want to compute its integral : $$ \int_0^3 f(x) dx = \int_0^1 f(x) dx + \int_1^2 f(x) dx + \int_2^3 f(x) dx \\ = \int_0^1 0\ dx + \int_1^2 1\ dx + \int_2^3 2\ dx = \\ 0 + 1 + 2 = 3 $$ On the other hand, if you consider simply the non-step function $g(x) = x$ then $\int_0^3 g(x) dx = 9/2$ which is close but not exactly the same as with $f(x)$. Simply draw the two functions and $\textit{see}$ the area under their curve !

Answer 3

It is not terribly difficult to compare: $$ \color{blue}{C_n} = \int_{1}^{n}\log(x)\,dx =\color{blue}{n\log(n)-n+1},\qquad \color{purple}{D_n} = \sum_{k=1}^{n}\log(k).$$ Assuming $n\geq 2$, summation by parts leads to: $$ \color{purple}{D_n} = n \log n -\sum_{k=1}^{n-1} k \log\left(1+\frac{1}{k}\right)=\color{blue}{n\log(n)-n+1}+\sum_{k=1}^{n-1}\left(1-k\log\frac{k+1}{k}\right) $$ but: $$ 0\leq 1-k\log\left(1+\frac{1}{k}\right)\leq \frac{1}{2k} $$ hence:

$$\color{blue}{C_n} \leq \color{purple}{D_n} \leq \color{blue}{C_n}+\frac{\log n}{2}.$$

Answer 4

Using the Abel's summation it is very easy to see that $$S_{n}=\sum_{k=1}^{n}\log\left(n\right)=\sum_{k=1}^{n}1\cdot\log\left(n\right) $$ $$=n\log\left(n\right)-\int_{1}^{n}\frac{\left\lfloor t\right\rfloor }{t}dt $$ where $\left\lfloor t\right\rfloor $ is the floor function. Since $t-1\leq\left\lfloor t\right\rfloor \leq t $ we have $$n\log\left(n\right)-n-1\leq S_{n}\leq n\log\left(n\right)-n+1+\log\left(n\right). $$ hence $$\int_{1}^{n}\log\left(t\right)dt\leq S_{n}\leq\int_{1}^{n}\log\left(t\right)dt+\log\left(n\right).$$

Answer 5

There is a standard trick here. In what follows, $a,b,k,n$ all refer to integer variables, $x$ to a real variable, and $\lfloor \ \rfloor$ refers to the floor function: $\lfloor x \rfloor$ is the largest integer less than or equal to $x$.

---

First, we can relate the sum to the integral of a step function by using the fact $$ f(n) = \int_{n}^{n+1} f(\lfloor x \rfloor) \, \mathrm{d} x = \int_{n-1}^{n} f(\lfloor x+ 1 \rfloor) \, \mathrm{d} x $$ and consequently $$ \sum_{k=a}^b f(k) = \int_a^{b+1} f(\lfloor x \rfloor) \, \mathrm{d} x = \int_{a-1}^{b} f(\lfloor x+ 1 \rfloor) \, \mathrm{d} x $$ This is probably what made you think of step functions; while $\log(k)$ is itself not a step function, $\log \lfloor x \rfloor$ is. (the other possibility is that you were thinking of something like $\sum_{k=1}^{\lfloor x \rfloor} \log k$)

---

Second, for any nondecreasing function $f(x)$, we have inequalities

$$ f(n-1) \leq f(\lfloor n \rfloor) \leq f(n) \leq f(\lfloor n+1 \rfloor) $$

which carries over to the integrals:

$$ \int_{a-1}^{b-1} f(x) \, \mathrm{d} x \leq \int_a^b f(\lfloor x \rfloor) \, \mathrm{d} x \leq \int_a^b f(x) \, \mathrm{d} x \leq \int_{a+1}^{b+1} f(\lfloor x \rfloor) \, \mathrm{d} x $$

and consequently,

$$ \int_{a-1}^{b} f(x) \, \mathrm{d} x \leq \sum_{k=a}^b f(k) \leq \int_a^{b+1} f(x) \, \mathrm{d} x $$

---

Applying this to the problem at hand, we get

$$ \int_{1}^{n} \log x \, \mathrm{d} x \leq \sum_{k=2}^n \log k \leq \int_2^{n+1} \log x \, \mathrm{d} x $$

which we can then use to make rigorous estimates about the size of the sum.

(I split off the $k=1$ term to avoid problems with the integrals; but it's zero anyways so it doesn't affect the total. You could get a more accurate estimate by splitting off more terms, computing them exactly, then adding the result back into the inequality)