\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
Generalized Catalan Numbers: \\
\vskip .1in
Linear Recursion and Divisibility
}
\vskip 1cm
\large
B. Sury\\
Stat-Math Unit \\
Indian Statistical Institute\\
8th Mile Mysore Road \\
Bangalore 560059 \\
India\\
\href{mailto:sury@isibang.ac.in}{\tt sury@isibang.ac.in}\\
\end{center}
\vskip .2 in
\begin{abstract}
We prove a {\it linear} recursion for the generalized Catalan
numbers $C_a(n) := \frac{1}{(a-1)n+1} {an \choose n}$ when $a \geq
2$.
As a consequence, we show $p \, | \, C_p(n)$ if
and only if $n \neq \frac{p^k-1}{p-1}$ for all integers $k \geq 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.
\end{abstract}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}
\section{Introduction}
The Catalan numbers $\frac{1}{n+1} {2n \choose n}$ arise
in diverse situations like counting lattice paths, counting rooted
trees etc. In this note, we consider for each natural number $a
\geq 2$, generalized Catalan numbers (referred to henceforth as
GCNs) $C_a(n) := \frac{1}{(a-1)n+1} {an \choose n}$ and give a
{\it 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 \cite{H} and \cite{R}. In this
paper, the letter $p$ always denotes a prime number.
\section{Linear recursion for GCNs}
\begin{lemma}\label{linrec}
{\it For any $a \geq 2$, the numbers $C_a(n)
= \frac{1}{(a-1)n+1} {an \choose n}$ can be defined recursively by
$$C_a(0) = 1$$
$$C_a(n) = \sum_{k=1}^{\lfloor \frac{(a-1)n+1}{a} \rfloor} (-1)^{k-1} {(a-1)(n-k)+1 \choose k}
C_a(n-k)~,n \geq 1.$$ In particular, the usual Catalan numbers
$C_2(n)$ satisfy the linear recursion}
$$C_2(n) = \sum_{k=1}^{\lfloor \frac{n+1}{2} \rfloor} (-1)^{k-1} {n-k+1 \choose k}
C_2(n-k)~,n \geq 1.$$
\end{lemma}
\subsection{A definition and remarks}
Before proceeding to prove the lemma, we recall a useful definition.
One defines the {\it forward difference operator} $\Delta$ on the
set of functions on $\mathbb{R}$ as follows. For any function $f$,
the new function $\Delta f$ is defined by
$$(\Delta f)(x) := f(x+1)-f(x).$$
Successively, one defines $\Delta^{k+1}f = \Delta (\Delta^k f)$ for
each $k \geq 1$. It is easily proved by induction on $n$ (see, for
instance \cite[pp.\ 102--103]{A}) that
$$(\Delta^n f)(x) = \sum_{k=0}^n (-1)^k {n \choose k} f(x+n-k).$$
We note that if $f$ is a polynomial of degree $d$, then $\Delta f$
is also a polynomial and has degree $d-1$. In particular, $\Delta^N
f \equiv 0$, the zero function, when $N > d$. Therefore, $(\Delta^N
f)(0) = 0$.
\bigskip
\noindent {\it Proof of \ref{linrec}}. The asserted recursion can be
rewritten as
$$\sum_{k \geq 0} (-1)^k {n \choose k}{a(n-k) \choose n-1} = 0.$$
One natural way to prove such identities is to try and view the sum
as $(\Delta^n f)(0)$ for a polynomial $f$ of degree $< n$. In our
case, we may take $f(x) = ax(ax-1) \cdots (ax-n+2)$ which is a
polynomial of degree $< n$. Then,
$$(\Delta^n f)(x) = \sum_{k \geq 0} (-1)^k {n \choose k} f(x+n-k) \equiv 0.$$
This gives
$$(\Delta^n f)(0) = \sum_{k \geq 0} (-1)^k {n \choose k}{a(n-k) \choose n-1} = 0.$$
Thus the asserted recursion follows. $\blacksquare$
Using this lemma, we have the following:\\
\begin{theorem}
\label{divis} The prime {\it $p\, | \, C_p(n)$ if and only if $n \neq
\frac{p^k-1}{p-1}$ for all integers $k \geq 0$. In particular,
$C_2(n)$ is odd if and only if $n$ is a Mersenne number $2^k-1$.}
\end{theorem}
\begin{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
\frac{p^{r+1}-1}{p-1}$). This term is, to within sign, ${p^r \choose
n- \frac{p^r-1}{p-1}} C_p(\frac{p^r-1}{p-1})$ if $n \leq
\frac{p^{r+1}-1}{p-1}$ (respectively, ${p^{r+1} \choose 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 ${p^r \choose
s}$ is a multiple of $p$ if and only if $0~~ \frac{p^{r+1}-1}{p-1}$).
This is equivalent to $p^r < (p-1)n + 1 < p^{r+1}$ if $n \leq
\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.
\end{proof}
\section{Another proof of Theorem using Kummer's algorithm}
Kummer proved that, for $r \leq n$, the $p$-adic valuation
$v_p({n \choose 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.
\subsection{Another proof of Theorem \ref{divis}}
Write the base-$p$ expansion of $(p-1)n+1$ as
$$(p-1)n+1 = a_s \cdots a_{r+1} 0 \cdots 0$$
say, where $a_{r+1} \neq 0, s \geq r+1$ and $r \geq 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 = \ast \cdots \ast (a_{r+1}-1) \underbrace{(p-1) \cdots (p-1)}_{r~{\rm times}}$$
where $a_{r+1}-1$ is between $0$ and $p-2$. So, the base-$p$
expansion of $n$ itself looks like
$$n = \ast \cdots \ast 1 \cdots 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 \equiv u$ (mod $p$); that is, $u+v$ is a non-zero multiple
of $p$ (and therefore $\geq 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
\ref{divis} again. $\blacksquare$
\section{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 base-$p$ expansion of
$n$. In \cite{H}, Honsberger deduces Kummer's theorem (used in the
previous section) from Legendre's result and refers to Ribenboim's
book \cite{R} for a proof of the latter. Ribenboim's proof is by
verifying that Legendre's base-$p$ formula agrees with the standard
formula
%
\begin{equation}
v_p \left ( n! \right ) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor
\frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots.
\label{eq:kummer}
\end{equation}
%
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.
\subsection{Legendre's formula:}
\begin{lemma}
\label{legendre} {\it Let $n = (a_k \cdots a_1 a_0)_p$ and $s(n) =
\sum_{r=0}^k a_r$. Then,}
%
\begin{equation}
v_p \left (n! \right ) = \frac{n - s(n)}{p-1}
\end{equation}
%
\end{lemma}
\begin{proof}
The formulae are evidently valid for $n=1$. We shall show that if
Legendre's formula $v_p \left (n! \right ) = \frac{n - s(n)}{p-1}$
holds for $n$, then it also holds for $pn+r$ for any $0
\leq r < p$. Note that the base-$p$ expansion of $pn+r$ is
$$
a_k \cdots a_1 a_0~ r.
$$
Let $f(m) = \frac{m-s(m)}{p-1}$, where $m \geq 1$. Evidently,
$$
f(pn+r) = \frac{pn - \sum_{i=0}^ka_i}{p-1}=n+f(n).
$$
On the other hand, it follows by induction on $n$ that
%
\begin{equation}
v_p \left ((pn+r)! \right ) = n + v_p(n!). \label{eq:eq1}
\end{equation}
%
For, if it holds for all $n~~