Cómo calcular $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$

Question

Al intentar responder esta pregunta Llegué a $$\int^\infty_0\frac{\sin(nx)\sin^n{x}}{x^{n+1}}dx=\frac{\pi}{2}\frac{(-1)^n}{n!}\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$$ Después de utilizar Wolfram Alpha para evaluar la suma para varios valores de $n$ parece que $$\sum^n_{k=0}(-1)^k\binom{n}{k}k^n\stackrel?=(-1)^nn!$$ Lo mejor que puedo hacer es expresar la suma como $$\left(x\frac{d}{dx}\right)^n(1-x)^n\Bigg{|}_{x=1}$$ pero hasta ahí puedo llegar. ¿Puedo saber cómo se puede calcular la suma? Gracias.

Answer 1

Puedes derivar el resultado utilizando la suma que obtengas.

Sea $x = e^\theta$ tenemos

$$ \left.\left(x\frac{d}{dx}\right)^n(1-x)^n\right|_{x=1} = \left.\frac{d^n}{d\theta^n}\left(1-e^\theta\right)^n\right|_{\theta=0} = (-1)^n \left.\frac{d^n}{d\theta^n}\left[\theta^n\left(\frac{e^\theta-1}{\theta}\right)^n\right]\right|_{\theta=0} $$ Recordemos la Regla general de Leibniz para la $n^{th}$ derivada de un producto de dos funciones:

$$(fg)^{(n)} = \sum_{k=0}^n \binom{n}{k} f^{(k)} g^{(n-k)}$$ Si un sustituto $$f = \theta^n \quad\text{ and }\quad g = \begin{cases} \left(\frac{e^\theta-1}{\theta}\right)^n,&\theta \ne 0\\ 1, & \theta = 0 \end{cases} $$ y aviso

• $f^{(m)}(0) = 0$ para $m = 0, 1, \ldots, n-1$ ,
• $g(\theta)$ es una función suave sobre una vecindad de $\theta = 0$ .

Según la regla general de Leibniz, sólo el $k = n$ plazo sobrevivir y

$$\text{RHS} = (-1)^n \binom{n}{n} \left.\left( \frac{d^n}{d\theta^n}\theta^n \right)\right|_{\theta=0} g(0) = (-1)^n n! $$

Answer 2

Supongamos que quiero contar las permutaciones del conjunto $[n]=\{1,\ldots,n\}$ . Para cada $k\in[n]$ deje $A_k$ sea el conjunto de funciones de $[n]$ a $[n]\setminus\{k\}$ . Una función de $[n]$ a $[n]$ es una permutación si no está en $A_1\cup\ldots\cup A_n$ por lo que hay $n^n-|A_1\cup\ldots\cup A_n|$ permutaciones. Por una norma argumento de inclusión-exclusión

$$\begin{align*} |A_1\cup\ldots\cup A_n|&=\sum_{1\le k\le n}|A_k|\\ &\quad-\sum_{1\le k<\ell\le n}|A_k\cap A_\ell|\\ &\quad+\sum_{1\le j<k<\ell\le n}|A_j\cap A_k\cap A_\ell|\\ &\quad\;\vdots\\ &\quad+(-1)^{n+1}|A_1\cap\ldots\cap A_n|\;. \end{align*}\tag{1}$$

Sea $K\subseteq[n]$ y que $k=|K|$ . Entonces

$$\left|\bigcap_{i\in K}A_i\right|=(n-k)^n\;,$$

porque $\bigcap_{i\in K}A_i$ es el conjunto de funciones de $[n]$ a $[n]$ cuyos rangos son disjuntos de $K$ . Existen $\binom{n}k$ tales conjuntos $K$ Así que $(1)$ se puede reescribir

$$\begin{align*} |A_1\cup\ldots\cup A_n|&=\binom{n}1(n-1)^n\\ &\quad-\binom{n}2(n-2)^n\\ &\quad+\binom{n}3(n-3)^n\\ &\quad\;\vdots\\ &\quad+(-1)^{n+1}\binom{n}n(n-n)^n\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^n\;. \end{align*}$$

Por supuesto, sabemos que el número de permutaciones de $[n]$ es $n!$ Así que

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

y multiplicación por $(-1)^n$ da el resultado deseado.

Answer 3

Otro enfoque consiste en reconocer $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$ como resultado de tomar la secuencia $(i^n)_{i\in\Bbb N}$ de $n$ -th poderes, aplicando $n$ veces $-\Delta$ donde $\Delta$ es el operador de diferencia $(a_i)_{i\in\Bbb N}\mapsto(a_{i+1}-a_i)_{i\in\Bbb N}$ y tomando el término inicial en $i=0$ . Para el operador diferencia aplicado a secuencias polinómicas es conveniente utilizar la base de las llamadas potencias factoriales decrecientes definidas por $$ x^{\underline k} = x(x-1)\ldots(x-k+1) $$ que satisfagan $\Delta\bigl((i^{\underline k})_{i\in\Bbb N}\bigr)=k(i^{\underline{ k-1}})_{i\in\Bbb N}$ para $k>0$ y $\Delta\bigl((i^{\underline 0})_{i\in\Bbb N}\bigr)=\Delta\bigl((1)_{i\in\Bbb N}\bigr)=0$ . Desde $x^{\underline k}$ es un polinomio mónico de grado $k$ en $x$ es evidente que la expresión de la secuencia $(i^n)_{i\in\Bbb N}$ como combinación lineal de secuencias factoriales decrecientes de potencia $(i^{\underline k})_{i\in\Bbb N}$ para $k=0,1,\ldots,n$ implicará la secuencia final $(i^{\underline n})_{i\in\Bbb N}$ con coeficiente $~1$ . Todos los demás términos son asesinados por $\Delta^n$ Así que $\Delta^n\bigl((i^n)_{i\in\Bbb N}\bigr)=\Delta^n\bigl((i^{\underline n})_{i\in\Bbb N}\bigr)$ que por las relaciones anteriores es la secuencia constante $(n!i^{\underline 0})_{i\in\Bbb N}=(n!)_{i\in\Bbb N}$ . De ello se deduce que $$ \sum^n_{k=0}(-1)^k\binom{n}{k}k^n = (-\Delta)^n\bigl((i^n)_{i\in\Bbb N}\bigr)\Bigm|_{i=0} =(-1)^n n!. $$

Answer 4

Utilizar el principio de inclusión-exclusión. En efecto, sea $F$ sea el conjunto de todas las funciones de $\{1,2,...,n\}$ en $\{1,2,...,n\}$ . Y que $A_{k}$ sea el conjunto de todos los $f \in F$ tal que $k \notin \text{image}(f)$

Answer 5

La suma es igual a $(-1)^nn!$ y he aquí una posible derivación. En la expresión (final) que obtuviste en la pregunta, puedes sustituir $y=x-1$ y observe que para cualquier función $f$ uno tiene $\def\d{\mathrm d}\frac\d{\d x}f(x-1)=f'(x-1)$ que es el resultado de fijar $y=x-1$ en $\frac\d{\d y}f(y)$ entonces necesita encontrar $$ c_n=\left.\left((y+1)\circ\frac\d{\d y}\right)^n((-y)^n)\right|_{y=0}. $$ El operador $E=(y+1)\circ\frac\d{\d y}$ satisface $E(y^k)=ky^k+ky^{k-1}$ a partir de la cual se demuestra fácilmente por inducción que $E^m(y^k)|_{y=0}=0$ siempre que $k>m$ . Ahora se calcula $$ c_n = E^n\bigl((-y)^n\bigr)|_{y=0} = E^{n-1}\Bigl(n(-y)^n)-n(-y)^{n-1}\Bigr)|_{y=0} = -nE^{n-1}\bigl((-y)^{n-1}\bigr)|_{y=0}=-nc_{n-1} $$ de la que $c_n=(-1)^nn!$ se deduce por inducción.