\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