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

Question

Básicamente, yo tenía un poco de diversión haciendo esto:

0
    1
1       6
    7       6
8       12
    19      6
27      18
    37      6
64      24
    61
125

etc.

comenzando con $k^n$ ($n=3$) y, a continuación, el cálculo de las diferencias. Resulta que el resultado después de n pasos es siempre $n!$. Bastante limpio, je? :)

Por lo tanto:

$$ n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $$ donde $n \in \mathbb{N}$ $r \in \mathbb{Z}$

Pero, ¿cómo puedo demostrar que?

Answer 1

Deje $\mathbf E$ ser el operador de desplazamiento en funciones en $\Bbb R$ o $\Bbb Z$: $(\mathbf{E}f)(x)=f(x+1)$. Deje $\mathbf\Delta$ ser el delantero operador diferencia: $(\mathbf{\Delta} f)(x)=f(x+1)-f(x)$. Deje $\mathbf 1$ ser la identidad del operador: $\mathbf{1}f=f$. A continuación,$\mathbf{\Delta}=\mathbf{E}-\mathbf{1}$, lo $$\mathbf{\Delta}^n=(\mathbf{E}-\mathbf{1})^n=\sum_{k=0}^n(-1)^k\binom{n}k\mathbf{E}^{n-k}\;,$$ y por lo tanto

$$\begin{align*} \mathbf{\Delta}^nf(r)&=\sum_{k=0}^n(-1)^k\binom{n}k\mathbf{E}^{n-k}f(r)\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}kf(r+n-k)\;. \end{align*}$$

En particular, si $f(x)=x^n$, tenemos

$$\mathbf{\Delta}^nf(r)=\sum_{k=0}^n(-1)^{n-k}\binom{n}k(r+n-k)^n\;.\tag{1}$$

Ahora me reclama que $\mathbf{\Delta}^nf$ es la función constante con valor de $n!$. Esto es fácil de demostrar por inducción. Supongamos que es cierto para todos los exponentes de menos de $n$, y tenga en cuenta que si $f$ es una función constante, entonces $\mathbf{\Delta}^kf$ es idéntica $0$ todos los $k\ge 1$. Entonces

$$\mathbf{\Delta}x^n=(x+1)^n-x^n=\sum_{k=0}^{n-1}\binom{n}kx^k$$ por el teorema del binomio, por lo que

$$\begin{align*} \mathbf{\Delta}^nx^n&=\sum_{k=0}^{n-1}\binom{n}k\mathbf{\Delta}^{n-1}x^k\\ &=\binom{n}{n-1}(n-1)!\\\\ &=n(n-1)!\\\\ &=n!\;, \end{align*}$$

y la inducción es completa. La combinación de este con $(1)$ se obtiene el resultado deseado.

Answer 2

Supongamos $f(x)=a_0 x^n+a_1x^{n-1}+\ldots+a_n$ ser un polinomio de grado $n$. Es sencillo comprobar que $f(x+1)-f(x)$ es un polinomio en a $x$ grado $n-1$, con un coeficiente inicial $n a_0$. Tomando $f(x)=x^n$, repitiendo este proceso $n$ a veces, tenemos que $$ \sum_{k=0}^n (-1)^k {n\elegir k}(x+n-k)^n $$ es un polinomio en a $x$ de grado 0, con los principales coeficiente de $n!$.

Answer 3

Deje $D = \partial/\partial x$. Entonces $$\begin{eqnarray*} \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} &=& \sum_{k=0}^{n}(-1)^{n-k} \binom{n}{k}(k+r)^{n} \\ &=& \left.\left(x D\right)^n \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} x^{k+r}\right|_{x=1} \\ &=& \left.\left(x D\right)^n x^r(x-1)^n \right|_{x=1} \\ &=& \left.D^n (x-1)^n\right|_{x=1} \\ &=& n! \end{eqnarray*}$$

Observe que en la evaluación de $\left.\left(x D\right)^n x^r(x-1)^n \right|_{x=1}$, todas las contribuciones de la forma $x^m D^m x^r(x-1)^n$ $m<n$ se desvanecen. Para más información sobre el operador $(x D)^n$, ver a esta pregunta.

Answer 4

Ya que la pregunta es con la etiqueta "combinatoria" aquí está una combinatoria de la prueba. :)

Deje $A_k$ ser el conjunto de todas las funciones de $f: \{1, 2, \ldots, n\} \mapsto \{1, 2, \ldots, n+r\}$ tal que $f(i) = k$ durante al menos un $i$ donde $1 \leq k \leq n$. La identidad se cuenta el número de funciones en $\cap_{k=1}^n A_k$ en dos formas diferentes.

Primera forma: El conjunto de $\cap_{k=1}^n A_k$ es el conjunto de en funciones de $\{1, 2, \ldots, n\}$ a sí mismo. Desde una en función de un conjunto finito a sí mismo debe ser uno-a-uno así, la intersección de la $A_k$'s es el conjunto de bijections en $\{1, 2, \ldots, n\}$. Hay $n$ opciones para $f(1)$, seguido por $n-1$ opciones para $f(2)$$f(1)$, y así sucesivamente. Por lo tanto: $$\text{There are $n!$ functions in } \bigcap_{k=1}^n A_k.$$

Segunda forma: Ahora queremos usar el principio de inclusión-exclusión. Las funciones en la intersección de las $\bar{A}_{i_1}, \bar{A}_{i_2}, \ldots, \bar{A}_{i_k}$ son los que mapa de$\{1, 2, \ldots, n\}$$\{1, 2, \ldots, n+r\} - \{i_1, i_2, \ldots i_k\}$. Hay $n-k+r$ elementos en este último conjunto, y por tanto, hay $(n-k+r)^n$ funciones $\cap_{j=1}^k \bar{A}_{i_j}$. Además, hay $n^n$ total funciones de $\{1, 2, \ldots, n\}$ a sí mismo. Por la inclusión, la exclusión, entonces, también tenemos los siguientes: $$\text{There are } \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+r)^n \text{ functions in } \bigcap_{k=1}^n A_k.$$