Htykuut

Mathematica says $displaystylesum_{k=1}^{n} dfrac{binom{n-1}{k-1}}{n^k} = dfrac{(n+1)^{n-1}}{n^n}$. I would like to know how to show this equality.

The left hand side is the solution to a probability problem: Select integers (with replacement) from {1,2,...,n} until the cumulative sum of your selected integers is at least n. What is the probability that your cumulative sum is exactly n? The right hand side is the ratio of labeled trees on n+1 nodes to functions from [n] into [n]. A combinatorial proof to the equations would be great. I would settle for an analytic proof.

According to the Binomial Theorem we get as a series expansion for $(n+1)^{n-1}$ the following

$$(1+n)^{n-1}=sum_{k=0}^{n-1}binom{n-1}{k}n^{n-1-k}$$

By applying the index shift $k'=k+1$ - and therefore $k=k'-1$ - we further get

$$sum_{k=0}^{n-1}binom{n-1}{k}n^{n-1-k}=sum_{k'=1}^{n}binom{n-1}{k'-1}n^{n-k'}$$

One may note that within the term $n^{n-k'}$ the $n^n$ is independed of the index. By reshaping the whole equality we get

$$begin{align}
(1+n)^{n-1}&=sum_{k'=1}^{n}binom{n-1}{k'-1}n^{n-k'}\
&=n^nsum_{k'=1}^{n}frac{binom{n-1}{k'-1}}{n^{k'}}\
Leftrightarrow frac{(1+n)^{n-1}}{n^n}&=sum_{k'=1}^{n}frac{binom{n-1}{k'-1}}{n^{k'}}
end{align}$$

which is your desired result.