What is the maximum sum of coefficients in a binomial expansion?

[Ackbach]

Here is this week's POTW:

-----

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 \frac{2k}{3}\rfloor} (-1)^i a_{k-i,i}\leq 1.\]

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 235 - Sep 29, 2016

This was Problem B-4 in the 1997 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

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, \dots, \lfloor \frac{2k}{3} \rfloor)$. Since
\[
a_{m+1,n} = a_{m,n} + a_{m,n-1} + a_{m,n-2},
\]
we have
\begin{align*}
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}.
\end{align*}
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$.