Putnam 1997, Problem B-4

Let $a_{m,n}$ denote the coefficient of $x^n$ in the expansion of $(1 + x + x^2)^m$. Prove that for all [integers] $k \geq 0$,
$$0 \leq \sum_{i=0}^{\lfloor 2k/3 \rfloor} (-1)^i a_{k-i,i} \leq 1.$$

Solution:
Let \( s_k = \sum_i (-1)^i a_{k-1,i} \) be the given sum (note that \( a_{k-1,i} \) is nonzero precisely for \( i = 0, \ldots, \lfloor \frac{2k}{3} \rfloor \)). Since  
\[
a_{m+1,n} = a_{m,n} + a_{m,n-1} + a_{m,n-2},
\]  
we have  
\[
s_k - s_{k-1} + s_{k+2} = \sum_i (-1)^i (a_{n-i,i} + a_{n-i,i+1} + a_{n-i,i+2}) = \sum_i (-1)^i a_{n-i+1,i+2} = s_{k+3}.
\]  
By computing \( s_0 = 1, s_1 = 1, s_2 = 0 \), we may easily verify by induction that \( s_{4j} = s_{4j+1} = 1 \) and \( s_{4j+2} = s_{4j+3} = 0 \) for all \( j \geq 0 \). (Alternate solution suggested by John Rickert: write \( S(x,y) = \sum_{i=0}^\infty (y + xy^2 + x^2 y^3)^i \), and note that \( s_k \) is the coefficient of \( y^k \) in \( S(-1,y) = (1 + y)/(1 - y^4) \).)