MathDB

Coefficient in (1+x+x^2+x^3)^n

Source:

November 29, 2006

factorialPutnamStanfordcollege

Problem Statement

For nonnegative integers

n

and

k

, define

Q(n, k)

to be the coefficient of

x^{k}

in the expansion

(1+x+x^{2}+x^{3})^{n}

. Prove that

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

. [hide="hint"] Think of

\binom{n}{j}

as the number of ways you can pick the

x^{2}

term in the expansion.

Back to Problems View on AoPS