Generalized Catalan Numbers: Linear Recursion and Divisibility

B. Sury Stat-Math Unit Indian Statistical Institute 8th Mile Mysore Road Bangalore 560059 India

                      sury@isibang.ac.in

Abstract We prove a linear recursion for the generalized Catalan numbers C_{a}(n) := \frac{1}{(a−1)n+1} \binom{an}{n}

when a ≥ 2. As a consequence, we show p | C_{p}(n) if and only if n ≠ \frac{p^{k}−1}{p−1} for all integers k ≥ 0. This is a generalization of the well-known result that the usual Catalan number C_{2}(n) is odd if and only if n is a Mersenne number 2^{k} − 1. Using certain beautiful results of Kummer and Legendre, we give a second proof of the divisibility result for C_{p}(n). We also give suitably formulated inductive proofs of Kummer’s and Legendre’s formulae which are different from the standard proofs.

1 Introduction

The Catalan numbers \frac{1}{n+1} \binom{2n}{n} arise in diverse situations like counting lattice paths, counting rooted trees etc. In this note, we consider for each natural number a ≥ 2, generalized Catalan numbers (referred to henceforth as GCNs) C_{a}(n) := \frac{1}{(a−1)n+1} \binom{an}{n} and give a linear recursion for them. Note that a = 2 corresponds to the Catalan numbers. The linear recursion seems to be a new observation. We prove the recursion by a suitably formulated induction. This new recursion also leads to a divisibility result for C_{p}(n)’s for a prime p and, thus also, to another proof of the well-known parity assertion for the usual Catalan numbers. The latter asserts C_{2}(n) is odd if and only if n is a Mersenne number; that is, a number of the form 2^{k} − 1 for some positive integer k. Using certain beautiful results of Kummer and Legendre, we give a second proof of the divisibility result for C_{p}(n). We also give suitably formulated inductive proofs of Kummer’s and Legendre’s formulae mentioned below. This is different from the standard proofs [2] and [3]. In this paper, the letter p always denotes a prime number.

2 Linear recursion for GCNs

Lemma 1. For any a ≥ 2, the numbers C_{a}(n) = \frac{1}{(a−1)n+1} \binom{an}{n} can be defined recursively by

C_{a}(0) = 1

C_{a}(n) = ∑_{k=1}^{⌊ \frac{(a−1)n+1}{a} ⌋}(−1)^{k−1}\binom{(a − 1)(n − k) + 1}{k}C_{a}(n − k) , n ≥ 1.

In particular, the usual Catalan numbers C_{2}(n) satisfy the linear recursion

C_{2}(n) = ∑_{k=1}^{⌊ \frac{n+1}{2} ⌋}(−1)^{k−1}\binom{n − k + 1}{k}C_{2}(n − k) , n ≥ 1.

2.1 A definition and remarks

Before proceeding to prove the lemma, we recall a useful definition. One defines the forward difference operator Δ on the set of functions on ℝ as follows. For any function f, the new function Δf is defined by

(Δf)(x) := f(x + 1) − f(x).

Successively, one defines Δ^{k+1}f = Δ(Δ^{k}f) for each k ≥ 1. It is easily proved by induction on n (see, for instance [1, pp. 102–103]) that

(Δ^{n}f)(x) = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}f(x + n − k).

We note that if f is a polynomial of degree d, then Δf is also a polynomial and has degree d − 1. In particular, Δ^{N}f ≡ 0, the zero function, when N > d. Therefore, (Δ^{N}f)(0) = 0.

Proof of 1. The asserted recursion can be rewritten as

∑_{k≥0}(−1)^{k}\binom{n}{k}\binom{a(n − k)}{n − 1} = 0.

One natural way to prove such identities is to try and view the sum as (Δ^{n}f)(0) for a polynomial f of degree < n. In our case, we may take f(x) = ax(ax − 1) ⋯ (ax − n + 2) which is a polynomial of degree < n. Then,

(Δ^{n}f)(x) = ∑_{k≥0}(−1)^{k}\binom{n}{k}f(x + n − k) ≡ 0.

This gives

(Δ^{n}f)(0) = ∑_{k≥0}(−1)^{k}\binom{n}{k}\binom{a(n − k)}{n − 1} = 0.

Thus the asserted recursion follows. ■

Using this lemma, we have the following:

Theorem 2. The prime p | C_{p}(n) if and only if n ≠ \frac{p^{k}−1}{p−1} for all integers k ≥ 0. In particular, C_{2}(n) is odd if and only if n is a Mersenne number 2^{k} − 1.

Proof. We shall apply induction on n. The result holds for n = 1 since C_{p}(1) = 1. Assume n > 1 and that the result holds for all m < n. Let p^{r} ≤ n ≤ p^{r+1} − 1. Let us read the right hand side of

C_{p}(n) = ∑_{k=1}^{⌊ \frac{(p−1)n+1}{p} ⌋}(−1)^{k−1}\binom{(p − 1)(n − k) + 1}{k}C_{p}(n − k)

modulo p. We use the induction hypothesis that for m < n, C_{p}(m) is a multiple of p whenever (p − 1)m + 1 is not a power of p. Modulo p, the terms in the above sum which are non-zero are those for which n − k is of the form \frac{p^{N} −1}{p−1}. But, since p^{r} ≤ n < p^{r+1}, the only non-zero term modulo p is the one corresponding to the index k for which (p − 1)(n − k) = p^{r} − 1 if n ≤ \frac{p^{r+1}−1}{p−1} (respectively, (p − 1)(n − k) = p^{r+1} − 1 if n > \frac{p^{r+1}−1}{p−1}). This term is, to within

sign, \binom{p^{r}}{n− \frac{p^{r}−1}{p−1}}C_{p}(\frac{p^{r}−1}{p−1}) if n ≤ \frac{p^{r+1}−1}{p−1} (respectively, \binom{p^{r+1}}{n− \frac{p^{r+1}−1}{p−1}}C_{p}(\frac{p^{r+1}−1}{p−1}) if n > \frac{p^{r+1}−1}{p−1}). As

the binomial coefficient \binom{p^{r}}{s} is a multiple of p if and only if 0 < s < p^{r}, the above term is a multiple of p if and only if 0 < n− \frac{p^{r}−1}{p−1} < p^{r} if n ≤ \frac{p^{r+1}−1}{p−1} (respectively, 0 < n− \frac{p^{r+1}−1}{p−1} < p^{r+1} if n > \frac{p^{r+1}−1}{p−1}). This is equivalent to p^{r} < (p − 1)n + 1 < p^{r+1} if n ≤ \frac{p^{r+1}−1}{p−1} (respectively, p^{r+1} < (p − 1)n + 1 < p^{r+2} if n > \frac{p^{r+1}−1}{p−1}), which means that (p − 1)n + 1 is not a power of p. The theorem is proved.

3 Another proof of Theorem using Kummer’s algorithm

Kummer proved that, for r ≤ n, the p-adic valuation v_{p}(\binom{n}{r}) is simply the number of carries when one adds r and n − r in base-p. We give another proof of Theorem 2 now using Kummer’s algorithm.

3.1 Another proof of Theorem 2

Write the base-p expansion of (p − 1)n + 1 as

(p − 1)n + 1 = a_{s} ⋯ a_{r+1}0 ⋯ 0

say, where a_{r+1} ≠ 0, s ≥ r + 1 and r ≥ 0. Evidently, v_{p}((p − 1)n + 1) = r. Thus, unless (p − 1)n + 1 is a power of p, the base-p expansion of (p − 1)n will have the same number of digits as above. It is of the form

(p − 1)n = ∗ ⋯ ∗ (a_{r+1} − 1) \underbrace{(p − 1) ⋯ (p − 1)}_{r times}

where a_{r+1} − 1 is between 0 and p − 2. So, the base-p expansion of n itself looks like

n = ∗ ⋯ ∗ 1 ⋯ 1

with r ones at the right end. Also, there are at least r carries coming from the right end while adding the base-p expansions of n and (p − 1)n. Moreover, unless (p − 1)n + 1 is a power of p, consider the first non-zero digit to the left of the string of (p − 1)’s at the end of the expansion of (p − 1)n. If it is denoted by u, and the corresponding digit for n is v, then (p − 1)v ≡ u (mod p); that is, u + v is a non-zero multiple of p (and therefore ≥ p). Thus, there are at least r + 1 carries coming from adding the base-p expansions of n and (p − 1)n unless (p − 1)n + 1 is a power of p. This proves Theorem 2 again. ■

4 Kummer and Legendre’s formulae inductively

Legendre observed that v_{p}(n!) is \frac{n−s(n)}{p−1} where s(n) is the sum of the digits in the basep expansion of n. In [2], Honsberger deduces Kummer’s theorem (used in the previous section) from Legendre’s result and refers to Ribenboim’s book [3] for a proof of the latter. Ribenboim’s proof is by verifying that Legendre’s base-p formula agrees with the standard formula

v_{p} (n!) = ⌊\frac{n}{p}⌋ + ⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + · · · .  (1)

Surprisingly, it is possible to prove Legendre’s formula without recourse to the above formula and that the standard formula follows from such a proof. What is more, Kummer’s formula also follows without having to use Legendre’s result.

4.1 Legendre’s formula:

Lemma 3. Let n = (a_{k} ⋯ a_{1}a_{0})_{p} and s(n) = ∑_{r=0}^{k} a_{r}. Then,

v_{p} (n!) = \frac{n − s(n)}{p − 1}  (2)

Proof. The formulae are evidently valid for n = 1. We shall show that if Legendre’s formula v_{p} (n!) = \frac{n−s(n)}{p−1} holds for n, then it also holds for pn + r for any 0 ≤ r < p. Note that the base-p expansion of pn + r is

a_{k} ⋯ a_{1}a_{0} r.

Let f(m) = \frac{m−s(m)}{p−1}, where m ≥ 1. Evidently,

f(pn + r) = \frac{pn − ∑_{i=0}^{k} a_{i}}{p − 1} = n + f(n).

On the other hand, it follows by induction on n that

v_{p} ((pn + r)!) = n + v_{p}(n!).  (3)

For, if it holds for all n < m, then

v_{p}((pm + r)!) = v_{p}(pm) + v_{p}((pm − p)!)
= 1 + v_{p}(m) + m − 1 + v_{p}((m − 1)!) = m + v_{p}(m!).

Since it is evident that f(m) = 0 = v_{p}(m!) for all m < p, it follows that f(n) = v_{p}(n!) for all n. This proves Legendre’s formula.

Note also that the formula

v_{p}(n!) = ⌊\frac{n}{p}⌋ + ⌊\frac{n}{p^{2}} ⌋ + ⌊\frac{n}{p^{3}} ⌋ + ⋯

follows inductively using Legendre’s result.

4.2 Kummer’s algorithm:

Lemma 4. For r, s ≥ 0, let g(r, s) be the number of carries when the base-p expansions of r and s are added. Then, for k ≤ n,

v_{p} (\binom{n}{k}) = g(k, n − k).  (4)

Proof. Once again, this is clear if n < p, as both sides are then zero. We shall show that if the formula holds for all integers 0 ≤ j ≤ n (and every 0 ≤ k ≤ j), it does so for pn + r for 0 ≤ r < p (and any k ≤ pn + r). This would prove the result for all natural numbers.

Consider a binomial coefficient of the form \binom{pn+r}{pm+a}, where 0 ≤ a < p.

First, suppose a ≤ r.

Write m = b_{k} ⋯ b_{0} and n−m = c_{k} ⋯ c_{0} in base-p. Then the base-p expansions of pm+a and p(n − m) + (r − a) are, respectively,

pm + a = b_{k} ⋯ b_{0} a
p(n − m) + (r − a) = c_{k} ⋯ c_{0} r − a.

Evidently, the corresponding number of carries is

g(pm + a, p(n − m) + (r − a)) = g(m, n − m).

By the induction hypothesis, g(m, n − m) = v_{p}(\binom{n}{m}). Now v_{p} (\binom{pn + r}{pm + a}) is equal to

v_{p}((pn + r)!) − v_{p}((pm + a)!) − v_{p}((p(n − m) + r − a)!)
= n + v_{p}(n!) − m − v_{p}(m!) − (n − m) − v_{p}((n − m)!) = v_{p} (\binom{n}{m}) .

Thus, the result is true when a ≤ r.

Now suppose that r < a. Then v_{p} (\binom{pn + r}{pm + a}) is equal to

v_{p}((pn + r)!) − v_{p}((pm + a)!) − v_{p}((p(n − m − 1) + (p + r − a))!)
= n + v_{p}(n!) − m − v_{p}(m!) − (n − m − 1) − v_{p}((n − m − 1)!)
= 1 + v_{p}(n) + v_{p}((n − 1)!) − v_{p}(m!) − v_{p}((n − m − 1)!)
= 1 + v_{p}(n) + v_{p} (\binom{n − 1}{m}) .

We need to show that

g(pm + a, p(n − m − 1) + (p + r − a)) = 1 + v_{p}(n) + g(m, n − m − 1).  (5)

Note that m < n. Write n = a_{k} ⋯ a_{0}, m = b_{k} ⋯ b_{0} and n − m − 1 = c_{k} ⋯ c_{0} in base-p. If v_{p}(n) = d, then a_{i} = 0 for i < d and a_{d} ≠ 0. In base-p, we have

n = a_{k} ⋯ a_{d} 0 ⋯ 0

and, therefore,

n − 1 = a_{k} ⋯ a_{d+1}(a_{d} − 1) (p − 1) ⋯ (p − 1).

Now, the addition m + (n − m − 1) = n − 1 gives b_{i} + c_{i} = p − 1 for i < d (since they must be < 2p − 1). Moreover, b_{d} + c_{d} = a_{d} − 1 or p + a_{d} − 1.

Note the base-p expansions

pm + a = b_{k} ⋯ b_{0} a
p(n − m − 1) + (p + r − a) = c_{k} ⋯ c_{0} (p + r − a).

We add these using that fact that there is a carry-over in the beginning and that 1+b_{i}+c_{i} = p for i < d. Since there is a carry-over at the first step as well as at the next d steps, we have

pn + r = ∗ ∗ ⋯ a_{d} \underbrace{0 ⋯ 0}_{d times} r

and

g(pm + a, p(n − m − 1) + (p + r − a)) = 1 + d + g(m, n − m − 1).

This proves Kummer’s assertion also.

5 Acknowledgment

It is a real pleasure to thank the referee who read through the paper carefully and made a number of constructive suggestions and a few corrections as well.

References

[1] M. Aigner, Combinatorial Theory, Springer-Verlag, 1997.

[2] R. Honsberger, In Polya’s Footsteps, Miscellaneous Problems and Essays, The Dolciani Mathematical Expositions, No. 19, Mathematical Association of America, 1997.

[3] P.Ribenboim, The New Book of Prime Number Records, Springer-Verlag, 1996.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 11B83. Keywords: generalized Catalan numbers, linear recursion, divisibility.

(Concerned with sequence \underline{A000108}.)

Received May 21 2009; revised version received October 28 2009. Published in Journal of Integer Sequences, November 4 2009.

Return to Journal of Integer Sequences home page.