Demostrar $\sum_{k=0}^{n}\frac{n!}{k!}(n-k)n^k=n^{n+1}$ cualquier $n\in\mathbb N$.

Question

Quiero probar lo siguiente:

$$\sum_{k=0}^{n}\frac{n!}{k!}(n-k)n^k=n^{n+1}\quad\text{for any $n\in\mathbb N$.}$$ traté de inducción e invocando el teorema del binomio, con poco éxito. Estoy buscando algo rápido y sucio de la solución. Gracias por las sugerencias.

---

Como las respuestas a continuación revelan, la siguiente actualización que me había agregado anteriormente no es realmente de mucho uso, así que me golpeó.

Actualización: Después de algunos cambios, el lado izquierdo de la anterior puede ser reescrito como $$\requieren{encerrar} \encerrar{horizontalstrike}{n\sum_{k=0}^{n-1}\binom{n-1}{k}n^k(n-k)!}$$ De esta forma parece sugerir la necesidad de recurrir al teorema del binomio.

Answer 1

Es una manera de reescribir la L. H. S. como una telescópica suma: $\displaystyle\sum_{k=0}^{n}\left(\frac{n!~n^{k+1}}{k!}-\frac{n!~n^k}{(k-1)!}\right)$.

Answer 2

Supongamos que buscamos para evaluar

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

Introducir

$$n^{k-n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^k}{z^{n+1}} \frac{1}{1-z/n} \; dz.$$

Observar que esta integral proporciona una Iverson soporte, como se desvanece al $k\gt n.$ por lo Tanto podemos extender $k$ hasta el infinito.

Llegamos por la suma

$$n! n^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z/n} \sum_{k\ge 0} \frac{n-k}{k!} z^k \; dz \\ = n! n^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z/n} \left(n \exp(z) - z \sum_{k\ge 1} \frac{1}{(k-1)!} z^{k-1}\right) \; dz \\ = n! n^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{n}{n-z} \left(n \exp(z) - z \exp(z)\right) \; dz \\ = n! n^{n+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z) \; dz = n! n^{n+1} \frac{1}{n!} = n^{n+1}.$$

Esto concluye el argumento.

Answer 3

Puede mostrar a $$\sum_{k=0}^m\frac{n!}{k!}(n-k)n^k=\frac{n!}{m!}n^{m+1}$$

Answer 4

He aquí un argumento combinatorio.

Claramente $n^{n+1}$ es el número de funciones de$\{0,1,\ldots,n\}$$[n]$. Si $f$ es cualquier función, vamos a

$$k_f=\min\left\{k\in[n]:\exists\ell<k\big(f(k)=f(\ell)\big)\right\}\;.$$

Para un determinado$k\in[n]$, ¿cuántas de estas funciones tienen $k_f=k$?

• Hay $n^{\underline k}=n(n-1)\ldots(n-k+1)$ formas de elegir los $k$ valores distintos de $f(0),\ldots,f(k-1)$.
• Hay, a continuación, $k$ formas de elegir uno de estos valores para $f(k)$.
• Y por último hay $n^{n-k}$ formas de elegir los valores de $f(i)$$k<i\le n$.

Recapitulación sobre los posibles valores de $k$ a continuación, se obtiene el resultado:

$$\begin{align*} n^{n+1}&=\sum_{k=1}^nkn^{\underline k}n^{n-k}\\ &=\sum_{k=0}^nkn^{\underline k}n^{n-k}\\ &=\sum_{k=0}^n(n-k)n^{\underline{n-k}}n^k\\ &=\sum_{k=0}^n\frac{n!}{k!}(n-k)n^k\;. \end{align*}$$