Proof that the binomial transform is involution Let $\{x_n\}$, $n=0,1,2,\ldots$, be a sequence, and let $\{y_n\}$, $n=0,1,2,\ldots$, be its binomial transform, that is,
$$
y_n=\sum_{k=0}^{n} (-1)^k {n\choose k} x_k.
$$
I need to prove that the binomial transform is an involution, that is,
$$
x_n=\sum_{k=0}^{n} (-1)^k {n\choose k} y_k.
$$
I tried to use the combinatorial Vandermonde's identity but I failed. Please help me to prove.
 A: If $g(t) = \sum_{n=0}^\infty x_n t^n$ is the generating function of $\{x_n\}$,
then the generating function of $\{y_n\}$ is
$$ \eqalign{h(t) &= \sum_{n=0}^\infty \sum_{k=0}^n (-1)^k {n \choose k} x_k t^n\cr
&= \sum_{k=0}^\infty (-1)^k x_k \sum_{n=k}^\infty {n \choose k} t^n\cr
&= \sum_{k=0}^\infty (-1)^k x_k \frac{t^k}{(1-t)^{k+1}}
&= \dfrac{1}{1-t} g\left(-\frac{t}{1-t}\right)}$$
If $s = -t/(1-t)$, then $t = -s/(1-s)$, and this says
$$ g(s) = (1-t) h(t) = \dfrac{1}{1-s} h\left(-\frac{s}{1-s}\right)$$
Thus the generating function of the binomial transform of $\{y_n\}$ is $g$ again.
A: Suppose we seek to prove that
$$b_n = \sum_{k=0}^n (-1)^k {n\choose k}
\sum_{q=0}^k (-1)^q {k\choose q}  b_q.$$
Reversing the two sums we obtain
$$\sum_{q=0}^n (-1)^q b_q \sum_{k=q}^n
(-1)^k {n\choose k} {k\choose q}.$$
We have
$${n\choose k} {k\choose q} =
{n\choose q} {n-q\choose k-q}$$ 
and we obtain
$$\sum_{q=0}^n (-1)^q b_q \sum_{k=q}^n
(-1)^k {n\choose q} {n-q\choose k-q}
\\ = \sum_{q=0}^n (-1)^q {n\choose q} b_q 
\sum_{k=q}^n (-1)^k  {n-q\choose k-q}
\\ = \sum_{q=0}^n {n\choose q} b_q 
\sum_{k=0}^{n-q} (-1)^k  {n-q\choose k}.$$
Now the inner sum is $(-1)^0 {0\choose 0} = 1$ when $q=n$
and $(1-1)^{n-q} = 0$ otherwise. This leaves
$${n\choose n} b_n = b_n.$$
A: It is also convenient to show the involution property with the help of exponential generating functions.

Let
  \begin{align*}
A(t)=\sum_{n=0}^\infty x_{n}\frac{t^n}{n!} \qquad\text{and}\qquad B(t)=\sum_{n=0}^\infty y_{n}\frac{t^n}{n!}
\end{align*}
  the exponential generating functions of  $\{x_n\}$ and $\{y_n\}$.

Since
\begin{align*}
A(-t)e^t&=\left(\sum_{k=0}^\infty x_{k}\frac{(-t)^k}{k!}\right)\left(\sum_{l=0}^\infty \frac{t^l}{l!}\right)\\
&=\sum_{n=0}^\infty\left(\sum_{{k+l=n}\atop{k,l\geq 0}}\frac{(-1)^kx_k}{k!}\cdot\frac{1}{l!}\right)t^n\\
&=\sum_{n=0}^\infty\left(\sum_{k=0}^n\binom{n}{k}(-1)^kx_k\right)\frac{t^n}{n!}\\
&=\sum_{n=0}^\infty y_n\frac{t^n}{n!}\\
&=B(t)
\end{align*}

we obtain the following correspondence
  \begin{align*}
B(t)=A(-t)e^t\qquad\longleftrightarrow\qquad y_n=\sum_{k=0}^n\binom{n}{k}(-1)^k x_{k}\tag{1}
\end{align*}

Multiplication with $e^{-t}$ and substitution $t$ with $-t$ gives
\begin{align*}
A(t)=B(-t)e^{t}
\end{align*}

According to (1) we conclude due to symmetry
\begin{align*}
A(t)=B(-t)e^t\qquad\longleftrightarrow\qquad x_n=\sum_{k=0}^n \binom{n}{k}(-1)^ky_{k}
\end{align*}
  and the claim follows since sequence and its binomial transform have the same generating function.

A: Let $L$ be the linear transformation from the space of polynomials in $t$ into the space of scalars that is determined by
$$
L(t^n) = x_n \text{ for } n = 0,1,2,\ldots.
$$
Then
$$
y_n = \sum_{k=0}^n (-1)^k \binom n k x_k = \sum_{k=0}^n (-1)^k \binom n k L(t^k) = L\left( \sum_{k=0}^n \binom n k (-t)^k \right) = L((1-t)^n).
$$
And
\begin{align}
x_n & = L(t^n) = L((1-(1-t))^n) = L \left( \sum_{k=0}^n (-1)^k \binom n k (1-t)^k \right) \\[10pt]
& =  \sum_{k=0}^n (-1)^k \binom n k L((1-t)^k) = \sum_{k=0}^n (-1)^k \binom n k y_k.
\end{align}
(As far as I know, this argument is due to Gian-Carlo Rota.)
A: Consider the linear transformation of polynomials
$P(t) \mapsto P(1-t)$, clearly an involution
$$a_0 + a_1 X + a_2 X^2 + \cdots \mapsto a_0 + a_1(1-X) + a_2 (1-X)^2 + \cdots $$
so the map in terms of  the coefficients is
$(a_i) \mapsto (b_i)$
where
$$b_i = \sum_{k\ge i}(-1)^k \binom{k}{i} a_k$$
We see that we binomial transform  is the dual (transpose) of this involution, so again an involution.
