2
$\begingroup$

Catalan numbers are $c_n=\frac{1}{n+1}{\binom {2n}{n}}$.

Prove that $\sum_{k=1}^n c_k\equiv 1 \mod 3 \iff$ The digit $2$ appears in the ternary representation of $n+1$.

I was shown the solution a while ago and forgot it: It relies on finding some short identity that $c_n$ satisfy when considered modulo $3$, and using Lucas' theorem: $\binom{n}{k}$ is divisible by 3 iff when adding $k+(n-k)$ in base $3$ there is a carry.

$\endgroup$
1
$\begingroup$

$$\binom{2k+2}{k+1} -\binom{2k}{k}-\frac 1{k+1}\binom{2k}{k} = \binom{2k}{k} \left(\frac{(2k+2)(2k+1)}{(k+1)(k+1)}-1-\frac1{k+1}\right) = \binom{2k}{k} \frac{3k}{k+1} = 3 \binom{2k}{k+1}. $$

Which is clearly a multiple of three.

$\endgroup$
1
$\begingroup$

I was told the main part of the proof: we show that $\sum_{k=1}^n c_k -1 \equiv \binom{2(n+1)}{n+1} \mod 3$, and then we get $$\sum_{k=1}^n c_k -1 \equiv 0 \mod 3 \iff \binom{2(n+1)}{n+1} \equiv 0 \mod 3$$
$ \iff$there is a carry when adding $(n+1)+(n+1)$ in base $3$ $\iff$ The digit $2$ appears in the ternary representation of $n+1$.

Therefore, it suffices to prove $c_k \equiv \binom{2k+2}{k+1} - \binom{2k}{k} \mod 3$, and we will get by a telescopic series what we wanted. Can someone now tie the last knot and prove the congruence?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.