# Proving Riordan's identity that $\sum_{k=1}^{n} {n-1 \choose k-1} \frac{k!}{n^k}=1$

In a book titled "Advances in Problem Solving," authored by Sailesh Shirali, Riordan's identity is mentioned which can also be written as $$S=\sum_{k=1}^{n} {n-1 \choose k-1} \frac{k!}{n^k}=1~~~~(1)$$ Here, we prove it by the integral representation of $$(j+1)!$$ as: $$S=\sum_{j=0}^{n-1} {n-1 \choose j} \frac{(j+1)!}{n^{j+1}}=\sum_{j=0}^{n-1} {n-1 \choose j} \frac{1}{n^{j+1}} \int_{0}^{\infty} x^{j+1} e^{-x} dx$$ $$\implies S=\frac{1}{n^{n}}\int_{0}^{\infty} x ~(n+x)^{n-1} e^{-x} dx=n^{-n}\int_{0}^{\infty} [(x+n)^n-n(x+n)^{n-1}]~ e^{-x} dx$$ $$S=-n^{-n}\left. (x+n)^n~ e^{-x}\right|_{0}^{\infty}=1.$$

It will be interesting to see other approaches for proving (1).

We shall count the number of length $$n+1$$ sequences $$(x_1,\ldots,x_{n+1})$$ over a set of $$n$$ elements in two different ways.

The first is to just independently choose each $$x_i$$, yielding $$n^{n+1}$$ sequences.

Alternatively, let $$x_{k+1}$$ be the first repeated element in the sequence (a repetition must occur because the length of the sequence is greater than $$n$$). The first $$k$$ elements of the sequence can be chosen in $$k!\binom{n}{k}$$ ways (they must all be distinct), and $$x_{k+1}$$ can be chosen in exactly $$k$$ ways (choosing which of the first $$k$$ elements is repeated). The elements at the remaining $$n-k$$ positions can then be chosen in $$n^{n-k}$$ ways (there is no restriction on them). Multiplying these together and summing over $$k$$, we get

$$n^{n+1}=\sum_{k=0}^nk!\binom{n}{k}\cdot k\cdot n^{n-k}$$ $$1 = \sum_{k=0}^n \frac{k}{n}\binom{n}{k}\cdot\frac{k!}{n^k}$$ $$1=\sum_{k=1}^n\binom{n-1}{k-1}\frac{k!}{n^k}$$ which is exactly what we want.

We seek to show that

$$S= \sum_{k=0}^{n-1} {n-1\choose k} \frac{(k+1)!}{n^{k+1}} = 1.$$

The sum is

$$\frac{(n-1)!}{n} \sum_{k=0}^{n-1} \frac{k+1}{(n-1-k)!} \frac{1}{n^k}.$$

We get without the factor in front

$$\sum_{k=0}^{n-1} \frac{-n+k+1}{(n-1-k)!} \frac{1}{n^k} + \sum_{k=0}^{n-1} \frac{n}{(n-1-k)!} \frac{1}{n^k} \\ = - \sum_{k=0}^{n-2} \frac{n-1-k}{(n-1-k)!} \frac{1}{n^k} + \sum_{k=0}^{n-1} \frac{1}{(n-1-k)!} \frac{1}{n^{k-1}} \\ = - \sum_{k=0}^{n-2} \frac{1}{(n-2-k)!} \frac{1}{n^k} + \sum_{k=0}^{n-1} \frac{1}{(n-1-k)!} \frac{1}{n^{k-1}} \\ = - \sum_{k=1}^{n-1} \frac{1}{(n-1-k)!} \frac{1}{n^{k-1}} + \sum_{k=0}^{n-1} \frac{1}{(n-1-k)!} \frac{1}{n^{k-1}} \\ = \frac{1}{(n-1)!} \frac{1}{n^{-1}}.$$

Restoring the factor in front we find

$$\frac{(n-1)!}{n} \times \frac{1}{(n-1)!} \frac{1}{n^{-1}} = 1$$

as claimed.