4
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.