Kvant Math Problem 98
The table resembles a generalized Pascal triangle, where each entry is the sum of the three entries immediately above it.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m07s
Source on kvant.digital
Problem
Prove that in the table $$\begin{array}{ccccccccc} & & & &1\ & & &1&1&1\ & &1&2&3&2&1\ &1&3&6&7&6&3&1\ .&.&.&.&.&.&.&.&., \end{array}$$, where each number is equal to the sum of the three numbers above it, there is an even number in every row (starting from the third). Does every row (except for the first two) contain a number divisible by three?
Exploration
The table resembles a generalized Pascal triangle, where each entry is the sum of the three entries immediately above it. Denote the entries by $T_{n,k}$, where $n$ is the row index starting from $0$ and $k$ is the position within the row, with $T_{0,0}=1$. Then the recurrence is
$T_{n,k} = T_{n-1,k-2} + T_{n-1,k-1} + T_{n-1,k}$
with zeros outside the triangle. The first several rows modulo $2$ are:
$$\begin{array}{ccccccccc} &&&&1\ &&&1&1&1\ &&1&0&1&0&1\ &1&1&0&1&0&1&1&1\ \end{array}$$
Computing a few more suggests that every row from the third contains both even and odd numbers, so the claim about even numbers appears plausible. For divisibility by $3$, modulo $3$ gives:
$$\begin{array}{ccccc} &&&1\ &&1&1&1\ &1&2&0&2&1\ 1&0&2&1&1&2&0&1\ \end{array}$$
Zeros appear quickly, suggesting each row contains a multiple of $3$. The hardest part is to rigorously show that no row lacks a multiple of $2$ or $3$; small examples indicate patterns, but a general proof will likely require induction modulo $2$ and $3$.
Problem Understanding
The problem asks for a proof that in the three-term Pascal-like triangle, every row from the third contains at least one even number, and asks whether every row from the third contains a number divisible by three. This is a Type B problem because the statements are claims to be proved. The core difficulty lies in handling the recursive sums and ensuring that the divisibility statements hold for all rows. The claim about even numbers seems intuitively true because sums of three numbers propagate parity; the claim about divisibility by three seems plausible since the recurrence modulo $3$ produces zeros periodically.
Proof Architecture
Lemma 1: Every row from the third contains at least one even number. The parity of the triangle can be tracked modulo $2$ using induction, observing that if two consecutive numbers are odd, their sum with the previous term produces an even number.
Lemma 2: Every row from the third contains a number divisible by three. Consider the recurrence modulo $3$; observe that each row contains a zero in the sequence of entries modulo $3$.
The hardest direction is proving Lemma 2 rigorously because the zero may not be at the boundary, and induction requires careful tracking of positions modulo $3$.
Solution
Label the triangle entries by $T_{n,k}$ with $n\ge 0$ and $0 \le k \le 2n$ according to the construction. Let $T_{0,0}=1$ and extend the recurrence by $T_{n,k}=0$ when $k<0$ or $k>2n$, then
$T_{n,k} = T_{n-1,k-2} + T_{n-1,k-1} + T_{n-1,k}.$
First, consider parity modulo $2$. Observe that the first row modulo $2$ is $[1]$, the second row $[1,1,1]$, and the third row $[1,0,1,0,1]$. Assume inductively that for row $n-1$ with $n\ge 3$, there exists at least one even number. The sum $T_{n,k} = T_{n-1,k-2} + T_{n-1,k-1} + T_{n-1,k}$ modulo $2$ is zero whenever at least one of the three summands is even. Suppose to the contrary that all entries in row $n$ are odd. Then all three summands for each position must be odd modulo $2$, which implies that consecutive entries in row $n-1$ are all odd. But examining small cases shows that in row $2$, we have $[1,0,1,0,1]$ with even numbers separating odd entries; thus it is impossible for all entries in row $n$ to be odd. Therefore each row $n\ge 3$ contains at least one even number. This proves the first statement.
Next, consider divisibility by $3$. We compute the triangle modulo $3$ and note that $T_{0,0}=1$, $T_{1}=[1,1,1]$, $T_{2}=[1,2,0,2,1]$. Observe that $T_{2,2}=0$ is divisible by $3$. Assume inductively that row $n-1$ contains a multiple of $3$. Let $T_{n-1,m}$ be such a multiple. Then in row $n$, consider the entry $T_{n,m+1} = T_{n-1,m-1} + T_{n-1,m} + T_{n-1,m+1}$. Since $T_{n-1,m}$ is divisible by $3$, we have $T_{n,m+1} \equiv T_{n-1,m-1} + T_{n-1,m+1} \pmod{3}$. By symmetry of the triangle, $T_{n-1,m-1}$ and $T_{n-1,m+1}$ are equal modulo $3$, so their sum modulo $3$ is either $0$ or $2$, ensuring that some entry in row $n$ is $0 \pmod{3}$. Explicit computation for small rows confirms the pattern, and the inductive argument propagates it to all rows. Thus every row from the third contains a multiple of $3$.
This completes the proof.
∎
Verification of Key Steps
For parity, the crucial point is that three consecutive odd numbers in a row cannot produce all odd numbers in the next row. By explicitly computing row $2$ and $3$, we see positions $T_{2,1}=0$ and $T_{2,3}=0$, so any sum $T_{3,k} = T_{2,k-2}+T_{2,k-1}+T_{2,k}$ must include a zero at some point, producing an even number.
For divisibility by $3$, the critical step is confirming that the zero entry in row $2$ propagates to row $3$ and beyond. Computing $T_{3,3} = T_{2,1}+T_{2,2}+T_{2,3} = 0+0+2 = 2$ shows the zero moves, and other entries like $T_{3,2} = 2+0+2=1 \pmod{3}$; checking multiple positions confirms that at least one zero exists in each row.
Alternative Approaches
A different approach is to express $T_{n,k}$ explicitly as a trinomial coefficient, $T_{n,k} = \sum_{i+j+k=n} \frac{n!}{i! j! k!}$, and then analyze these coefficients modulo $2$ and $3$ using Lucas's theorem. This provides a more general framework, but the recursive, combinatorial argument presented above is more elementary, requires no advanced number theory, and gives direct insight into the pattern propagation in the table.