$\sum_{k=0}^n{\binom{n}{k}\binom{n+k}{k}} = 0 \pmod 3$ iff there is at least a $1$ in the ternary expansion of $n$

Question

While playing with OEIS sequences, I conjectured the following:

$$\sum_{k=0}^n{\binom{n}{k}\binom{2k}{k}} = 0 \pmod 3$$

if and only if $n$ has at least a $1$ digit in its ternary expansion (OEIS A081606).

The LHS is OEIS A026375. Originally, I have obtained it computing the largest coefficient of $(1+3x+x^2)^n$.

At OEIS A081606 a comment says that the following holds for the sequence:

$$\sum_{k=0}^n{\binom{n}{k}\binom{n+k}{k}} = 0 \pmod 3$$

The LHS in the congruence above are the central Delannoy numbers.

Also, the complement of A081606 (OEIS A005823) lists two more congruences $\mod 3$.

Any hint for proving the conjecture?

Answer 1

Yes, your conjecture holds. Note that $$\begin{align} T_n&=[x^n](1+3x+x^2)^n=[x^n]((1+x)^2+x)^n\\ &=[x^n]\sum_{k=0}^n\binom{n}{k}(1+x)^{2k}x^{n-k}=\sum_{k=0}^n{\binom{n}{k}\binom{2k}{k}} \end{align}$$ and according to (13) (where $T_n=[x^n](a+bx+cx^2)^n$), for any odd prime $p$ the following general Lucas-type congruence holds $$T_n\equiv T_{n_0}T_{n_1}\cdots T_{n_r}\pmod{p}$$ where $n_0+n_1 p +\dots +n_r p^r$ is $n$ written in base $p$.

If $p=3$ then $n_i\in\{0,1,2\}$ and $T_{0}=1$, $T_{1}=3$, $T_{2}=11$. It follows that $T_n\equiv 0\pmod{3}$ iff at least one of $n_i$'s is $1$.

A similar approach can be applied for the central Delannoy numbers: $$D_n=\sum_{k=0}^n{\binom{n}{k}\binom{n+k}{k}}=[x^n](1 + 3x + 2x^2)^n$$ and $D_{0}=1$, $D_{1}=3$, $D_{2}=13$.

Answer 2

Here I develop @MikeEarnest and @RobertZ comments on the accepted answer to use only Lucas's theorem.

We have that (see the accepted answer):

$$\sum_{k=0}^{n}\binom{n}{k}\binom{2k}{k} = [x^n](1+3x+x^2)^n \equiv [x^n](1+x^2)^n \pmod 3$$

For any $n$ odd, $[x^n](1+x^2)^n = 0$.

For $n$ even we have:

$$[x^n](1+x^2)^n = \binom{n}{n/2}$$

If $n$ has no $1$ in its ternary expansion, then each $2$ digit in $n$ corresponds to a $1$ digit in $n/2$ and each $0$ digit in $n$ corresponds to a $0$ digit in $n/2$, therefore by Lucas's theorem $\binom{n}{n/2} \not \equiv 0 \pmod 3$. By contradiction, if $\binom{n}{n/2} \equiv 0 \pmod 3$ then $n$ must have a $1$ in its ternary expansion.

If $n$ has a $1$ digit or more in its ternary expansion, then the number of ones must be even, because $n$ is even.

The ternary expansion of $n$ will be:

$$d_{1,1}\ldots d_{1,r_1}1d_{2,1}\ldots d_{2,r_2}1\ldots1d_{s-1,1}\ldots d_{s-1,r_{s-1}}1d_{s,1}\ldots d_{s,r_s}$$

with $d_{i,j} \in \{0,2\}$.

while the ternary expansion of $n/2$ can be obtained as the sum of:

$$e_{1,1}\ldots e_{1,r_1}0e_{2,1}\ldots e_{2,r_2}0\ldots0e_{s-1,1}\ldots e_{s-1,r_{s-1}}0e_{s,1}\ldots e_{s,r_s}$$

and

$$f_{1,1}\ldots f_{1,r_1}0f_{2,1}\ldots f_{2,r_2}2\ldots0f_{s-1,1}\ldots f_{s-1,r_{s-1}}2f_{s,1}\ldots f_{s,r_s}$$

where $e_{i,j} = d_{i,j}/2$ and thus $e_{i,j} \in \{0,1\}$, $f_{i,j} = 0$ for $i=1,s$ and $f_{i,j} = 1$ for $1 \lt i \lt s$. Then $e_{i.j}+f_{i,j} \lt 3$ and therefore there can be no carry when adding the two numbers. Summing the digits $0$ in the first number and $2$ in the second number (corresponding to every second $1$ in the ternary expansion of $n$), we have a $2$ digit in $n/2$, therefore we can apply Lucas's theorem and get $\binom{n}{n/2} \equiv \binom{1}{2} \equiv 0 \pmod 3$.