Discrete Calculus -- Summing $\sum _{k=1}^{n+1} \frac{k}{(n+1)^k (-k+n+1)!}$

Question

$$\sum _{k=1}^{n+1} \frac{k}{(n+1)^k (-k+n+1)!}$$

Mathematica gives that the answer is quite surprisingly the reciprocal of $n!$.

The first way I thought of trying to prove this was by induction, but I couldn't find a way to easily prove the case for $n+2$ assuming $n+1$ was true.

A second way I thought of was using the discrete analog of the FTIC. However, while $k$ and $(n+1)^k$ are readily integrable using this version, $(n-k+1)!$ is a bit trickier, and I am not sure how to convert this to something that can be applied to the discrete FTIC.

Could generating functions possibly be used?

Answer 1

Note that

$$\sum _{k=1}^{n+1} \frac{k}{(n+1)^k (-k+n+1)!}=\sum_{k=0}^n\frac{k+1}{(n+1)^{k+1}(n-k)!}=\frac1{n!}\sum_{k=0}^n\binom{n}k\frac{(k+1)!}{(n+1)^{k+1}}\;,$$

so the problem reduces to simplifying

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

I’ll concentrate on that last summation.

$$\begin{align*} \sum_{k=0}^n\binom{n}k(k+1)!(n+1)^{n-k}&=\sum_{k=0}^n\frac{n!}{k!}(n+1-k)(n+1)^k\\ &=(n+1)\sum_{k=0}^n\frac{n!}{k!}(n+1)^k-\sum_{k=0}^n\frac{n!}{k!}k(n+1)^k\\ &=(n+1)\sum_{k=0}^n\frac{n!}{k!}(n+1)^k-\sum_{k=1}^n\frac{n!}{(k-1)!}(n+1)^k\\ &=(n+1)\left(\sum_{k=0}^n\frac{n!}{k!}(n+1)^k-\sum_{k=0}^{n-1}\frac{n!}{k!}(n+1)^k\right)\\ &=(n+1)\cdot\frac{n!}{n!}(n+1)^n\\ &=(n+1)^{n+1}\;, \end{align*}$$

so the expressions in $(1)$ are equal to $1$, and the original summation is indeed $\dfrac1{n!}$.

Answer 2

Substituting $k$ by $n - k + 1$ in the following, we have $$\sum_{k=1}^{n+1} {k\over (n+1)^k(n-k+1)!} = \sum_{k=0}^{n} {n+1-k\over (n+1)^{n+1-k}k!} = {1\over {(n+1)}^{n+1}}\sum_{k=0}^{n} {(n+1-k)(n+1)^k\over k!}$$ = $${1\over (n+1)^{n+1}} \left( \sum_{k=0}^n {(n+1)^{k+1}\over k!} - \sum_{k=1}^n {(n+1)^k\over (k-1)!} \right)$$ Write $\sum_{k=0}^n {(n+1)^{k+1}\over k!}$ = $\sum_{k=1}^{n+1} {(n+1)^k\over (k-1)!}$, you will get in the above equation $${1\over (n+1)^{n+1}} \left( \sum_{k=0}^n {(n+1)^{k+1}\over k!} - \sum_{k=1}^n {(n+1)^k\over (k-1)!} \right) = {1\over (n+1)^{n+1}} \left( \sum_{k=1}^{n+1} {(n+1)^k\over (k-1)!} - \sum_{k=1}^n {(n+1)^k\over (k-1)!} \right) = {1\over (n+1)^{n+1}} {(n+1)^{n+1}\over n!} = {1\over n!}$$