\documentclass[12pt]{article} \usepackage{e-jc} \specs{P20}{20(4)}{2013} \usepackage{amsmath, epsfig, cite, lineno} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{latexsym} \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{property}[thm]{Property} \newtheorem{cor}[thm]{Corollary} \newtheorem{defi}[thm]{Definition} \newtheorem{lem}[thm]{Lemma} \newtheorem{conj}[thm]{Conjecture} \newtheorem{problem}[thm]{Problem} \newtheorem{exam}{Example}[section] \def\pf{\noindent {\it Proof.} } \newcommand{\qed}{{\hfill$\square$}} \numberwithin{equation}{section} \title{\bf Proof of Sun's conjecture on the\\ divisibility of certain binomial sums} \author{Victor J. W. Guo\thanks{Supported by the Fundamental Research Funds for the Central Universities.}\\ \small Department of Mathematics\\[-0.8ex] \small East China Normal University\\[-0.8ex] \small Shanghai 200062, People's Republic of China\\ \small \tt jwguo@math.ecnu.edu.cn,\quad http://math.ecnu.edu.cn/\textasciitilde{jwguo}} \date{\dateline{Jan 28, 2013}{Oct 22, 2013}{Nov 22, 2013}\\ \small Mathematics Subject Classifications: 11B65, 05A10, 11A07} \begin{document} \maketitle \begin{abstract} In this paper, we prove the following result conjectured by Z.-W. Sun: $$ (2n-1){3n\choose n}\left| \sum_{k=0}^{n}{6k\choose 3k}{3k\choose k}{6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k}\right. $$ by showing that the left-hand side divides each summand on the right-hand side. \bigskip\noindent \textbf{Keywords:} congruences, binomial coefficients, super Catalan numbers, Stirling's formula \end{abstract} \section{Introduction} In \cite{Sun}, Z.-W. Sun proved some new series for $1/\pi$ as well as related congruences on sums of binomial coefficients, such as \begin{align*} \sum_{n=0}^\infty\frac{n}{864^n}\sum_{k=0}^{n}{6k\choose 3k}{3k\choose k} {6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k} =\frac{1}{\pi}, \end{align*} and, for any prime $p>3$, \begin{align*} \sum_{n=0}^{p-1}\frac{n}{864^n}\sum_{k=0}^{n}{6k\choose 3k}{3k\choose k} {6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k} \equiv 0\pmod{p^2}. \end{align*} Sun \cite{Sun} also proposed many interesting related conjectures, one of which is \begin{conj}\label{conj:sun} {\rm\cite[Conjecture 4.2]{Sun}} For $n=0,1,2,\ldots,$ define \begin{align*} s_n:=\frac{1}{(2n-1){3n\choose n}} \sum_{k=0}^{n}{6k\choose 3k}{3k\choose k}{6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k}. \end{align*} Then $s_n\in\mathbb{Z}$ for all $n$. Also, \begin{align} \lim_{n\to\infty}\sqrt[n]{s_n}=64. \label{eq:64} \end{align} \end{conj} Sun himself has proved that $s_n\equiv 0\pmod 8$ for $n\geq 1$ and $s_{p-1}\equiv \lfloor(p-1)/6 \rfloor\pmod p$ for any prime $p$. In this paper, we shall prove that Conjecture {\rm\ref{conj:sun}} is true by establishing the following two theorems. \begin{thm}\label{thm:1} For $0\leq k\leq n$, we have \begin{align*} \frac{1}{(2n-1){3n\choose n}} {6k\choose 3k}{3k\choose k}{6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k}\in\mathbb{Z}. \end{align*} \end{thm} Note that, in \cite{Sun2,Sun3}, Sun proved many similar results on the divisibility of binomial coefficients. \begin{thm}\label{thm:2} For $n\geq 1$ and $0\leq k< n/2$, we have \begin{align*} &\hskip -2mm {6k\choose 3k}{3k\choose k}{6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k} \\ &\geq {6k+6\choose 3k+3}{3k+3\choose k+1}{6(n-k-1)\choose 3(n-k-1)}{3(n-k-1)\choose n-k-1}, \end{align*} and hence \begin{align} \frac{2}{2n-1}{6n\choose 3n}\leq s_n \leq \frac{n+1}{2n-1}{6n\choose 3n}. \label{eq:2n-1} \end{align} \end{thm} It is easy to see that \eqref{eq:64} follows from \eqref{eq:2n-1} and Stirling's formula $$ n!\sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n. $$ \section{Proof of Theorem \ref{thm:1}} We need the following two lemmas. \begin{lem} Let $m,n\geq 1$ and $0\leq k\leq n$. Then %(A87 in Sunopenconj) \begin{align*} {mn\choose n}\left|{2mk\choose mk}{mk\choose k}{2m(n-k)\choose m(n-k)}{m(n-k)\choose n-k}.\right. \end{align*} \end{lem} \pf Observe that \begin{align} &\hskip -2mm {2mk\choose mk}{mk\choose k}{2m(n-k)\choose m(n-k)}{m(n-k)\choose n-k}\left/{mn\choose n}\right. \nonumber \\ &=\frac{(2mk)!(2mn-2mk)!}{(mk)!(mn-mk)!(mn)!}{(m-1)n\choose (m-1)k}{n\choose k}. \label{eq:mkmk} \end{align} The proof then follows from the fact that numbers of the form $$ \frac{(2a)!(2b)!}{a!b!(a+b)!}, $$ called the {\it super Catalan numbers}, are integers (see \cite{Bober,Gessel,Warnaar}). \qed \begin{lem}\label{lem:2} Let $0\leq k\leq n$ be integers. Then \begin{align*} (2n-1)\left|\frac{(6k)!(6n-6k)!(2n)!}{(3k)!(3n-3k)!(3n)!(2k)!(2n-2k)!}\right., \end{align*} or equivalently, \begin{align*} \frac{(6k)!(6n-6k)!(2n)!(2n-2)!}{(3k)!(3n-3k)!(3n)!(2k)!(2n-2k)!(2n-1)!}\in\mathbb{Z}. \end{align*} \end{lem} \begin{cor}Let $n\geq 1$. Then $(2n-1)$ divides ${6n\choose 3n}$. \end{cor} For the $p$-adic order of $n!$, there is a known formula \begin{align} {\rm ord}_pn!=\sum_{i=1}^\infty\left\lfloor\frac{n}{p^i}\right\rfloor, \label{eq:ord} \end{align} where $\lfloor x\rfloor$ denotes the greatest integer less than or equal to a real number $x$. In order to prove Lemma \ref{lem:2}, we first establish the following result. \begin{lem}Let $m\geq 2$ and $0\leq k\leq n$ be integers. Then \begin{align} &\hskip -2mm \left\lfloor\frac{6k}{m}\right\rfloor+\left\lfloor\frac{6n-6k}{m}\right\rfloor +\left\lfloor\frac{2n}{m}\right\rfloor+\left\lfloor\frac{2n-2}{m}\right\rfloor \nonumber\\ &\geq \left\lfloor\frac{3k}{m}\right\rfloor+\left\lfloor\frac{3n-3k}{m}\right\rfloor +\left\lfloor\frac{3n}{m}\right\rfloor+\left\lfloor\frac{2k}{m}\right\rfloor +\left\lfloor\frac{2n-2k}{m}\right\rfloor+\left\lfloor\frac{2n-1}{m}\right\rfloor, \label{eq:long} \end{align} unless $m=3$, $n\equiv 2\pmod 3$, and $k\not\equiv 1\pmod 3$. \end{lem} \pf For any real numbers $x$ and $y$, we have (see, for example, \cite[Division 8, Problems 8 and 136]{PS}) \begin{align*} \lfloor 2x\rfloor +\lfloor 2y\rfloor &\geq \lfloor x\rfloor +\lfloor y\rfloor+\lfloor x+y\rfloor, \\ \lfloor x+y\rfloor &\geq \lfloor x\rfloor +\lfloor y\rfloor. \end{align*} It follows that \begin{align*} \left\lfloor\frac{6k}{m}\right\rfloor+\left\lfloor\frac{6n-6k}{m}\right\rfloor +\left\lfloor\frac{2n}{m}\right\rfloor \geq\left\lfloor\frac{3k}{m}\right\rfloor+\left\lfloor\frac{3n-3k}{m}\right\rfloor +\left\lfloor\frac{3n}{m}\right\rfloor+\left\lfloor\frac{2k}{m}\right\rfloor +\left\lfloor\frac{2n-2k}{m}\right\rfloor. \end{align*} Now suppose that \eqref{eq:long} does not hold. Then we must have \begin{align} \left\lfloor\frac{6k}{m}\right\rfloor+\left\lfloor\frac{6n-6k}{m}\right\rfloor &=\left\lfloor\frac{3k}{m}\right\rfloor+\left\lfloor\frac{3n-3k}{m}\right\rfloor +\left\lfloor\frac{3n}{m}\right\rfloor, \label{eq:3.1}\\ \left\lfloor\frac{2n}{m}\right\rfloor &=\left\lfloor\frac{2k}{m}\right\rfloor+\left\lfloor\frac{2n-2k}{m}\right\rfloor, \label{eq:3.2}\\ \left\lfloor\frac{2n-2}{m}\right\rfloor &<\left\lfloor\frac{2n-1}{m}\right\rfloor, \label{eq:3.3} \end{align} and so, by \eqref{eq:3.3}, $m\mid 2n-1$, then by \eqref{eq:3.2}, $m\mid 2k$ or $m\mid 2n-2k$. If $m\mid 2k$, then $m\mid k$ (since $m\mid 2n-1$ means that $m$ is odd), the identity \eqref{eq:3.1} implies that \begin{align} \left\lfloor\frac{6n}{m}\right\rfloor =2\left\lfloor\frac{3n}{m}\right\rfloor. \label{eq:6nm} \end{align} Since $m\mid 2n-1$, the identity \eqref{eq:6nm} can be written as \begin{align} \frac{2n-1}{m}+\left\lfloor\frac{3}{m}\right\rfloor =2\left\lfloor\frac{n+1}{m}\right\rfloor. \label{eq:2n-1m} \end{align} If $m\geq 4$, then the left-hand side of \eqref{eq:2n-1m} equals $(2n-1)/m$, while the right-hand side of \eqref{eq:2n-1m} belongs to $$\left\{\frac{2n+2}{m},\,\frac{2n}{m},\,\frac{2n-2}{m},\ldots\right\},$$ a contradiction! Therefore, $m\leq 3$. Since $m\geq 2$ is odd, we must have $m=3$. Hence, $n\equiv 2\pmod 3$ and $k\equiv 0\pmod 3$. Similarly, if $m\mid 2n-2k$, then we deduce that $m=3$, $n\equiv 2\pmod 3$ and $k\equiv 2\pmod 3$. This proves the lemma. \qed \medskip \noindent{\it Proof of Lemma \ref{lem:2}.} For any prime $p\neq 3$, by \eqref{eq:ord} and \eqref{eq:long}, we have \begin{align} &{\rm ord}_p(6k)!+{\rm ord}_p(6n-6k)!+{\rm ord}_p(2n)!+{\rm ord}_p(2n-2)! \nonumber \\ &\geq {\rm ord}_p(3k)!+{\rm ord}_p(3n-3k)!+{\rm ord}_p(3n)! +{\rm ord}_p(2k)!+{\rm ord}_p(2n-2k)!+{\rm ord}_p(2n-1)!. \label{eq:ineq} \end{align} For $p=3$, since ${\rm ord}_3(3j)!=j+{\rm ord}_3 j!$, the inequality \eqref{eq:ineq} reduces to \begin{align} {\rm ord}_3(2n)!+{\rm ord}_3(2n-2)! \geq {\rm ord}_3 k!+{\rm ord}_3(n-k)!+{\rm ord}_3 n!+{\rm ord}_3(2n-1)!. \label{eq:p3} \end{align} Noticing that $$ \frac{(2n)!(2n-2)!}{k!(n-k)! n!(2n-1)!} =\frac{1}{2n-1}{2n\choose n}{n\choose k} =\left(4{2n-2\choose n-1}-{2n\choose n}\right){n\choose k}\in\mathbb{Z}, $$ the inequality \eqref{eq:p3} holds. Namely, the inequality \eqref{eq:ineq} is true for $p=3$. This completes the proof. \qed \medskip \noindent{\it Proof of Theorem \ref{thm:1}.} By \eqref{eq:mkmk}, one sees that \begin{align*} &\hskip -2mm \frac{1}{(2n-1){3n\choose n}} {6k\choose 3k}{3k\choose k}{6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k} \\ &=\frac{1}{2n-1}\frac{(6k)!(6n-6k)!}{(3k)!(3n-3k)!(3n)!}{2n\choose 2k}{n\choose k}, \end{align*} which is an integer divisible by ${n\choose k}$ in view of Lemma \ref{lem:2}. \qed \section{Proof of Theorem \ref{thm:2}} Let \begin{align*} A_{n,k}={6k\choose 3k}{3k\choose k}{6(n-k)\choose 3(n-k)}{3(n-k)\choose n-k}. \end{align*} Then, for $n\geq 1$ and $0\leq k