5
$\begingroup$

Introduce the sequence (this is A047781 on OEIS) $$t_n=\sum_{k=0}^{n-1}\binom{n-1}k\binom{n+k}k$$ and denote the set $T(ij)=\{n\in\mathbb{N}: \text{the ternary digits of $n$ contain $i$ or $j$ only}\}$.

QUESTION. Is this true modulo $3$? $$t_n\equiv_3\begin{cases} 1 \qquad \text{if $\lfloor\frac{n}2\rfloor\in T(01)$} \\ 0 \qquad \text{otherwise}. \end{cases}$$

$\endgroup$
5
  • 3
    $\begingroup$ These kind of questions (for any prime, not only 3) can in principle be solved by a general result of Denef and Lipshitz, connecting finite automata with reduction of algebraic functions (or diagonals of rational functions) modulo p. A good reference with theory and examples is "Automatic congruences for diagonals of rational functions" by Rowland and Yassawi, Journal de Théorie des Nombres de Bordeaux 27 (2015), 245–288. $\endgroup$ Commented Jun 21, 2021 at 22:31
  • $\begingroup$ Is the question stated correctly? From the formula, $t_3 = \binom{2}{1}\binom{4}{1} + \binom{2}{2}\binom{5}{2} = 2 \times 4 + 1 \times 10 = 18 \equiv 0$ mod $3$. But $\lfloor 3/2 \rfloor = 1 \in T(01)$. Similarly $t_2 = \binom{1}{1}\binom{3}{1} = 1 \times 3 = 0$ mod $3$ and $\lfloor 2/1\rfloor = 1 \in T(01)$. $\endgroup$ Commented Jun 22, 2021 at 11:23
  • $\begingroup$ @MarkWildon: Oh, yes. The sum should start with $k=0$ not $k=1$. Thank you! $\endgroup$ Commented Jun 22, 2021 at 13:24
  • $\begingroup$ @OfirGorodetsky: I appreciate your reference. On the other hand, it might be an "overkill" to sort for those methods. So, I welcome more direct or elementary and specific proofs if possible. $\endgroup$ Commented Jun 22, 2021 at 13:55
  • $\begingroup$ If you want elementary, did you try a calculation with Lucas' theorem? At least to check that $t_n \equiv 1 \mod{3}$ if $\lfloor n/2 \rfloor \in T(01)$? It would seem like a natural approach for this problem. $\endgroup$
    – spin
    Commented Jun 22, 2021 at 13:57

2 Answers 2

7
$\begingroup$

The answer is Yes.

The generating function for $t_n$ is $$\sum_{n\geq 0} t_n x^n = \frac14\big(\frac{1+x}{\sqrt{1-6x+x^2}}-1\big).$$ Correspondingly, $$\sum_{n\geq 0} t_n x^n \equiv \frac{1+x}{\sqrt{1+x^2}}-1 \pmod{3}.$$ It follows that for $n>0$, $$t_n \equiv \binom{-1/2}{\lfloor n/2\rfloor}\equiv (-1)^{\lfloor n/2\rfloor}\binom{2\lfloor n/2\rfloor}{\lfloor n/2\rfloor}\pmod{3},$$ from where Lucas' theorem gives the desired result.

$\endgroup$
0
2
$\begingroup$

Here is a comment following Max Alekseyev's resolution. It has to do with his generating function for $t_n$ and working out directly on the Taylor's expansion (Binomial Theorem). Namely, $$\frac14\left(\frac{1+x}{\sqrt{1-6x+x^2}}-1\right) =\sum_{n=1}^{\infty}\frac{h(n-1)+h(n)}4\,x^n$$ where $$h(n)=\sum_{k=\lfloor\frac{n}2\rfloor}^n(-1)^{n+k}\binom{2k}k\binom{k}{n-k}3^{2k-n}2^{-n}.$$ To get to the conclusion we seek, let's just take $n\rightarrow 2n$ for instance. This leads to \begin{align*}t_{2n}=\frac{h(2n-1)+h(2n)}4&\equiv_3h(2n-1)+h(2n) \\ &\equiv_3\sum_{k=n}^{2n-1}(-1)^{k-1}\binom{2k}k\binom{k}{2n-1-k}3^{2k-2n+1}2^{-2n+1} \\ &+\sum_{k=n}^{2n}(-1)^k\binom{2k}k\binom{k}{2n-k}3^{2k-2n}2^{-2n} \\ &\equiv_3\sum_{k=n}^{2n}(-1)^k\binom{2k}k\binom{k}{2n-k}3^{2k-2n}2^{-2n} \\ &\equiv_3(-1)^n\binom{2n}n2^{-2n} \\ &\equiv_3(-1)^n\binom{2n}n. \end{align*}

$\endgroup$
3
  • $\begingroup$ What is benefit of this explicit expansion? $\endgroup$ Commented Jun 22, 2021 at 22:48
  • $\begingroup$ I liked two things (pedagogically speaking): (1) I noticed what I did not expect, that is, $4t_n=h(n-1)+h(n)$; (2) I noticed the presence of the quantities $3^m$ vanishing mostly. Of course, no doubt about your approach is neater. By the way, how do you prove the generating function works for $t_n$? I saw it appeared on OEIS. $\endgroup$ Commented Jun 22, 2021 at 23:02
  • $\begingroup$ I copied g.f. from the OEIS, but I'm pretty sure it can be easily obtained by Lagrange inversion. $\endgroup$ Commented Jun 22, 2021 at 23:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .