Show that the coefficient of x^{k} in the expansion of (1 + x + x^{2} + x^{3})^{n} is ∑_{j=0}^{k} nCj nC(k-2j).

**Solution**

1 + x + x^{2} + x^{3} = (1 + x)(1 + x^{2}). So the expression is (∑ nCi x^{i}) (∑ nCj x^{2j}). To get a term in x^{k} we must multiply a term x^{2j} by a term x^{n-2j} for some j. The result follows.

© John Scholes

jscholes@kalva.demon.co.uk

7 Jan 2001