Basic properties of logarithms and factorials
This theory bit recalls some basic properties of two special functions, the logarithm and the factorial.
Logarithms
Recall that, for each b\in \mathbb R_+\setminus \{1\}, the logarithm in base b (denoted as \log_b(\cdot)) is the unique function from \mathbb R_+ to \mathbb R such that \log_b(b^x)=b^{\log_b(x)}=x\ . In particular, \log_2(2^x)=2^{\log_2(x)}=x and \ln(e^x)=e^{\ln(x)}=x, since \ln(\cdot) is just an alias of \log_e(\cdot).
It follows immediately from the definition (how?) that
- \log_b(xy)=\log_b(x)+\log_b(y)
- for all a,b\in \mathbb R_+\setminus \{1\}, \displaystyle\log_a(x)=\frac{\log_b(x)}{\log_b(a)}.
- for every r\in \mathbb R, \displaystyle\log_b(x^r)=r\log_b(x).
\lim_{x\to \infty}\frac{\log_a(x)}{x^b}=0\, for all b> 0.
The factorial
The factorial of a natural number n (denoted as n!) is the number of different possible ways of arranging n distinct obects into a sequence. (0!=1)
Factorials exhibit a quite fast growth as the Stirling approximation shows.
n!\sim\sqrt{2\pi n} \left(\frac{n}{e}\right)^n\ , where \sim means that the ratio of n! and \sqrt{2\pi n} \left(\frac{n}{e}\right)^n tends to 1 as n\to +\infty. More precisely, n!=\sqrt{2\pi n} \left(\frac{n}{e}\right)^n\left(1+O\left(\frac{1}{n}\right)\right)\ .
The O\left(\frac{1}{n}\right) in the equality above is hiding terms that for all large n are at most proportional to \frac{1}{n}. Indeed, the equality above using more terms would be {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}-{\frac {139}{51840n^{3}}}-{\frac {571}{2488320n^{4}}}+\cdots \right).}
Taking \log_2 the Stirling’s approximation becomes \log_2(n!)=n\log_2(n)-n\log_2(e)+\frac{1}{2}\log_2(2\pi n)+O\left(\frac{1}{n}\right)\ , where the O-notation means that for all large values of n, the difference between \log_2(n!) and n\log_2(n)-n\log_2(e)+\frac{1}{2}\log_2(2\pi n) will be at most proportional to \frac{1}{n}.