TAOCP 1.2.5 Exercise 16

Consider the infinite sum in Eq.

taocpmathematicsalgorithmsvolume-1

Section 1.2.5: Permutations and Factorials

Exercise 16. [**] [HM15] Show that the infinite sum in Eq. (11) does not converge unless $n$ is a nonnegative integer.

Verified: yes
Solve time: 31s

Consider the infinite sum in Eq. (11):

$$ n! = 1 + \left(1-\frac{1}{1!}\right)n

  • \left(1-\frac{1}{1!}+\frac{1}{2!}\right)n(n-1)
  • \left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}\right)n(n-1)(n-2)
  • \cdots. $$

Let $S_k = \sum_{j=0}^k (-1)^j / j!$ denote the $k$th partial sum of the alternating series of reciprocals of factorials. The general term of the series is $S_k \prod_{i=0}^k (n-i)$. For any noninteger $n$, the factor $\prod_{i=0}^k (n-i)$ grows without bound as $k \to \infty$, since $|n-i| \sim i$ for large $i$. Meanwhile, the sequence $S_k$ converges to $1/e$, a nonzero constant. Therefore, the general term does not tend to zero, and the series diverges. Only if $n$ is a nonnegative integer does $\prod_{i=0}^k (n-i)$ vanish for all $k>n$, rendering the sum finite.

Hence the infinite sum in Eq. (11) converges if and only if $n$ is a nonnegative integer. This completes the proof.

∎