Demostrar que $\sum_{x=0}^{n}(-1)^x\binom{n}{n-x} (n+1-x)^n=n!$

Question

Averiguar estas cosa al "jugar" con los números:

$$3^2-2.2^2+1^2=2=2!$$

$$4^3-3.3^3+3.2^3-1^3=6=3!$$

$$5^4-4.4^4+6.3^4-4.2^4+1^4=24=4!$$

Así que voy a la conjetura de que:

$$\binom{n}{n}(n+1)^n-\binom{n}{n-1}n^n+\binom{n}{n-2}(n-1)^n-...=n!$$

o

$$\sum_{x=0}^{n}(-1)^x\binom{n}{n-x} (n+1-x)^n=n!$$

Ahora, ¿cómo puedo demostrar esta conjetura? Lo he intentado mucho, pero todavía no podía tener ninguna idea.

Answer 1

Podemos probar el caso $n=1$:

\begin{align}\sum_{x=0}^1(−1)^x{1\choose 1−x}(1+1−x)^1&=(−1)^0{1\choose 1−0}(1+1−0)^1+ (−1)^1{1\choose 1−1}(1+1−1)^1\\ &=2+(-1)\\ &=1\\ &=1!\end {Alinee el}

Ahora asumimos que tiene $n=k$, es decir % $ $$\sum_{x=0}^k(−1)^x{k\choose k-x}(k+1−x)^k=k!$

Tenemos que demostrar que tiene $n=k+1$, es decir % $ $$\sum_{x=0}^{k+1}(−1)^x{k+1\choose k+1-x}(k+2−x)^{k+1}=(k+1)!$

Tenga en cuenta % $ $$(k+1)!=k!\times (k+1)$

¿Se puede seguir desde aquí?

Answer 2

Aquí es una variante basada en la expansión de la serie de la función exponencial \begin{align*} e^t=1+t+\frac{t^2}{2!}+\frac{t^3}{3!}+\cdots \end{align*}

Utilizamos $[t^n]$ para denotar el coeficiente de $t^n$ en una serie y escribir $k$ en lugar de $x$ sólo para su comodidad.

Obtenemos \begin{align*} \sum_{k=0}^n(-1)^k\binom{n}{n-k}(n+1-k)^n&=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(k+1)^n\tag{1}\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}n![t^n]e^{(k+1)t}\tag{2}\\ &=n![t^n]e^t\sum_{k=0}^n\binom{n}{k}\left(e^{t}\right)^k(-1)^{n-k}\tag{3}\\ &=n![t^n]e^t(e^t-1)^n\tag{4}\\ &=n! \end{align*}

Comentario:

• En (1) podemos cambiar el orden de la suma por la sustitución del índice de $k\rightarrow n-k$.

• En (2) tenemos en cuenta el coeficiente de $t^n$$e^{(k+1)t}$.

• En (3) hacemos un reordenamiento para prepararse para el teorema del binomio.

• En (4) aplicamos el teorema del binomio y tenga en cuenta que $(e^t-1)^n$ comienza con $t^n$, por lo que el $[t^n]e^t(e^t-1)^n=1$.

Answer 3

Vamos a escribir su suma como $$ \bbox[lightyellow] { \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matriz{ n \cr n - k \cr} \right)\left( {n + 1 - k} \right)^{\n} } = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,n - j} \left( \matriz{ n \cr j \cr} \right)\left( {j + 1} \right)^{\n} } = n! } \etiqueta{1} $$

Considerar el Avance de Diferencia Finita de una función de $f(x)$, y sus iteraciones, que se define como $$ \bbox[lightyellow] { \eqalign{ & \Delta _{\,x} \,f(x) = f(x + 1) - f(x) \cr & \Delta _{\,x} ^{\,2} \,f(x) = \Delta _{\,x} \,\left( {\Delta _{\,x} \,f(x)} \right) = f(x + 2) - 2f(x + 1) + f(x) \cr & \quad \vdots \cr & \Delta _{\,x} ^{\,q} \,f(x)\quad \left| {\;0 \le {\rm integer}\,q} \right.\quad = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,q - k} \left( \matriz{ q \cr k \cr} \right)f(x + k)} \cr} } \etiqueta{2} $$

Si tomamos $f(x)$ a ser un polinomio de grado $d$ $$ \bbox[lightyellow] { p_{\,d} (x) = a_{\,d} \,x^{\,d} + a_{\,d - 1} \,x^{\,d - 1} + \; \cdots \; + a_{\,0} \,x^{\,0} = \sum\limits_{0\, \le \,j\, \le \,d} {a_{\,j} \,x^{\,j} } } \etiqueta{3.a} $$ y nos convierten en el Aumento de Factorial (Pochammer símbolo) por medio de los Números de Stirling, $$ \bbox[lightyellow] { p_{\,d} (x) = b_{\,d} \,x^{\,\underline d } + b_{\,d - 1} \,x^{\,\underline {d - 1} } + \; \cdots \; + b_{\,0} \,x^{\,\subrayado 0 } = \sum\limits_{0\, \le \,j\, \le \,d} {b_{\,j} \,x^{\,\underline {\,j\,} } } \quad \left| {\;b_{\,k} = \sum\limits_{0\, \le \,j\, \le \,d} {a_{\,j} \,\left\{ \matriz{ j \cr k \cr} \right\}\;} } \right. } \etiqueta{3.b} $$ entonces, gracias a la facilidad de expresión de la diferencia finita para la caída de los factoriales, no es difícil demostrar que $$ \bbox[lightyellow] { \eqalign{ & \Delta ^n p_{\,d} (x) = \sum\limits_k {\left( { - 1} \right)^{n - k} \left( \matriz{ n \cr k \cr} \right)\;p_{\,d} (x + k)} = \cr & = d!b_{\,d} \,\left( \matriz{ x \cr d - n \cr} \right) + \left( {d - 1} \right)!b_{\,d - 1} \,\left( \matriz{ x \cr d - 1 - n \cr} \right) + \; \cdots \; + 0!b_{\,0} \left( \matriz{ x \cr 0 - n \cr} \right) \cr} } \etiqueta{4} $$ que, calculado en $x=0$ le da: $$ \bbox[lightyellow] { \Delta ^n p_{\,d}(0) = \sum\limits_k {\left( { - 1} \right)^{n - k} \left( \matriz{ n \cr k \cr} \right)\;p_{\,d}(k)} = \left\{ {\matriz{ 0 & {d < n} \cr {d!b_{\,d} = d!a_{\,d} } & {n = d} \cr {n!b_ {\n} } & {n \le d} \cr } } \right. } \etiqueta{5} $$

Por lo que su caso es sólo un caso particular , con $p_{n}(x)=(1+x)^n$, de los de arriba que tiene para todos los polinomios de

Answer 4

Aquí está una combinatoria de prueba: consideremos el conjunto $F$ funciones $\{ 1, 2, \ldots, n \} \to \{ 1, 2, \ldots, n, n + 1 \}$, y para $k = 1, \ldots, n$, vamos a $S_k$ ser el conjunto de funciones que $k$ no está en el rango. Luego, por la inclusión-exclusión: $$\left|F \setminus \bigcup_{k=1}^n S_k \right| = |F| - \sum_{1 \le i \le n} |S_i| + \sum_{1 \le i < j \le n} |S_i \cap S_j| - \sum_{1 \le i < j < k \le n} |S_i \cap S_j \cap S_k| + \cdots + (-1)^n |S_1 \cap \cdots \cap S_n|.$$ Ahora, $|F| = (n+1)^n$; para cada $i$, $|S_i| = n^n$, así que el segundo término es $-\binom{n}{1} n^n$; para cada $i < j$, $|S_i \cap S_j| = (n-1)^n$, así que el tercer término es $\binom{n}{2} (n-1)^n$; y así sucesivamente. Por lo tanto, la suma en el lado derecho es igual para el lado izquierdo de la ecuación (utilizando ese $\binom{n}{n-x} = \binom{n}{x}$). Por otro lado, $F \setminus \bigcup_{k=1}^n S_k$ es exactamente el conjunto de funciones que cada uno de $1, 2, \ldots, n$ está en el rango, que es precisamente el conjunto de las permutaciones de $\{ 1, 2, \ldots, n \}$; por lo tanto, el lado izquierdo es igual a $n!$.

De hecho, si dejamos $F$ el conjunto de funciones de $\{ 1, 2, \ldots, n \} \to \{ 1, 2, \ldots, n + r \}$ en su lugar, este argumento se generaliza fácilmente a mostrar que, para $n$ un entero positivo y $r$ un entero no negativo: $$\sum_{x=0}^n (-1)^k \binom{n}{x} (n+r-x)^n = n!.$$

Answer 5

En primer lugar tenga en cuenta que $$\sum_{k=0}^{n}\dbinom{n}{n-k}\left(-1\right)^{k}\left(n-k+1\right)^{n}=\sum_{k=0}^{n}\dbinom{n}{k}\left(-1\right)^{k}\left(n-k+1\right)^{n}$$ then from the special case of the Melzak's identity: $$\sum_{k=0}^{n}\left(-1\right)^{k}\dbinom{n}{k}\frac{f\left(y-k\right)}{x+k},=\frac{f\left(x+y\right)}{x\dbinom{x+n}{n}}-n!a_{n+1}\,x,y\in\mathbb{R},\,x\neq-k$$ where $f $ is an algebraic polynomial of degree $%n+1$ and $a_{n+1}$ is the coefficient of the $n+1-$th power, we have, taking $f\left (z\right) = \left (z + 1\right) ^ {n+1} \, y = n $ $$\sum_{k=0}^{n}\dbinom{n}{k}\left(-1\right)^{k}\frac{\left(n-k+1\right)^{n+1}}{-x-k}=n!-\frac{\left(n+x+1\right)^{n+1}}{x\dbinom{x+n}{n}}$$ and so $% $ $\sum_{k=0}^{n}\dbinom{n}{k}\left(-1\right)^{k}\left(n-k+1\right)^{n}=\lim_{x\rightarrow-n-1}\left(n!-\frac{\left(n+x+1\right)^{n}}{x\dbinom{x+n}{n}}\right)={\color{red}{n!}}$como quería.