Here is another proof.

First, I prove the statement in the hint that I gave. Consider the exponential generating function

$\displaystyle g_B(z)=\sum_{j=0}^\infty b_j \frac{z^j}{j!}$

of the sequence $\displaystyle B=\{b_j\}$. By the basic properties of exponential generating functions, the product of the exponential generating functions of two sequences is the exponential generating function of their binomial convolution. So we have

$\displaystyle g_A(z) = \sum_{j=0}^\infty a_j \frac{z^j}{j!} = e^zg_B(z)$

and so $\displaystyle g_B(z)=e^{-z}g_A(z)$. Extracting the coefficient of $\displaystyle \frac{z^n}{n!}$ on both sides we obtain $\displaystyle b_n = \sum_{j=0}^n {n \choose j}(-1)^{n-j}a_j$ as required.

Now let us partition the set $\displaystyle S_n$ of permutations of $\displaystyle \{1,\dots,n\}$ as follows; let $\displaystyle T_j \subset S_n$ denote those permutations which have precisely $\displaystyle j$ fixed points, for $\displaystyle j=0, \dots, n$. Clearly there are $\displaystyle {n \choose j}$ ways of picking the elements which are to be fixed, and the remaining $\displaystyle n-j$ elements have to be deranged. So $\displaystyle |T_j| = {n \choose j}!(n-j)$. Since the $\displaystyle T_j$ are clearly distinct we have

$\displaystyle |S_n|=n!=\sum_{j=0}^n|T_j| = \sum_{j=0}^n{n \choose j}!(n-j) = \sum_{j=0}^n{n \choose j}!j$

because $\displaystyle {n \choose j} = {n \choose n-j}$. Now just apply the binomial involution just proved!