Let (1 + x + x2)m = ∑02m am,nxn. Prove that for all k ≥ 0, ∑0[2k/3] (-1)iak-i,i ∈ [0,1].
Solution
Straightforward. (Easy if you instinctively leap for generating functions).
Notice first that, if we let am,n = 0 where there is no term xn 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 am+1,n= am,n + am,n-1 + am,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) = ∑ am,n ymxn. Then if we set x = - y, we find that the coefficient of yk is the required sum. But f(x, y) = 1/(1 - y(1+x+x2)), so f(-y, y) = (1 + y)/(1 - y4) = (1 + y)(1 + y4 + y8 + ... ) and the coefficient of yk = 1 if k = 0 or 1 (mod 4), 0 otherwise.
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998