Prueba con coeficiente binomial y la delta de kronecker

Question

Quiero demostrar que la $$ \sum_{k=i}^n \binom{n}{k}\binom{k}{i}(-1)^{n-k}=\delta_{n,i} $$ Donde $\delta_{n,i}$ es la Delta de Kronecker, es decir, $\delta_{n,i}=0$ si $n \neq i$ $\delta_{n,i}=1$ si $i=n$.

Tengo una intuitiva prueba con matrices que representan la transformación lineal $F(x)=(1+x)^n$ $G(x)=(1-x)^n$ y su producto. Pero prefiero una precisa la prueba, si es que existe. Gracias.

Answer 1

Por el teorema del binomio tenemos

$$\begin{align} x^n &= \bigl((x+1)-1\bigr)^n\\ &= \sum_{k=0}^n (-1)^{n-k}\binom{n}{k}(x+1)^k\\ &= \sum_{k=0}^n (-1)^{n-k}\binom{n}{k}\left(\sum_{i=0}^k \binom{k}{i}x^i\right)\\ &= \sum_{k=0}^n\sum_{i=0}^k (-1)^{n-k}\binom{n}{k}\binom{k}{i}x^i\\ &= \sum_{i=0}^n \left(\sum_{k=i}^n (-1)^{n-k}\binom{n}{k}\binom{k}{i}\right)x^i \end{align}$$

y, por supuesto,

$$x^n = \sum_{i=0}^n \delta_{n,i}x^i.$$

Answer 2

La suma es $$(-1)^n \sum_{k=i}^n (-1)^k \binom{n}{k,i,n-k-i}$$ which is equivalent to summing over all $i$-subsets $S$ of $[n]:=\{1,2,\ldots,n\}$ and $T \supseteq S$, so the formula is also given by $$(-1)^n \sum_{S \subseteq [n]:|S|=i} \underbrace{\sum_{T \subseteq [n]:S \subseteq T} (-1)^{|T|}}_{\text{call this } f(T)}.$$ Esto se ilustra a continuación:

Se observa que el $f(T)$ es igual al número de subconjuntos de tamaño de $T$ contiene $S$ menos el número de impares del tamaño de los subconjuntos de a $T$ contiene $S$. Por lo tanto $f(T)=0$, y, en consecuencia, la suma total $=0$, a menos que $i=n$, en cuyo caso $S=[n]$, y la suma se simplifica a $$(-1)^{n} (-1)^{n}=1.$$

Answer 3

Observar que cuando multiplicamos dos exponenciales funciones de generación de las secuencias de $\{a_n\}$ $\{b_n\}$ obtenemos que $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\elegir k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ es decir, el producto de las dos funciones de generación es la generación de la función de $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

En el presente caso tenemos $$ A(z) = \sum_{k\ge 0} {k\elegir j} \frac{z^k}{k!} = \sum_{k\ge j} \frac{1}{j!} \frac{z^k}{(k-j)!} = \frac{z^j}{j!} \sum_{k\ge j} \frac{z^{k-j}}{(k-j)!} = \frac{z^j}{j!} \exp(z)$$ y $$ B(z) = \sum_{k\ge 0} (-1)^k \frac{z^k}{k!} = \exp(-z).$$ El producto $Q(z)$ de estos dos es $$Q(z) = \frac{z^j}{j!} \exp(z) \exp(-z) = \frac{z^j}{j!}.$$ La extracción de los coeficientes de la EGF con el coeficiente de operador de extracción claramente tenemos $$n! [z^n] Q(z) \quad = \quad \begin{cases} 0 & n\ne j \\ n! \frac{1}{j!} = 1 & n = j. \end{casos}$$ Esta es precisamente la definición de $\delta_{n,j}.$

Utilizamos $j$ en lugar de $i$ para evitar la confusión con variables complejas. Un cálculo similar se puede encontrar aquí.