21. The sequence $\left\{a_{n}\right\}$ is defined as follows: $a_{1}=0, a_{2}=1$ and for $n \geqslant 3$, $a_{n}=\frac{1}{2} n a_{n-1}+\frac{1}{2} n(n-1) a_{n-2}+(-1)^{n}\left(1-\frac{n}{2}\right)$. Try to find: $f_{n}=\sum_{k=0}^{n-1}(k+1) C_{n}^{k} a_{n-k}$ in its simplest form.
21. Solution 1 Let $b_{n}=\frac{a_{n}}{n!}$, then $b_{1}=0, b_{2}=\frac{1}{2}, b_{3}=\frac{1}{3}$, and $b_{n}=\frac{1}{2}\left(b_{n-1}+b_{n-2}\right)+(-1)^{n} \frac{1}{n!}(1-$
$$
\left.\frac{n}{2}\right), b_{n}-b_{n-1}-(-1)^{n} \frac{1}{n!}=-\frac{1}{2}\left[b_{n-1}-b_{n-2}-(-1)^{n-1} \frac{1}{(n-1)!}\right] \text {. Let } d_{n}=b_{n}-b_{n-1}-(-1)^{n} \frac{1}{n!} \text {, }
$$

then $d_{n}=-\frac{1}{2} d_{n-1}$. And $d_{2}=b_{2}-b_{1}-(-1)^{2} \frac{1}{2!}=0, \therefore d_{3}=-\frac{1}{2} d_{2}=0, \cdots, d_{n}=0$, i.e., $b_{n}-b_{n-1}=$ $(-1)^{n} \frac{1}{n!}$. Let $g_{n}=\frac{f_{n}}{n!}$, then $g_{n}=\frac{1}{n!} \sum_{k=0}^{n-1}(k+1) C_{n}^{k} a_{n-k}=\frac{1}{n!} \sum_{k=1}^{n}(n-k+1) C_{n}^{n-k} a_{k}=\sum_{k=1}^{n} \frac{n-k+1}{(n-k)!} b_{k}$, $g_{n+1}-g_{n}=\sum_{k=1}^{n+1} \frac{n-k+2}{(n+1-k)!} b_{k}-\sum_{k=1}^{n} \frac{n-k+1}{(n-k)!} b_{k}=\sum_{k=2}^{n+1} \frac{n-k+2}{(n+1-k)!} b_{k}-\sum_{k=2}^{n+1} \frac{n-k+2}{(n-k+1)!} b_{k-1}=$ $\sum_{k=2}^{n+1} \frac{n-k+2}{(n-k+1)!}\left(b_{k}-b_{k-1}\right)=\sum_{k=2}^{n+1} \frac{n-k+2}{(n-k+1)!}(-1)^{k} \frac{1}{k!}=\sum_{k=2}^{n} \frac{(-1)^{k}}{(n-k)!k!}+\sum_{k=2}^{n+1} \frac{(-1)^{k}}{(n-k+1)!k!}=$ $\frac{1}{n!} \sum_{k=2}^{n}(-1)^{k} C_{n}^{k}+\frac{1}{(n+1)!} \sum_{k=2}^{n+1}(-1)^{k} C_{n+1}^{k}$. Since $\sum_{k=0}^{n}(-1)^{k} C_{n}^{k}=(1-1)^{n}=0, \sum_{k=0}^{n+1}(-1)^{k} C_{n+1}^{k}=(1-1)^{n+1}=$ 0 , so $g_{n+1}-g_{n}=-\frac{1}{n!}(1-n)-\frac{1}{(n+1)!}[1-(n+1)]=\frac{1}{(n-1)!}-\frac{1}{(n+1)!}$. And $g_{2}=\frac{f_{2}}{2!}=\frac{1}{2}\left[a_{2}+\right.$ $\left.2 C_{2}^{1} a_{1}\right]=\frac{1}{2}, \therefore g_{n}=g_{2}+\sum_{k=2}^{n-1}\left(g_{k+1}-g_{k}\right)=\frac{1}{2}+\sum_{k=2}^{n-1}\left[\frac{1}{(k-1)!}-\frac{1}{(k+1)!}\right]=\frac{1}{2}+\frac{1}{1!}+\frac{1}{2!}-\frac{1}{(n-1)!}-$ $\frac{1}{n!}=2-\frac{n+1}{n!}$. Therefore, $f_{n}=n!g_{n}=2 n!-(n+1)$.

Solution 2 First, we prove that $a_{n}$ is the derangement number $D_{n}$ in Example 1 of Chapter 1, §2-5. In fact, $a_{n}-n a_{n-1}-$ $(-1)^{n}=-\frac{n}{2}\left[a_{n-1}-(n-1) a_{n-2}-(-1)^{n-1}\right]$. Let $b_{n}=a_{n}-n a_{n-1}-(-1)^{n}$, then $b_{n}=-\frac{n}{2} b_{n-1}$, and $b_{2}=a_{2}-$ $2 a_{1}-(-1)^{2}=0, \therefore b_{3}=-\frac{3}{2} b_{2}=0, \cdots, b_{n}=0$, hence $a_{n}-n a_{n-1}=(-1)^{n}$ and $a_{1}=0, a_{1}=1$. This is exactly the same as the recurrence relation of the derangement number $D_{n}$ in Example 1 of Chapter 1, §2-6, so $a_{n}=D_{n}$. Next, the total number of permutations of $n$ different elements is $n$!, which can be divided into $n+1$ categories, where the $k$-th category is the permutations with $k$ elements deranged and the remaining $n-k$ elements remain unchanged, and the number of such permutations is $C_{n}^{k} D_{k}=C_{n}^{k} a_{k}$ $(k=0,1,2, \cdots, n)$, so $\sum_{k=0}^{n} C_{n}^{k} a_{k}=n!$, here $D_{0}=a_{0}=1$ represents the number of permutations with no elements deranged, so $\sum_{k=1}^{n} C_{n}^{k} a_{k}=n!-1$. Using $k C_{n}^{k}=n C_{n-1}^{k-1}$ we get $f_{n}=a_{n}+2 C_{n}^{1} a_{n-1}+3 C_{n}^{2} a_{n-2}+\cdots+(n-1) C_{n}^{n-2} a_{2}+$
$$
\begin{array}{l}
n C_{n}^{n-1} a_{1}=\left(C_{n}^{n} a_{n}+C_{n}^{n-1} a_{n-1}+\cdots+C_{n}^{1} a_{1}\right)+\left(C_{n}^{1} a_{n-1}+2 C_{n}^{2} a_{n-2}+\cdots+(n-2) C_{n}^{n-2} a_{2}+(n-1) C_{n}^{n-1} a_{1}\right) \\
=\left(C_{n}^{n} a_{n}+C_{n}^{n-1} a_{n-1}+\cdots+C_{n}^{2} a_{2}+C_{n}^{1} a_{1}\right)+n\left(a_{n-1}+C_{n-1}^{1} a_{n-2}+\cdots+C_{n-1}^{n-3} a_{2}+C_{n-1}^{n-2} a_{2}\right)=\sum_{k=1}^{n} C_{n}^{k} a_{k}+ \\
n \sum_{k=1}^{n-1} C_{n-1}^{k} a_{k}=(n!-1)+n[(n-1)!-1]=2 n!-(n+1) .
\end{array}
$$