binomial coefficients modulo $3$

Question

Let $a(n)$ be the number of binomial coefficient's on the $n$-th row of Pascal's triangle which leave remainder $1$ upon division by $3$, and $b(n)$ be the number that leave remainder $2$. Show that $a(n)-b(n)$ is a power of $2$. So I stumbled upon this problem in a book by Naoki Sato online and have been unable to crack it since. After generating the first few values of $a(n)-b(n)$ on python, I'm fairly convinced that the answer to the problem has something to do with the base $3$ representation of $n$, but so far I have been unable to make real progress.

Answer 1

The problem at the bottom of page $5$ of this PDF is to show that $a(n)>b(n)$ for all $n\in\Bbb Z^+$. The solution by Andy Liu at the top of page $6$ is easily modified to show that $a(n)-b(n)$ is a power of $2$ for all $n\in\Bbb N$. All congruences are modulo $3$.

Let

$$n=\sum_{i=0}^k3^in_i\,,$$

where each $n_i\in\{0,1,2\}$. Then

$$(1+x)^n\equiv\prod_{i=0}^k(1+x)^{3^in_i}\equiv\prod_{i=0}^k\left(1+x^{3^i}\right)^{n_i}\,.$$

For $0\le\ell\le k$ let

$$F_\ell(x)=\prod_{i=0}^\ell\left(1+x^{3^i}\right)^{n_i}\,,$$

and let $c(\ell)$ be the amount by which the number of coefficients of $F_\ell(x)$ congruent to $1$ exceeds the number congruent to $2$. $F_0(x)=(1+x)^{n_0}$, so $F_0(x)$ is $1$, $1+x$, or $1+2x+x^2$, so $c(0)$ is $2^0$ or $2^1$. Suppose that $0\le\ell<k$, and $c(\ell)=2^m$. Then

$$F_{\ell+1}(x)=\left(1+x^{3^{\ell+1}}\right)^{n_{\ell+1}}F_\ell(x)\,,$$

and we consider the three possibilities for $n_{\ell+1}$.

• If $n_{\ell+1}=0$, $F_{\ell+1}(x)=F_\ell(x)$, so $c(\ell+1)=2^m$.
• If $n_{\ell+1}=1$, $F_{\ell+1}(x)=F_\ell(x)+x^{3^{\ell+1}}F_\ell(x)$, where $\deg F_\ell(x)<3^{\ell+1}$. $x^{3^{\ell+1}}F_\ell(x)$ has the same coefficients as $F_\ell(x)$, so $c(\ell+1)=2^{m+1}$.
• If $n_{\ell+1}=2$, $F_{\ell+1}(x)=F_\ell(x)+2x^{3^{\ell+1}}F_\ell(x)+x^{2\cdot3^{\ell+1}}F_\ell(x)$, where again there are no like terms. Modulo $3$ the coefficients of $2x^{3^{\ell+1}}F_\ell(x)$ are the negatives of the coefficients of $F_\ell(x)$, and $x^{2\cdot3^{\ell+1}}F_\ell(x)$ has the same coefficients as $F_\ell(x)$, so $c(\ell+1)=2^m$.

In every case $c(\ell+1)$ is a power of $2$, so by induction $c(k)$ is a power of $2$, and clearly $c(k)=a(k)-b(k)$.