# A formula for the number of Catalan numbers divisible by 2^k

## Summary

The Catalan numbers are defined by $C_n = \frac{1}{n + 1} \binom {2n} {n}.$

This note will use results obtained by Liu and Yeh in  to obtain a formula for the number of $C_n < 2^{ t }$ which are divisible by $2^{ k }$   where $t, k \in \mathbb{N}.$

Firstly, as in , let the p-adic order of a positive integer n be defined by $\omega_p(\, n )\, := max\{\alpha \in \mathbb{N} : p^{\alpha} | n\} .$

and the cofactor of n with respect to $p^{ \omega_p(\, n )\, }$  be defined by $CF_p(\, n )\, := \frac {n} {p^{\omega_p(\, n )\,}} .$

In addition the function $\alpha : \mathbb{N} \to \mathbb{N}$  is defined by $\alpha (\, n )\, := \frac {CF_2(\, n + 1 )\, - 1} {2}.$

For a number p, we write the base p expansion of a number n as $[\, n ]\,_{p} = \langle n_{r} n_{r-1} ... n_{1} n_{0} \rangle$

where $n_{i} \in [\, 0, p - 1]\,$  and $n = n_{r} p^{r} + n_{r-1} p^{r-1} + ... + n_{1} p + n_{0}.$

Then the function $d : \mathbb{N} \to \mathbb{N} := d (\, n )\, = n_{r} + n_{r-1} + ... + n_{1} + n$  is the sum of the p-adic digits of a natural number n (i.e. the sum of the digits of n when n is written in base p). Here we will only be interested in the case $p = 2$ . Then

Theorem   1: $\#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k \} = \binom {t} {k + 1}.$

Corollary   2: $\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \sum_{i = k+1}^{i = t} \binom{t} {i}.$

Corollary   3: $\#\{n < 2^t: C_{n} \equiv 2^{k-1} \mod {2^k} \} = \binom{t} {k}.$

## Proofs.

Proof of Theorem 1:

Let $\alpha = \alpha (\, n )\, = \frac {CF_2(\, n + 1 )\, - 1} {2}$ .  Then $n + 1 = 2^{s} (\, 2^{\alpha} + 1 )\,$

for some arbitrary $s \in \mathbb{N} : s \geq 0$ .  Writing $n + 1$  in base 2 we have $[\, n + 1 ]\,_{2} = \langle [\, \alpha ]\,_{2}, 1, 0 ... 0, 0 \rangle$  where there are s  0’s at the end and $s \geq 0$  is arbitrary. So, $[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1 ... 1, 1 \rangle$  where there are s  1’s  at the end and $s \geq 0$  is arbitrary. It can be seen that $d(\, n )\, = d(\, \alpha )\, + s.$

Since $n < 2^{t}$  and $d(\, \alpha (\, n )\, )\, = k$  the possible base 2 representations of n are $[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0 \rangle$  with $\alpha < 2^{t - 1}$ $[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1 \rangle$  with $\alpha < 2^{t - 2}$

.

.

. $[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1, 1, ... 1 \rangle$  with $\alpha < 2^{k}$  and $(\, t - k - 1)\,$   1’s at the end.

Therefore, counting each of these possibilities and using the fact that $d (\, \alpha )\, = k$  gives $\#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k \} = \sum_{i = k}^{i = t - 1} \binom{i} {k} = \binom{t} {k + 1}.$ $\Box$

## Proof of Corollary 2.

The following result appears in .

Theorem 4 (Corollary 4.3 of ): In general, we have $\omega_{2} (\, C_{n} )\, = d (\, \alpha )\, .$   In particular, $C_{n} \equiv 0 (\, mod 2^{k} )\,$  if and only if $d (\, \alpha )\, \geq k$ ,  and $C_{n} \equiv 2^{k - 1} (\, mod 2^{k} )\,$  if and only if $d (\, \alpha )\, = k - 1.$

Corollary 2 follows from Theorem 1 and Theorem 4 above since $\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \#\{n < 2^t: d(\, \alpha (\, n )\, )\, \geq k \}$  from Theorem 4 $= 2^{t} - 1 - \sum_{i = 0}^{i = k - 1} \#\{n < 2^t: d(\, \alpha (\, n )\, )\, = i \}$ $= 2^{t} - 1 - \sum_{i = 0}^{i = k - 1} \binom{t} {i + 1}$  from Theorem 1 $= 2^{t} - \sum_{i = 0}^{i = k} \binom{t} {i}$ $= \sum_{i = k + 1}^{i = t} \binom{t} {i}$  since $2^{t} = \sum_{i = 0}^{i = t} \binom{t} {i}$ $\Box$

## Proof of Corollary 3.

From Theorem 4, $\#\{n < 2^t: C_{n} \equiv 2^{k-1} \mod {2^k} \} = \#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k - 1 \}$ $= \binom{t} {k}$  from Theorem 1. $\Box$

## Reference

  Liu, S.-C., & Yeh, J. (2010). Catalan numbers modulo $2^k$. J Integer Sequences. Vol 13 (2010) Article 10.5.4