Cómo demostrar que $\sum\limits_{i=0}^p (-1)^{p-i} {p \choose i} i^j$ es $0$ para $j < p$ y $p!$ para $j = p$

Question

Dejemos que $p \in \mathbf{N}$ . No sé cómo demostrarlo $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^j=0 \textrm{ for } j \in \{0,\ldots,p-1\},$$ y $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^p=p!$$

(Tal vez utilizando la siguiente pista, pero no necesariamente. Consideremos el sistema de ecuaciones de Cramer (donde $0^0:=1$ ): $$0^j x_0+1^j x_1+\ldots + p^j x_p=p! \delta_{j,p}$$

( $j=0, \ldots,p$ ). La solución viene dada probablemente por $x_i=(-1)^{p-i} {p \choose i}$ para $i=0,\ldots, p$ .)

Gracias.

Answer 1

Utilice funciones generadoras .

Llame a $s_{j,p}$ el $j$ y considere la función generadora exponencial $S_p$ de la secuencia $(s_{j,p})_{j\geqslant0}$ definido como $$ S_p(x)=\sum\limits_{j=0}^{+\infty}s_{j,p}\frac{x^j}{j!}=\sum\limits_{i=0}^p(-1)^{p-i}{p\choose i}\sum\limits_{j=0}^{+\infty}i^j\frac{x^j}{j!}=\sum\limits_{i=0}^p(-1)^{p-i}{p\choose i}\mathrm e^{ix}. $$ Por el teorema del binomio la última suma es $$ \sum\limits_{i=0}^p{p\choose i}a^ib^{p-i}=(a+b)^p, $$ para $a=\mathrm e^x$ y $b=-1$ Por lo tanto $$ S_p(x)=(\mathrm e^x-1)^p. $$ La expansión en serie de $\mathrm e^x-1$ no tiene $x^0$ término por lo que la valoración de $S_p(x)$ es al menos $p$ . Esto demuestra que $s_{j,p}=0$ por cada $0\leqslant j\leqslant p-1$ .

Además $\mathrm e^x-1=x+o(x)$ de ahí que el $x^p$ término en $S_p(x)$ es exactamente $1$ y $s_{p,p}=p!$ .

Este método proporciona $s_{p+j,p}$ por cada positivo $j$ también, por ejemplo, $$ \frac{s_{p+1,p}}{(p+1)!}=\frac{p}2,\qquad \frac{s_{p+2,p}}{(p+2)!}=\frac{p(3p+1)}{24}, $$ y, de forma más general, para todo lo no negativo $j$ la relación $\dfrac{s_{p+j,p}}{(p+j)!}$ es un polinomio en $p$ de grado $j$ y con coeficientes racionales.

Nota: Para calcular $S_p(x)$ También se puede observar que la suma al final de nuestra primera ecuación mostrada es un múltiplo de la expectativa de la suma $X_p=Y_1+\cdots+Y_p$ de $p$ i.i.d. Variables aleatorias de Bernoulli $Y_k$ con la expectativa $x$ Por lo tanto $$ S_p(x)=2^p(-1)^p\mathrm E((-1)^{X_p}\mathrm e^{xX_p}). $$ Por independencia la expectativa es un producto de $\mathrm E((-1)^{Y_k}\mathrm e^{xY_k})=\frac12(1-\mathrm e^x)$ Por lo tanto $$ S_p(x)=(-1)^p(1-\mathrm e^x)^p=(\mathrm e^x-1)^p. $$

Answer 2

Otra solución podría ser la siguiente:

Es un recuento doble de las funciones suryentes del conjunto $\{1,\dots,j\}$ al conjunto $\{1,\dots, p\}$ .

Por un lado, es evidente que estas funciones son $p!$ si $j=p$ mientras que no existen tales funciones si $j<p$ .

Vamos a contar estas funciones de una manera diferente:

Para $1\leq i\leq p$ definamos los conjuntos $$A_i:=\{\text{the functions from }\{1,\dots,j\}\text{ to }\{1,\dots,p\}\text{ which doesn't contain }\; i\;\text{ in their image}\}.$$

Tenemos entonces

$$\begin{align} |A_i|&=(p-1)^j\\ |A_i\cap A_l|&=(p-2)^j\\ &\vdots&\\ \left|\bigcap_{i=1}^p A_i\right|&=0.\end{align}$$

Estamos interesados en calcular lo siguiente: $$|\overline{A_1}\cap\overline{A_2}\cap\dots\cap\overline{A_p}|=|\overline{A_1\cup A_2 \cup\dots\cup A_p}|= p^j-|A_1\cup A_2 \cup\dots\cup A_p|= $$ $$p^j-\sum_{i=1}^p\left((-1)^{i+1}\sum_{1\leq j_1<\dots<j_i\leq p}\left|\bigcap_{k=1}^i A_{j_k}\right|\right)=\sum_{k=0}^p(-1)^{p+k}\binom{p}{k}k^j.$$ De lo cual se desprende la tesis.

EDITAR Dado que hace un año dediqué mucho tiempo a este problema, me gustaría dar otros dos centavos sobre el tema, y daría otra solución, o al menos un esbozo de ella:

Entonces, consideremos el operador diferencial que realiza: $$D(f(x)) = \frac{\mathrm d}{\mathrm dx}(x\cdot f(x)) = f(x) + x\cdot\frac{\mathrm df}{\mathrm dx}.$$ Inmediatamente se ve que $$D(x^m)=m\cdot x^m,$$ por lo que $$\sum_{k=0}^{p}(-1)^k \binom{p}{k}\,k^j = \left.D^j\left((1-x)^p\right)\right|_{x=1}.$$ Así que, (casi) inmediatamente, de nuevo sigue la tesis.

---

Permítanme decir una última cosa. Esta fórmula está estrictamente relacionada con Números Stirling del segundo tipo pero fíjate que la segunda prueba que te di no dice mucho sobre lo que pasa si $j>p$ , mientras que el primero encaja perfectamente incluso en esta situación.

Answer 3

Dejemos que $\Sigma$ sea un alfabeto de $p$ diferentes letras. Afirmo que $$\sum\limits_{i=0}^p (-1)^{p-i} \binom{p}{i} i^j$$ cuenta el número de palabras sobre $\Sigma$ de longitud $j$ que utilizan todos los $p$ de las letras al menos una vez cada una. Esto es sólo el principio de inclusión-exclusión . Para cada $i$ de $0$ a través de $p$ hay $\binom{p}{i}i^j$ formas de elegir un subconjunto de $i$ letras y formar un $j$ -palabra de letras utilizando sólo letras de ese subconjunto, pero no todas estas formas utilizan todas $i$ de las letras del subconjunto. Así, $$\binom{p}{p}p^j = p^j$$ es sólo una primera aproximación. De ello restamos las palabras que utilizan sólo $p-1$ de las letras para obtener una segunda aproximación, $$\binom{p}{p}p^j - \binom{p}{p-1}(p-1)^j.$$ Por supuesto, cada palabra a la que le faltan al menos dos letras ha sido sustraída con demasiada frecuencia, así que tenemos que volver a añadirlas para obtener una tercera aproximación, $$\binom{p}{p}p^j - \binom{p}{p-1}(p-1)^j + \binom{p}{p-2}(p-2)^j.$$ El resultado final después de realizar todas las correcciones es la suma original, $$\sum\limits_{i=0}^p (-1)^{p-i} \binom{p}{i} i^j.$$

Su resultado es una consecuencia inmediata: si $j \in \{0,1,\dots,p-1\}$ Por supuesto, hay no palabras de longitud $j$ que utilizan todos los $p$ letras, y si $j=p$ , las palabras que utilizan todos $p$ las letras son precisamente las $p!$ permutaciones de $\Sigma$ .

Answer 4

Una comparación con la definición del $p$ -diferencia hacia adelante muestra que

$$\sum_{j=0}^p (-1)^{p-j} \binom{p}{j} j^k=\left.\Delta^p x^k\right\vert_{x=0}$$

Ahora, $x^k$ puede ampliarse como una serie de factoriales descendentes :

$$x^k=\sum_{j=0}^k \left\{k \atop j\right\} x^{(j)}$$

donde $\left\{n \atop j\right\}$ es un Número de subconjunto de Stirling . Así,

$$\Delta^p x^k=\sum_{j=0}^k \left\{k \atop j\right\}\Delta^p x^{(j)}$$

donde utilizamos la linealidad del operador de diferencia hacia adelante. Desde

$$\Delta^p x^{(k)}=\left(\prod_{j=0}^{p-1} (k-j)\right)x^{(k-p)}$$

y el producto se hace cero si $k < p$ , $\Delta^p x^{(k)}=0$ si $k < p$ . Del mismo modo, si $k=p$ el producto anterior es igual a $p!$ y también tenemos la propiedad $x^{(0)}=1$ Así que.., $\Delta^p x^{(p)}=p!$ . Sustituyendo estos en la expansión de $x^k$ en términos de $x^{(j)}$ y observando que $\left\{k \atop k\right\}=1$ La reclamación está probada.

Answer 5

Tenga en cuenta que $\displaystyle\binom{p}{i}\binom{i}{k}=\binom{p}{k}\binom{p-k}{i-k}$ Por lo tanto, $$ \begin{align} \sum_i(-1)^i\binom{p}{i}\binom{i}{k} &=\sum_i(-1)^i\binom{p}{k}\binom{p-k}{i-k}\\ &=\binom{p}{k}(1-1)^{p-k}\\ &=\binom{p}{k}0^{p-k}\tag{1} \end{align} $$ Que es $1$ cuando $k=p$ y $0$ cuando $k<p$ . Así, $\displaystyle T_pf=\sum_i(-1)^i\binom{p}{i}f(i)$ acaba con todos los polinomios combinatorios de grado inferior a $p$ .

$\displaystyle k!\binom{i}{k}$ es un grado $k$ polinomio en $i$ con coeficiente de plomo $1$ . Así, podemos escribir $$ i^j=j!\binom{i}{j}+\sum_{k=0}^{j-1}a_{jk} k!\binom{i}{k}\tag{2} $$ para algunos enteros $a_{jk}$ . Por lo tanto, reunir $(1)$ y $(2)$ , $$ \begin{align} \sum_i(-1)^i\binom{p}{i}i^j &=\sum_i(-1)^i\binom{p}{i}\left(j!\binom{i}{j}+\sum_{k=0}^{j-1}a_k k!\binom{i}{k}\right)\\ &=j!\binom{p}{j}0^{p-j}+\sum_{k=0}^{j-1}a_kk!\binom{p}{k}0^{p-k}\\ &=\left\{\begin{array}{rl}0&\text{if }j<p\\p!&\text{if }j=p\end{array}\right.\tag{3} \end{align} $$