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

## Summary

The Catalan numbers are defined by

This note will use results obtained by Liu and Yeh in [1] to obtain a formula for the number of which are divisible by where

Firstly, as in [1], let the p-adic order of a positive integer n be defined by

and the cofactor of n with respect to be defined by

In addition the function is defined by

For a number p, we write the base p expansion of a number n as

where and

Then the function 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 . Then

**Theorem 1**:

**Corollary 2**:

**Corollary 3**:

## Proofs.

**Proof of Theorem 1:**

Let . Then

for some arbitrary . Writing in base 2 we have

where there are s 0’s at the end and is arbitrary. So,

where there are s 1’s at the end and is arbitrary. It can be seen that

Since and the possible base 2 representations of n are

with

with

.

.

.

with and 1’s at the end.

Therefore, counting each of these possibilities and using the fact that gives

## Proof of Corollary 2.

The following result appears in [1].

**Theorem 4 (Corollary 4.3 of [1]): **In general, we have In particular, if and only if , and if and only if

Corollary 2 follows from Theorem 1 and Theorem 4 above since

from Theorem 4

from Theorem 1

since

## Proof of Corollary 3.

From Theorem 4,

from Theorem 1.

## Reference

[1] Liu, S.-C., & Yeh, J. (2010). Catalan numbers modulo . *J Integer Sequences*. **Vol 13** (2010) Article 10.5.4