Let (1 + x + x^{2})^{m} = ∑_{0}^{2m} a_{m,n}x^{n}. Prove that for all k ≥ 0, ∑_{0}^{[2k/3]} (-1)^{i}a_{k-i,i} ∈ [0,1].

**Solution**

*Straightforward. (Easy if you instinctively leap for generating functions).*

Notice first that, if we let a_{m,n} = 0 where there is no term x^{n} in the expansion, then the required sum is simply taken over all i.

There are two ways to do this. The straightforward way is induction, using the fact that a_{m+1,n}= a_{m,n} + a_{m,n-1} + a_{m,n-2}. If S(k) denotes the sum for k, then we find that S(k) = S(k-1) - S(k-2) + S(k-3). This is a routine computation.

The slick way is to use a generating function in two variables f(x,y) = ∑ a_{m,n} y^{m}x^{n}. Then if we set x = - y, we find that the coefficient of y^{k} is the required sum. But f(x, y) = 1/(1 - y(1+x+x^{2})), so f(-y, y) = (1 + y)/(1 - y^{4}) = (1 + y)(1 + y^{4} + y^{8} + ... ) and the coefficient of y^{k} = 1 if k = 0 or 1 (mod 4), 0 otherwise.

© John Scholes

jscholes@kalva.demon.co.uk

12 Dec 1998