Interesting combinatorial identity A friend of mine has shown me the following combinatorial identity:
$$
\sum_{k=0}^n{x\choose k}\frac{k\cdot k!}{x^{k+1}}
= 1 - {x\choose n+1}\frac{(n+1)!}{x^{n+1}}
$$
I feel like I lack tools to tackle that problem. Hints?
 A: In this situation a simple induction on $n$ works. When $n=0$,
your formula becomes $0=1-1$, which is admittedly true. Now, if the formula
holds for $n$, we have
$$
\begin{array}{lcl}
\sum_{k=0}^{n+1}{x\choose k}\frac{k\cdot k!}{x^{k+1}}
&=& {x\choose n+1}\frac{(n+1)\cdot (n+1)!}{x^{n+2}}+\sum_{k=0}^{n}{x\choose k}\frac{k\cdot k!}{x^{k+1}} \\
&=&  {x\choose n+1}\frac{(n+1)\cdot (n+1)!}{x^{n+2}}+1 - {x\choose n+1}\frac{(n+1)!}{x^{n+1}} \\
&=&  1+{x\choose n+1}\Bigg(\frac{(n+1)\cdot (n+1)!}{x^{n+2}}-
\frac{(n+1)!}{x^{n+1}}\Bigg) \\
&=&  1+{x\choose n+1}\Bigg(\frac{(n+1)!}{x^{n+2}}(n+1-x)\Bigg) \\
&=&  1+{x\choose n+1}\frac{x-(n+1)}{n+2}\Bigg(\frac{(n+2)!}{x^{n+2}}\Bigg) \\
&=&  1-{x\choose n+2}\Bigg(\frac{(n+2)!}{x^{n+2}}\Bigg) \\
\end{array}
$$
so that the formula holds for $n+1$ also. This finishes the proof by induction.
A: Here is a probabilistic interpretation of the identity.
Suppose you have $x$ colored balls labelled, $1,2,3,...,x$, and you pick $(n+1)$ balls independently and uniformly at random with replacement, then both sides of the identity give the probability that you do not pick two balls with the same color.
For the RHS,
The probability that the $(n+1)$ balls you pick are of different colors is
$${x\choose n+1}\frac{(n+1)!}{x^{n+1}}$$
Hence the probability that you have at least two of the same color is
$$1 - {x\choose n+1}\frac{(n+1)!}{x^{n+1}}$$
For the LHS,
Note that in order to have a color repeat, there must be a minimum index $k$ for which the chosen balls $b_1,b_2,b_3,...,b_k$ are all distinct but $b_{k+1} \in \{b_1,b_2,b_3,...,b_k\}$.
But we note that there are
$${x\choose k}k\cdot k!$$
possible ways of this happening for a fixed $k$.
So it occurs with probability
$${x\choose k}\frac{k\cdot k!}{x^{k+1}}$$
Since this minimum index can vary from $1,2,...,n$ we can see that the total probability of at least two balls having the same color is
$$\sum_{k=0}^n{x\choose k}\frac{k\cdot k!}{x^{k+1}}$$
Which is the LHS,
So we can conclude that
$$
\sum_{k=0}^n{x\choose k}\frac{k\cdot k!}{x^{k+1}}
= 1 - {x\choose n+1}\frac{(n+1)!}{x^{n+1}}
$$
