I want to prove that $$ \sum_{k=i}^n \binom{n}{k}\binom{k}{i}(-1)^{n-k}=\delta_{n,i} $$ Where $\delta_{n,i}$ is the Kronecker Delta, i.e. $\delta_{n,i}=0$ if $n \neq i$ and $\delta_{n,i}=1$ if $i=n$.
I have an intuitive proof with matrices representing the linear transformation $F(x)=(1+x)^n$ and $G(x)=(1-x)^n$ and their product. But I'd prefer an accurate proof, if it exists. Thanks.
By the binomial theorem we have
$$\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}$$
and of course
$$x^n = \sum_{i=0}^n \delta_{n,i}x^i.$$
The sum is $$(-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)}.$$ This is illustrated below:
We observe that $f(T)$ is equal to the number of even-sized subsets of $T$ containing $S$ minus the number of odd-sized subsets of $T$ containing $S$. Hence $f(T)=0$, and consequently the whole sum $=0$, unless $i=n$, in which case $S=[n]$, and the sum simplifies to $$(-1)^{n} (-1)^{n}=1.$$
Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ 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\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
In the present case we have $$ A(z) = \sum_{k\ge 0} {k\choose 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)$$ and $$ B(z) = \sum_{k\ge 0} (-1)^k \frac{z^k}{k!} = \exp(-z).$$ The product $Q(z)$ of these two is $$Q(z) = \frac{z^j}{j!} \exp(z) \exp(-z) = \frac{z^j}{j!}.$$ Extracting coefficients of the EGF with the coefficient extraction operator we clearly have $$n! [z^n] Q(z) \quad = \quad \begin{cases} 0 & n\ne j \\ n! \frac{1}{j!} = 1 & n = j. \end{cases}$$ This is precisely the definition of $\delta_{n,j}.$
We use $j$ instead of $i$ to avoid confusion with complex variables. A similar computation may be found here.
