¿Cómo probar $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?

Question

¿Cómo probar la siguiente identidad directamente?

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

Pensé acerca del uso del teorema del binomio para $(x+a)^n$, pero se quedó atascado, porque me di cuenta que mi $x$ y $a$ en este caso son las variables dinámicas. ¿Cualquier sugerencias? No me da la respuesta; Quiero pensar en esto por mi cuenta, pero un empujón en la dirección correcta sería increíble. ¡ Gracias!

Answer 1

1. Esta identidad es conocida como "Identidad de Abel". Puede ser probada por generalización:

$$\sum_{k} \binom{n}{k} (k+s-n)^{k} (r+n-k)^{n-k-1} = \frac{(r+s)^n}{r}$ $ (Enchufando $s=n-1,r=1$ obtenemos la identidad original.) Mejor forma de escribirlo es: $$\sum_{k} \binom{n}{k} (s-k)^{n-k} (r+k)^{k-1} = \frac{(r+s)^n}{r}$ $ a veces se agrega un parámetro adicional: %#% $ de #% esta identidad generalizada es mucho más fácil de probar.

1. Una pista más: para probar la identidad generalizada, uno puede expandir $$\sum_{k} \binom{n}{k} (s-tk)^{n-k} (r+tk)^{k-1} = \frac{(r+s)^n}{r}$ por el teorema del binomio y cambiar orden de adición.

Answer 2

No me des la respuesta que yo realmente quiero pensar que a través de esto por mi cuenta, pero un empujón en la dirección correcta sería impresionante.

Como usted desea; es tu pregunta, después de todo.

Existen los siguientes exponencial en la generación de funciones:

$$\begin{align*} \frac{-z}{W(-z)(1+W(-z))}&=\sum_{k=0}^\infty\frac{(k-1)^k}{k!}z^k\\ \frac{-W(-z)}{z}&=\sum_{k=0}^\infty\frac{(k+1)^{k-1}}{k!}z^k \end{align*}$$

donde $W(z)$ es la función de Lambert. (A veces, estos EGFs se expresa en términos de "el árbol de la función" $T(z)=-W(-z)$.) La serie de Maclaurin para $-W(-z)$ tiene este aspecto:

$$-W(-z)=\sum_{k=1}^\infty \frac{k^{k-1}}{k!} z^k$$

que tendrá que demostrar, tal vez por componer dos de la serie.

Ahora, el OP de la identidad puede ser reestructurada como una convolución:

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

El cambio a la generación de la función de la vista, la convolución de la izquierda tiene la función de la generación de

$$\left(\frac{-z}{W(-z)(1+W(-z))}\right)\left(\frac{-W(-z)}{z}\right)=\frac1{1+W(-z)}$$

lo que significa que

$$\frac1{1+W(-z)}=1+\sum_{k=1}^\infty\frac{k^k}{k!}z^k$$

Ahora a probar la validez de esta identidad, se puede iniciar mediante la derivación de la fórmula (y el correspondiente de la serie) por la derivada de la función de Lambert. Recordar la relación fundamental $W(z)\exp(W(z))=z$; el uso implícito de diferenciación para derivar una expresión $W^\prime(z)$ que luego pueden ser manipulados para parecerse a $\dfrac1{1+W(-z)}$. De nuevo, los detalles están a la izquierda.

Answer 3

Una prueba agradable utiliza la fórmula de inversión de Lagrange-Bürman. Empezar a definir:\begin{equation} C(z) = z e^{C(z)} \end{equation} que da la extensión:\begin{equation} e^{\alpha C(z)} = \alpha \sum_{n \ge 0} \frac{(\alpha + n)^{n - 1} z^n}{n!} \end{equation} entonces tienes:\begin{equation} e^{(\alpha + \beta) C(z)} = e^{\alpha C(z)} \cdot e^{\beta C(z)} \end{equation} expandiendo y comparando ambos lados da el teorema del binomio de Abel:\begin{equation} (\alpha + \beta) (\alpha + \beta + n)^{n - 1} = \sum_{0 \le k \le n} \binom{n}{k} (\alpha + k)^{k - 1} (\beta + n - k)^{n - k - 1} \end{equation}

Answer 4

Como una observación adicional me gustaría señalar que la expansión de la serie de $$e^{\alpha T(z)}$$ where $$T(z) = z \times e^{T(z)}$$ también puede ser calculada con la de Cauchy Teorema de los Residuos, lo que da una variante de Lagrange de la Inversión.

Buscamos para calcular $$[z^n] e^{\alpha T(z)} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} e^{\alpha T(z)} \; dz.$$

Poner $w=T(z)$ en el funcional de la ecuación de $T(z)$ para obtener $a$z = w e^{w} \quad \text{y} \quad dz = e^{w} - w e^{w} = (1-w) e^{w}.$$

Sustituir en la integral para obtener $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{e^{w(n+1)}}{w^{n+1}} e^{\alpha w} e^{w} (1-w) \; ps.$$ Este es $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{e^{w(n+\alpha)}}{w^{n+1}} (1-w) \; ps.$$ Ahora podemos leer en el residuo de a $w=0$ para obtener $$\frac{(n+\alpha)^n}{n!} - \frac{(n+\alpha)^{n-1}}{(n-1)!} = (n+\alpha) \frac{(n+\alpha)^{n-1}}{n!} - n \frac{(n+\alpha)^{n-1}}{n!} = \alpha \frac{(n+\alpha)^{n-1}}{n!}$$ citado en la respuesta por @vonbrand arriba.

Answer 5

¿Has probado la inducción? Primero consideremos el caso base $n=0$. A continuación, mostrar que si lleva a cabo para $n$ entonces esto implica que tiene $n+1$. Otra forma podría ser que escriba $n = (n-k+1)+(k+1)$ y luego hacer la expansión de $n^n$, es decir va al revés.