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?
Best Answer
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$.