Prove that every row of the Trinomial Triangle contains at least one even number.

Question

So the Trinomial Triangle is the coefficient of $x$ in $(1 + x + x^2) ^ n$.

I am investigating the coefficient modulo 2. In particular, I want to proof that each row of the Trinomial Triangle (start from the 3rd row) has at least 1 even number.

The first few rows of the triangle (under modulo 2):

                      1
                    1 1 1
                  1 0 1 0 1
                1 1 0 1 0 1 1
              1 0 0 0 1 0 0 0 1
            1 1 1 0 1 1 1 0 1 1 1
          1 0 1 0 0 0 1 0 0 0 1 0 1
        1 1 0 1 1 0 1 1 1 0 1 1 0 1 1
      1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
    1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1
  1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1
1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1

Can someone give me a clue on how should I tackle this problem? I suspect that the multinomial theorem might work here, or is there any 'generalizations' of the Lucas' Theorem?

Answer 1

If we look at

$$(1+x+x^2)(1+x+x^2)\cdots(1+x+x^2)=a_{2n}x^{2n}+\cdots+a_1x+a_0$$

From this, we can compute the term $a_i$. How many ways can we partition $i$ using only $0,1,2$ (and having $n$ terms)? Let's just assume $i<n$; we can do this since it seems $a_n$ will never be even so we won't even bother thinking about that, and $a_i=a_{2n-i}$ due to symmetry. So, if we manage to partition $i$ in terms of $1,2$ regardless of how many terms we use, then we can just fill that up with $0$'s to have $n$ terms. And we can't partition $i$ in more than $n$ terms since $i<n$. Now we partition $i$ using $j$ times the number $2$:

$$i= \underbrace{(2+\cdots+2+2)}_{j}+\underbrace{(1+\cdots+1+1)}_{i-2j}+\underbrace{(0+\cdots+0+0)}_{n-i+j}$$

And $j$ can range from $0$ to $\lfloor\tfrac12i\rfloor$. This means that (taking permutations into account):

$$a_i=\sum_{j=0}^{\lfloor i/2\rfloor}\frac{n!}{j!(i-2j)!(n-i+j)!}$$

So we need to prove that this is can be even.

---

Notice that $a_1=n$, so that if $n$ is even, we have an even term $a_1$. So, we'll assume $n$ is odd from now on.

---

Case 1: $n\equiv 1\mod 4$

Let's look at $a_3$:

$$a_3=\tfrac16n(n-1)(n-2)+n(n-1)$$

Now $n(n-1)$ is clearly even. Now note that $n-1\equiv 0\mod 4$ so that $\tfrac12(n-1)$ is even; hence, the entire $\tfrac16n(n-1)(n-2)$ is even, thus, $a_3$ is even.

---

Let's split cases.

Case 2: $n\equiv 3\mod 4$

Let's look at $a_2$:

$$a_2=\tfrac12n(n-1)+n$$

Now we see $n-1\equiv 2\mod 4$; hence, $\tfrac12(n-1)$ is odd. As a result, $a_2=\tfrac12n(n-1)+n$ is even. This concludes the $3\mod 4$ case.

---

We've handled all cases. To recap:

\begin{align} n\equiv 0\mod4&\implies a_1\text{ is even}\\ n\equiv 1\mod4&\implies a_3\text{ is even}\\ n\equiv 2\mod4&\implies a_1\text{ is even}\\ n\equiv 3\mod4&\implies a_2\text{ is even}\\ \end{align}

This concludes the proof.

Just a sidenote: I didn't say anything about the cases $n=0$ and $n=1$ throughout the whole proof; where are those? Well, as for $n=0$, it is true $a_1=0$ is even, but we don't consider it part of the polynomial as its degree is $0$. Similarly, it is true that for $n=1$, we have $a_3=0$, but again we don't count this as part of the polynomial as its degree is $2$. For $n>1$ however the even terms we found are part of the polynomials.