1992 Putnam B2

For nonnegative integers $n$ and $k$, define $Q(n, k)$ to be

the coefficient of $x^k$ in the expansion of $(1 + x + x^2 + x^3)^n$.

Prove that

$$

Q(n, k) = \sum_{j=0}^k \binom{n}{j} \binom{n}{k-2j},

$$

where $\binom{a}{b}$ is the standard binomial coefficient. (Reminder: For

integers $a$ and $b$ with $a \geq 0$, $\binom{a}{b} =

\frac{a!}{b!(a-b)!}$for$0 \leq b \leq a$, with$\binom{a}{b} = 0$ otherwise.)

对于非负整数 $n$ 和 $k$，定义 $Q(n, k)$ 为

$(1 + x + x^2 + x^3)^n$ 展开式中 $x^k$ 的系数。

证明

$$

Q(n, k) = \sum_{j=0}^k \binom{n}{j} \binom{n}{k-2j},

$$

其中 $\binom{a}{b}$ 是标准二项式系数。 (温馨提示：对于

整数 $a$ 和 $b$ 且 $a \geq 0$, $\binom{a}{b} =

\frac{a!}{b!(a-b)!}$表示$0 \leq b \leq a$，否则$\binom{a}{b} = 0$。)