스털링 근사식_{(Stirling’s approximation)}이란 충분히 큰 양의 정수 $n \in \N$에 대하여 계승_(factorial) $n!$를 근사적으로 구하는 방법이다. 양의 정수 $n \in \N$에 대하여 함수 $s(n) = \sqrt{2 \pi n} \Big( \dfrac{n}{e} \Big)^{n}$을 정의하자. 스털링 근사식에 의하면 \[ \lim_{n \to \infty} \frac{n!}{s(n)} = \lim_{n \to \infty} \frac{n!}{\sqrt{2\pi n} \big( \frac{n}{e} \big)^{n}} = 1 \] 가 성립한다. 즉, 충분히 큰 양의 정수 $n \in \N$에 대하여, $n! \sim s(n)$과 같이 나타낼 수 있다.

스털링 근사식은 감마분포_{(Gamma distribution)}를 중심극한정리_{(central limit theorem)}를 이용하여 정규분포_{(normal distribution)}로 근사하여 증명하는 방법; 가우스 적분_{(Gaussian integral)}을 이용하는 방법; 적분을 근사하는 라플라스 방법_{(Laplace's method)}을 이용하는 방법 등 다양한 방법으로 증명이 가능하다. 이번 포스트의 목적은 이러한 기교들을 사용하지 않고, 스털링 근사식을 최대한 고등학교 정도의 수준 수학을 이용하여 증명해 보는 것이다.

$ $

$ $

증명. 적분에 대한 사다리꼴 공식_{(trapezoidal rule)}은 다음과 같다: 함수 $f(x)$가 구간 $[a,\, b]$에서 두번 미분 가능하다고 하자. 그러면 적당한 $\xi \in (a,\, b)$가 존재하여 다음을 만족한다. \[ \int_{a}^{b} f(x) \,dx = \frac{1}{2} \Big( f(a) + f(b) \Big) (b - a) - \frac{1}{12}f''(\xi)(b - a)^{3}. \] 이제 $f(x) = \log(x)$로 두고 위 공식을 적용하면, 적당한 $\xi_{k} \in (k,\, k+1)$에 대하여, \begin{align*} \int_{0}^{n} \log(x) \,dx &= \sum_{k=1}^{n-1} \int_{k}^{k+1} \log(x) \,dx \\[2px] &= \sum_{k=1}^{n-1} \left[ \frac{1}{2} \Big( \log(k) + \log(k+1) \Big) + \frac{1}{12 \xi_{k}^{2}} \tag*{$\myblue{(1)}$}\right] \end{align*} 이 성립한다. (위 식의 좌변은 이상적분_{(improper integral)}이지만 수렴하므로, 증명에 문제는 없다.) 이제 증명의 편의를 위해 $D_{k} = 1/(12 \xi_{k}^{2})$으로 정의하자. 그러면 모든 자연수 $k$에 대하여 $D_{k} > 0$이고, 또한 $k < \xi_{k}$라는 사실로부터 \[ D := \sum_{k=1}^{\infty} D_{k} = \frac{1}{12} \sum_{k=1}^{\infty} \frac{1}{\xi_{k}^{2}} < \frac{1}{12} \sum_{k=1}^{\infty} \frac{1}{k^{2}} < \infty, \] 즉, $D_{k}$의 무한합이 수렴함을 알 수 있다. 이제 \[ \varepsilon_{n} = D - \sum_{k=1}^{n-1} D_{k} = \sum_{k=n}^{\infty} D_{k} \] 를 정의하자. 그러면 식 $\myblue{(1)}$을 \[ \int_{0}^{n} \log(x) \,dx = \frac{1}{2} \sum_{k=1}^{n-1} \Big( \log(k) + \log(k+1) \Big) + D - \varepsilon_{n} \] 과 같이 변형할 수 있다. 이제 위 식의 좌변과 우변을 각각 정리하면, \[ n \log(n) - n + 1 = \log(n!) - \frac{1}{2} \log(n) + D - \varepsilon_{n}. \] 따라서 \begin{align*} \log(n!) &= \Big( n + \frac{1}{2} \Big) \log(n) - n + 1 - D + \varepsilon_{n} \\[2px] &= \log \left( e^{1-D} \sqrt{n} \Big( \frac{n}{3} \Big)^{n} e^{\varepsilon_{n}} \right) \end{align*} 이고 이를 정리하면, \[ n! = e^{1-D} \sqrt{n} \Big( \frac{n}{e} \Big)^{n} e^{\varepsilon_{n}} \tag*{$\myblue{(2)}$} \] 이 성립함을 알 수 있다.

$ $

다음으로 식 $\myblue{(2)}$에서 $e^{1 - D} = \sqrt{2\pi}$임을 보이자. 이를 위해 다음의 월리스의 곱공식_{(Wallis' product formula)}를 이용할 것이다. (월리스의 곱공식에 대한 (고등학교 수준의) 증명은 이곳에서 확인해 볼 수 있다.) \begin{align*} \frac{\pi}{2} &= \lim_{n \to \infty} \prod_{k=1}^{n} \left( \frac{2k}{2k-1} \cdot \frac{2k}{2k+1} \right) \\[2px] &= \lim_{n \to \infty} \prod_{k=1}^{n} \left( \frac{(2k)^2}{(2k-1)(2k+1)} \cdot \frac{(2k)^2}{(2k)(2k)} \right) \\[2px] &= \lim_{n \to \infty} \frac{2^{4n} (n!)^{4}}{((2n)!)^{2} (2n+1)} \end{align*} 이제 식 $\myblue{(2)}$를 월리스의 곱공식에 대입하여 정리하면, \begin{align*} \frac{\pi}{2} &= \lim_{n \to \infty} \frac{2^{4n} \Big[ e^{1-D} \sqrt{n} \Big( \dfrac{n}{e} \Big)^{n} e^{\varepsilon_{n}} \Big]^{4}}{\Big[ e^{1-D} \sqrt{2n} \Big( \dfrac{2n}{e} \Big)^{2n} e^{\varepsilon_{2n}} \Big]^{2} (2n+1)} \\[2px] &= \lim_{n \to \infty} e^{2(1-D)} \frac{n}{2(2n+1)} e^{4\varepsilon_{n} - 2\varepsilon_{2n}} \\[2px] &= \frac{1}{4}e^{2(1-D)} \end{align*} 를 얻는다. (위 계산에서 $\displaystyle \lim_{n \to \infty} \varepsilon_{n} = \lim_{n \to \infty} \varepsilon_{2n} = 0$이라는 사실을 이용하였다.) 마지막으로 위 식을 정리하면 \[ e^{1-D} = \sqrt{2\pi} \tag*{$\myblue{(3)}$} \] 가 됨을 확인할 수 있다. 여기까지의 결과를 정리하면 임의의 양의 정수 $n \in \N$에 대하여 적당한 양의 실수 $\varepsilon_{n} > 0$이 존재하여 $n! = \sqrt{2 \pi n} \Big( \dfrac{n}{e} \Big)^{n} e^{\varepsilon_{n}}$으로 나타낼 수 있다는 결론을 얻을 수 있다. 또한 실수열 $(\varepsilon_{n})$은 $n \to \infty$일 때, $\varepsilon_{n} \to 0$를 만족한다.

이제 $\varepsilon_{n}$의 상계와 하계를 구해보자. 이를 위해서 $D_{k}$의 값을 다시 계산해보면, \begin{align*} D_{k} &= \int_{k}^{k+1} \log(x) \,dx - \frac{1}{2} \Big[ \log(k) + \log(k+1) \Big] \\[2px] &= \Big[ (k+1) \log(k+1) - (k+1) - k \log(k) + k \Big] - \frac{1}{2} \Big[ \log(k) + \log(k+1) \Big] \\[2px] &= \Big( k + \frac{1}{2} \Big) \log \Big( \frac{k+1}{k} \Big) - 1 \end{align*} 이제 $x_{k} = \dfrac{1}{2k+1}$로 정의하자. 그러면 $\dfrac{1 + x_{k}}{1 - x_{k}} = \dfrac{k+1}{1}$가 성립함을 쉽게 확인할 수 있다. 따라서 \[ D_{k} = \frac{1}{2x_{k}} \log \Big( \frac{1 + x_{k}}{1 - x_{k}} \Big) - 1 \tag*{$\myblue{(4)}$} \] 를 얻는다. 한 편, $\abs{x} < 1$인 범위에서 $\log(1+x)$와 $\log(1-x)$의 테일러 전개_{(Taylor expansion)}를 이용하면, \[ \log \Big( \frac{1+x}{1-x} \Big) = 2 \left( x + \frac{x^{3}}{3} + \frac{x^{5}}{5} + \cdots \right) \] 를 얻고 이를 이용하여 다음과 같이 식 $\myblue{(4)}$에 나오는 $D_{k}$ 값의 상계를 구할 수 있다. \begin{align*} D_{k} &= \frac{1}{3(2k+1)^{2}} + \frac{1}{5(2k+1)^{4}} + \frac{1}{7(2k+1)^{6}} + \cdots \\[2px] & < \frac{1}{3} \left[ \frac{1}{(2k+1)^{2}} + \frac{1}{(2k+1)^{4}} + \frac{1}{(2k+1)^{6}} + \cdots \right] \\[2px] &= \frac{1}{3} \cdot \frac{1}{(2k+1)^{2} - 1} \\[2px] &= \frac{1}{3} \cdot \frac{1}{4k(k+1)} \\[2px] &= \frac{1}{12} \Big( \frac{1}{k} - \frac{1}{k+1} \Big). \end{align*} 이를 이용하여 $\varepsilon_{n}$의 상계를 망원급수_{(telescoping series)}의 합을 이용하여 계산할 수 있다. \[ \varepsilon_{n} = \sum_{k=n}^{\infty} D_{k} < \frac{1}{12} \sum_{k=n}^{\infty} \Big( \frac{1}{k} - \frac{1}{k+1} \Big) = \frac{1}{12n}. \tag*{$\myblue{(5)}$} \]

$ $

계산은 조금더 복잡하지만 $\varepsilon_{n}$의 하계 또한 비슷한 방법으로 구할 수 있다. 먼저 $D_{k}$의 하계를 아래와 같이 ($\varepsilon_{n}$의 하계를 망원급수_{(telescoping series)}를 이용하여 계산할 수 있도록) 구해보자. \begin{align*} D_{k} &= \frac{1}{3(2k+1)^{2}} + \frac{1}{5(2k+1)^{4}} + \frac{1}{7(2k+1)^{6}} + \cdots \\[2px] & > \frac{1}{3(2k+1)^{2}} + \frac{1}{3^{2}(2k+1)^{4}} + \frac{1}{3^{3}(2k+1)^{6}} + \cdots \\[2px] &= \frac{1}{3(2k+1)^{2} - 1} \\[2px] &= \frac{1}{12k^{2} + 12k + 2} \\[2px] &= \frac{12}{144k^{2} + 144k + 24}. \end{align*} 여기서 위 식의 분모를 다음과 같이 조작하자. \begin{align*} 144k^{2} + 144k + 24 & < 144k^{2} + 168k + 13 \\[2px] &= (12k+1)(12k+13) \\[2px] &= (12k+1) \big( 12(k+1)+1 \big) \end{align*} 그러므로 $D_{k} > \dfrac{1}{12k+1} - \dfrac{1}{12(k+1)+1}$이 성립하고, \[ \varepsilon_{n} = \sum_{k=n}^{\infty} D_{k} > \sum_{k=n}^{\infty} \Big( \frac{1}{12k+1} - \frac{1}{12(k+1)+1} \Big) = \frac{1}{12n+1}. \tag*{$\myblue{(6)}$} \] 를 만족한다. 따라서 식 $\myblue{(5)}$, $\myblue{(6)}$에 의해 모든 양의 정수 $n \in \N$에 대하여 $\dfrac{1}{12n+1} < \varepsilon_{n} < \dfrac{1}{12n}$가 성립하고, 증명이 완료된다.$ $

$ $

참고.

1. 위 정리에 의해서, 양의 정수 $n \in \N$이 충분히 클 때, $n!$을 $s(n) = \sqrt{2\pi n} \Big( \dfrac{n}{e} \Big)^{n}$으로 근사할 수 있음을 알 수 있다. 즉, \[ \lim_{n \to \infty} \frac{n!}{s(n)} = \lim_{n \to \infty} \frac{n!}{\sqrt{2\pi n} \big( \frac{n}{e} \big)^{n}} = 1 \] 이 성립한다. 이 사실은 $n!$이 포함된 극한을 계산할 때 굉장히 유용하게 사용된다.
2. $e^{\varepsilon_{n}} > 1$이 성립하므로, 임의의 양의 정수 $n \in \N$에 대하여 다음의 부등식 $n! > s(n)$이 성립한다. 다시 말해 $s(n)$은 $n!$을 언제나 보다 작은 값으로 근사하게 된다. 따라서 계산의 정확도를 높히기 위해서 $s(n) = \sqrt{2\pi n} \Big( \dfrac{n}{e} \Big)^{n}$ 대신 $\bar{s}(n) = \sqrt{2\pi n} \Big( \dfrac{n}{e} \Big)^{n} e^{\frac{1}{12n+1}}$을 사용할 수 있다.
3. 스털링 근사식은 아브라함 드무아브르_{(Abraham de Moivre)}에 의해 최초로 발견되었다고 알려져 있다. 그는 적당한 양의 실수 $C \in \R$가 존재하여 \[ n! \sim C \sqrt{n} \Big( \frac{n}{e} \Big)^{n} \] 과 같이 근사할 수 있음을 보였고, 이후 스털링에 의해 $C = \sqrt{2 \pi}$가 성립한다는 사실이 증명되었다고 한다.

$ $

예제 1. (공정한) 동전을 $2n$번 던졌을 때, 앞면과 뒷면이 각각 $n$번씩 나올 확률은 $\displaystyle \binom{2n}{n} \Big( \frac{1}{2} \Big)^{2n}$이다. 이 값의 크기를 근사적으로 확인해 보기 위하여 스털링 근사식을 이용하면, \[ \binom{2n}{n} \Big( \frac{1}{2} \Big)^{2n} = \frac{(2n)!}{2^{2n} (n!)^2} \sim \frac{\sqrt{2 \pi (2n)} \Big( \dfrac{2n}{e} \Big)^{2n}}{2^{2n} \Big[ \sqrt{2 \pi n} \Big( \dfrac{n}{e} \Big)^{n} \Big]^{2}} = \frac{1}{\sqrt{\pi n}} \] 이 성립함을 알 수 있다. 이 결과를 폴리아의 무작위 보행_{(random walk)} 문제를 증명하는 데 이용할 수 있다.$ $

$ $

예제 2. 스털링 근사를 이용하여 충분히 큰 $n$에 대하여 $(2n)!!$과 $(2n-1)!!$의 값을 비교해 보자. (단, $n!!$은 양의 정수 $n \in \N$에 대한 이중계승_{(double factorial)}을 나타낸다.) 먼저 이중계승의 성질에 의해 $(2n)!! = 2^n n!$이고 $(2n)! = (2n)!! (2n-1)!!$이 성립함을 확인할 수 있다. 이제 이 사실들과 스털링 근사식을 이용하면 \[ \frac{(2n-1)!!}{(2n)!!} = \frac{(2n)!}{\big[ (2n)!! \big]^2} = \frac{(2n)!}{\big[ 2^n n! \big]^2} = \frac{(2n)!}{2^{2n} (n!)^2} \sim \frac{1}{\sqrt{\pi n}} \] 을 얻는다.$ $

$ $

예제 3. 충분히 큰 양의 정수 $n \in \N$에 대하여, $n!$의 자릿수는 $\lfloor \log_{10}(n!) \rfloor + 1$로 나타낼 수 있다. 이 값을 구하기 위하기 위해서 $s(n) = \sqrt{2\pi n} \Big( \dfrac{n}{e} \Big)^{n}$를 정의하면 스털링 근사식에 의해 다음 부등식 \[ 1 < e^{\frac{1}{12n+1}} < \frac{n!}{s(n)} < e^{\frac{1}{12n}} \] 을 얻는다. 이제 위 식의 양변에 자연로그를 취하면, \[ 0 < \log(n!) - \log(s(n)) < \frac{1}{12n}. \] 이고 위 식의 양변을 $\log(10)$으로 나누어주고 정리하면, \[ \log_{10}(s(n)) < \log_{10}(n!) < \log_{10}(s(n)) + \frac{1}{12n \log(10)} \tag*{$\myblue{(7)}$} \] 을 얻는다. 이를 이용하면, 예를 들어 $n = 100$인 경우, \[ \log_{10}(s(100)) < \log_{10}(100!) < \frac{1}{1200 \log(10)} + \log_{10}(s(100)) \] 이고, 실제로 계산을 해 보면 $\log_{10}(s(100)) < 157.97$이고 $\frac{1}{1200 \log(10)} < 0.0004$ 이므로 \[ \lfloor \log_{10}(100!) \rfloor + 1 < \lfloor 157.9704 \rfloor + 1 = 158 \] 이 되어 $100!$은 $158$자리를 갖는 수임을 확인해 볼 수 있다.

$ $

위 부등식 $\myblue{(7)}$에 의해, 대부분의 $n \in \N$에 대하여 $\lfloor \log_{10}(n!) \rfloor = \lfloor \log_{10}(s(n)) \rfloor$이 성립할 것이라 예상할 수 있다. 실제로 $\lfloor \log_{10}(n!) \rfloor = \lfloor \log_{10}(s(n)) \rfloor + 1$이 성립하는 최초의 양의 정수 $n \in \N$은 $n = 6,561,101,970,383$임이 알려져 있다.$ $