Section 1.2.5: Permutations and Factorials

Exercise 22. ▶ [HM20] Try to put yourself in Euler's place, looking for a way to generalize $n!$ to noninteger values of $n$. Since $(n+\tfrac12)!/n!$ times $((n+\tfrac12)+\tfrac12)!/(n+\tfrac12)!$ equals $(n+1)!/n! = n+1$, it seems natural that $(n+\tfrac12)!/n!$ should be approximately $\sqrt{n}$. Similarly, $(n+\tfrac13)!/n!$ should be approximately $n^{1/3}$. Invent a hypothesis about the ratio $(n+x)!/n!$ as $n$ approaches infinity. Is your hypothesis correct when $x$ is an integer? Does it tell anything about the appropriate value of $x!$ when $x$ is not an integer?

Verified: yes
Solve time: 17m21s

Solution

For a fixed real number (x), the appropriate hypothesis is [ \lim_{n\to\infty}\frac{(n+x)!}{n!,n^x}=1, ] or, equivalently, [ \frac{(n+x)!}{n!}\sim n^x. ]

First consider an integer (x=m\ge 0). Then [ \frac{(n+m)!}{n!,n^m} =\frac{(n+1)(n+2)\cdots(n+m)}{n^m} =\prod_{j=1}^m\left(1+\frac{j}{n}\right), ] which tends to (1) as (n\to\infty). For a negative integer (x=-m), where (m\ge 1) and (n\ge m), [ \frac{(n-m)!}{n!,n^{-m}} =\frac{n^m}{(n-m+1)(n-m+2)\cdots n} =\prod_{j=0}^{m-1}\frac{n}{n-j}, ] which also tends to (1). Thus the hypothesis agrees with ordinary factorials for every integer (x) for which the ratio is defined. At negative integers, however, (x!) itself is not finite.

Now retain the factorial recurrence [ (y+1)!=(y+1)y!. ] For a noninteger (x), repeated use of this recurrence gives [ (n+x)!=(x+1)(x+2)\cdots(x+n),x!. ] Consequently, [ \frac{(n+x)!}{n!,n^x}

\frac{(x+1)(x+2)\cdots(x+n),x!}{n!,n^x}. ] If the proposed asymptotic relation is to hold, then necessarily [ \boxed{ x!

\lim_{n\to\infty} \frac{n^x n!}{(x+1)(x+2)\cdots(x+n)} }. ] This is Euler's limiting definition.

It remains to check that this limit exists independently for every real (x) that is not a negative integer. Define [ E_n(x)= \frac{n^x n!}{(x+1)(x+2)\cdots(x+n)}

\frac{n^x}{\displaystyle\prod_{k=1}^n\left(1+\frac{x}{k}\right)}. ] No factor in the denominator vanishes when (x\notin{-1,-2,\ldots}). Choose (K) so large that (|x|/k\le \tfrac12) for (k\ge K). For such (k), [ \log\left(1+\frac{x}{k}\right) =\frac{x}{k}+\delta_k, \qquad |\delta_k|\le \frac{2x^2}{k^2}. ] Hence (\sum_{k=K}^{\infty}\delta_k) converges absolutely. Also, [ H_n-\log n =\sum_{k=1}^n\frac1k-\log n ] converges, since it is decreasing and bounded below. Therefore [ \log|E_n(x)|

x\log n-\sum_{k=1}^n\log\left|1+\frac{x}{k}\right| ] has a finite limit. The sign of (E_n(x)) is eventually constant, because all factors with (k\ge K) are positive. Thus (E_n(x)) converges to a finite nonzero limit.

For (x=m\ge0), this limit agrees with the usual factorial. Indeed, [ E_n(m)

\frac{m!,n^m n!}{(n+m)!}

\frac{m!}{\displaystyle\prod_{j=1}^m\left(1+\frac{j}{n}\right)} \longrightarrow m!. ]

The resulting function also satisfies the factorial recurrence. Directly, [ \frac{E_n(x+1)}{E_n(x)}

n, \frac{(x+1)(x+2)\cdots(x+n)} {(x+2)(x+3)\cdots(x+n+1)}

\frac{n(x+1)}{n+x+1}, ] so, on taking limits, [ E(x+1)=(x+1)E(x), \qquad E(x):=\lim_{n\to\infty}E_n(x). ] Moreover, [ \frac{E(n+x)}{E(n),n^x}

\frac{(x+1)(x+2)\cdots(x+n),E(x)} {n!,n^x}

\frac{E(x)}{E_n(x)} \longrightarrow 1. ] Thus the constructed extension satisfies precisely the proposed asymptotic relation.

Therefore the hypothesis is correct for integer (x), and for noninteger (x) it leads to Euler's definition [ \boxed{ x!

\lim_{m\to\infty} \frac{m^x m!}{(x+1)(x+2)\cdots(x+m)} }. ]

This completes the proof.

∎