\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf On Certain Sums Divisible by the  \\
Central Binomial Coefficient\\
\vskip 1cm}
\large
Jovan Miki\'{c}\\
J.U. S\v{S}C ``Jovan Cviji\'{c}''\\
74480 Modri\v{c}a\\
Republic of Srpska\\
\href{mailto:jnmikic@gmail.com}{\tt jnmikic@gmail.com} \\
\end{center}

\vskip .2in

\begin{abstract}
We prove that some sums, which arise as generalizations of known binomial coefficient identities, are divisible by the central binomial coefficient. A new method is used. In particular, we show that  an alternating sum concerning the product of a  power of a binomial coefficient with two Catalan numbers is  always divisible by the central binomial coefficient.
\end{abstract}

\section{Introduction}\label{sec:1}
Let $n$ be a non-negative integer and let $m$ be a positive integer. Let $C_n=\frac{1}{n+1}\binom{2n}{n}$ denote the $n$th Catalan number.

In this paper, we consider the following four binomial sums:
\begin{align}
P(n,m)&=\sum_{k=0}^{n}(-1)^k{\binom{n}{k}}^m\binom{2k}{k}\binom{2n-2k}{n-k}\text{,}\label{eq:1}\\
Q(n,m)&=\sum_{k=0}^{n}(-1)^k{\binom{n}{k}}^m\binom{2k}{k}\binom{2n-2k}{n-k}(n-k)\text{,}\label{eq:2}\\
R(n,m)&=\sum_{k=0}^{n}(-1)^k{\binom{n}{k}}^m C_k\,\binom{2n-2k}{n-k}\text{,}\label{eq:3}\\
T(n,m)&=\sum_{k=0}^{n}(-1)^k{\binom{n}{k}}^m C_k\, C_{n-k}\text{.}\label{eq:4}
\end{align}

For $m=1$, all four sums (\ref{eq:1}), (\ref{eq:2}), (\ref{eq:3}), and (\ref{eq:4}) reduce to  interesting combinatorial identities.
For example, it is well-known that \cite[Example 3.6.2, p.\ 45]{MPWZ}
\begin{equation}
\sum_{k=0}^{2n}(-1)^k{\binom{2n}{k}}\binom{2k}{k}\binom{4n-2k}{2n-k}={\binom{2n}{n}}^2\text{.}\label{eq:5}
\end{equation}
By Eq.~(\ref{eq:5}), it follows that $P(2n,1)={\binom{2n}{n}}^2$.

Recently, the  following two binomial coefficient identities involving
the Catalan numbers were discovered \cite{JM3}:
\begin{align}
\sum_{k=0}^{n}(-1)^k{\binom{n}{k}} C_k\,\binom{2n-2k}{n-k}&={\binom{n}{\lfloor\frac{n}{2}\rfloor}}^2\text{,}\label{eq:6}\\
\sum_{k=0}^{2n}(-1)^k{\binom{2n}{k}} C_k\, C_{2n-k}&=C_n\binom{2n}{n}\text{.}\label{eq:7}
\end{align}

In this paper we  present,  among other results,  two generalizations of Eqns. (\ref{eq:6}) and (\ref{eq:7}). See Remark \ref{rem:1}.
By Eqns.~(\ref{eq:6}) and (\ref{eq:7}), it follows that $R(n,1)={\binom{n}{\lfloor\frac{n}{2}\rfloor}}^2$ and $T(2n,1)=C_n\binom{2n}{n}$.
Our main results are as follows:
\begin{theorem}\label{t:1}
The sum $P(2n,m)$ is divisible by $\binom{2n}{n}$ for all non-negative integers $n$ and for all positive integers $m$.
\end{theorem}

\begin{theorem}\label{t:2}
The sum $Q(2n-1,m)$ is divisible by $2(2n-1)\binom{2(n-1)}{n-1}$ for all positive integers $n$ and $m$.
\end{theorem}

\begin{theorem}\label{t:3}
The sum $R(2n,m)$ is divisible by $(n+1)\binom{2n}{n}$ for all non-negative integers $n$ and for all positive integers $m$.
\end{theorem}

\begin{corollary}\label{cor:1}
The sum $T(2n,m)$ is divisible by $\binom{2n}{n}$ for all non-negative integers $n$ and for all positive integers $m$.
\end{corollary}

\begin{theorem}\label{t:4}
The sum $R(2n-1,m)$ is divisible by $\binom{2n-1}{n}$ for all positive integers $n$ and $m$.
\end{theorem}
For proving our main results, we use a method we call the ``method
of $D$ sums''.
\begin{definition}\label{def:1}
Let $n$, $j$, and $t$ be non-negative integers such that $j\leq \lfloor \frac{n}{2}\rfloor$, and let $m$ be a positive integer.
Let $S(n,m)=\sum_{k=0}^{n}\binom{n}{k}^m F(n,k)$,
where $F(n,k)$ is an integer-valued function that depends only on $n$ and $k$. Then the $D$ sums for $S(n,m)$ are
\begin{equation}
D_S(n,j,t)=\sum_{l=0}^{n-2j}\binom{n-j}{l}\binom{n-j}{j+l}\binom{n}{j+l}^tF(n,j+l)\mbox{.}\label{eq:8}
\end{equation}
\end{definition}
First, note that all four sums (\ref{eq:1}), (\ref{eq:2}), (\ref{eq:3}), and (\ref{eq:4}) are instances of $S(n,m)$.
For $m\geq 2$, by Eq.~(\ref{eq:8}), it follows that
\begin{equation}\label{eq:9}
S(n,m)=D_S(n,0,m-2)\text{.}
\end{equation}
Furthermore, $D$ sums satisfy the following two recurrence relations \cite[Thm.\ 2, Thm.\ 3, p.\ 2]{JM1}:
\begin{align}
 D_S(n,j,t+1)&=\sum_{u=0}^{\lfloor \frac{n-2j}{2} \rfloor} \binom{n}{j+u}\binom{n-j}{u}D_S(n,j+u,t)\text{,}\label{eq:10}\\
 D_S(n,j,0)&=\sum_{u=0}^{\lfloor \frac{n-2j}{2} \rfloor}\binom{n-j}{j+u}\binom{n-2j-u}{u}\sum_{v=0}^{n-2j-2u}\binom{n-2j-2u}{v}F(n,j+u+v)\label{eq:11}\mbox{.}
\end{align}

The idea is to calculate the $D$ sums for (\ref{eq:1}), (\ref{eq:2}), (\ref{eq:3}), and (\ref{eq:4}) by using Relations  \ref{eq:10} and \ref{eq:11}. We show that their $D$ sums have interesting divisibility properties.
For example, we show that $D_P(2n,j,0)$ is divisible by $\binom{2n}{n}$ for all non-negative integers $j$ and $n$ such that $j\leq n$. Surprisingly, this result is sufficient to prove Theorem \ref{t:1} for $m \geq 2$. Namely, then by Relation \ref{eq:10} and induction, it can be shown that all $D_P(2n,j,t)$ are divisible by $\binom{2n}{n}$. By Relation \ref{eq:9}, it follows that $P(2n,m)$ is divisible by $\binom{2n}{n}$ for all $m \geq 2$. See \cite[Section 5]{JM1}.

To calculate the sum $D_P(2n,j,0)$, we derive the following binomial coefficient identity:
\begin{equation}\label{eq:12}
\sum_{k=t}^{2n-t}(-1)^k\binom{2n-2t}{k-t}\binom{2k}{k}\binom{4n-2k}{2n-k}=(-1)^t\frac{\binom{2n}{n}\binom{2t}{t}\binom{2(n-t)}{n-t}}{\binom{2n-t}{t}}\text{,}
\end{equation}
where $n$ and $t$ are non-negative integers such that $t\leq n $.
For $t=0$, Eq.~(\ref{eq:12}) becomes  Eq.~(\ref{eq:5}). Therefore, we can see  Eq.~(\ref{eq:12}) as a  generalization of Eq.~(\ref{eq:5}).

\section{Motivation}\label{sec:2}

The first application of $D$ sums  \cite[Section 8]{JM1} was for proving Calkin's result \cite[Thm.\ 1]{NC}. In $ 1998$, Calkin  proved that the alternating binomial sum $\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^m $ is divisible by $\binom{2n}{n} $ for all non-negative integers $n$ and all positive integers $m$.

 In 2007, Guo, Jouhet, and Zeng proved, among other things, two generalizations of Calkin's result \cite[Thm.\ 1.2, Thm.\ 1.3, p.\ 2]{VG1}. As a special case of \cite[Thm.\ 1.2,  p.\ 2]{VG1}, they gave a direct generalization of Calkin's result  \cite[Thm.\ 4.1, p.\ 8]{VG1}.
Moreover, this generalization implies that the sum  $D_{S_3}$  \cite[Section 8]{JM1} is divisible by $\binom{2n}{n}$ and $\binom{2n-j}{n}$ for $t\geq 1$. Take $m=t+2$, $n_1=n_2=\cdots=n_{t+1}=n$, and $n_{t+2}=n-j$ in \cite[Thm.\ 4.1, p.\ 8]{VG1}. 

 Since the sum  in \cite[Thm.\ 4.1, p.\ 8]{VG1} is  not instance of $S(n,m)$ from our Definition \ref{def:1}, it is clear that $D$ sums cannot prove this direct generalization by  Guo, Jouhet, and Zeng.  Therefore, method of $D$ sums proves the smallest generalization of Calkin's result.

In this paper, we show how the method of $D$ sums works on harder sums, such as our four sums (\ref{eq:1}), (\ref{eq:2}), (\ref{eq:3}), and (\ref{eq:4}).  
 Note that our main results are not consequences of \cite[Thm.\ 1.2, Thm.\ 1.3, Thm.\ 4.1.]{VG1}.

Let $S$, $F$, and $D_S$ be sums according to Definition \ref{def:1}. The main obstacle is to calculate the sum $D_S(n,j,0)$.
In order to make Relation \ref{eq:11} more readable, we introduce the following definition.
\begin{definition}\label{def:3}
Let $n$ and $t$ be non-negative integers such that $t\leq \lfloor \frac{n}{2}\rfloor$.
Then $S_t(n)$ denotes
\begin{equation}\label{eq:13}
\sum_{k=t}^{n-t}\binom{n-2t}{k-t}F(n,k)\text{.}
\end{equation}
\end{definition}
Obviously, for $t=0$, it follows that $S_0(n)=S(n,1)$. Therefore, a sum $S_t(n)$ can be viewed as a generalization of a sum $S(n,1)$.
Furthermore, by substitution $k=u+j+v$, the inner sum of the right-side of (\ref{eq:11}) becomes
\begin{equation}\label{eq:14}
\sum_{v=0}^{n-2j-2u}\binom{n-2j-2u}{v}F(n,j+u+v)=S_{j+u}(n)\text{.}
\end{equation}
It is readily verified \cite[Eq.~(1.4), p.~5]{Koshy} that $\binom{n-j}{j+u}\binom{n-2j-u}{u}=\binom{n-j}{u}\binom{n-j-u}{j+u}$. By using this fact and  Eq.~(\ref{eq:14}), Relation \ref{eq:11} becomes
\begin{equation}\label{eq:15}
 D_S(n,j,0)=\sum_{u=0}^{\lfloor \frac{n-2j}{2}\rfloor}\binom{n-j}{u}\binom{n-j-u}{j+u}S_{j+u}(n)\text{.}
\end{equation}
From now on, for calculating $D_S(n,j,0)$ sum, we use Eq.~(\ref{eq:15}) instead of Relation \ref{eq:11}.

To find a sum $D_S(n,j,0)$, we first need to find the appropriate $S_t(n)$.
For example, let us consider our first sum $P(2n,m)$. We want to find $D_P(2n,j,0)$ sum, where $j$ is a non-negative integer such that $j\leq n$. Let $t$ be a non-negative integer such that $t\leq n$.  Then what is $P_t(2n)$?
By Definitions (\ref{def:1}) and (\ref{def:3}), $P_t(2n)$ is equal to the left side of  Eq.~(\ref{eq:12}).
If  Eq.~(\ref{eq:12}) holds, then it follows that
\[P_t(2n)=(-1)^t\frac{\binom{2n}{n}\binom{2t}{t}\binom{2(n-t)}{n-t}}{\binom{2n-t}{t}}\text{.}\]
Note that formula above is our Lemma \ref{l:3}. Therefore, Lemma \ref{l:3} is a restatement of  Eq.~(\ref{eq:12}).
Also we want to find the
sums $Q_t(2n-1)$, $R_t(2n)$, $R_t(2n-1)$, and $T_t(2n)$.

This paper consists of two main parts. 
In the first part, we derive formulas for $P_t(2n)$, $Q_t(2n-1)$, $R_t(2n)$,  $R_t(2n-1)$ and $T_t(2n)$ sums. We use recurrences and telescoping. Interestingly, $Q_t(2n)$, $R_t(n)$, and $T_t(n)$ are auxiliary sums for the sum  $P_t(2n)$. See \cite{JM2}. Therefore, if we find the first sum $P_t(2n)$, then the others follow by using recurrence relations. Note that we use telescoping only for the first sum $P_t(2n)$.

In the second part, we apply the method of $D$ sums by using Relations \ref{eq:10}, \ref{eq:15}, and \ref{eq:9}.

The rest of the paper is structured as follows:
In Section \ref{sec:3}, we begin with some preliminary results for Eqs.~(\ref{eq:1}), (\ref{eq:2}), (\ref{eq:3}), and (\ref{eq:4}). Also, we give some preliminary results for the sums $P_t(n)$, $Q_t(n)$, $R_t(n)$ and $T_t(n)$.
In Section \ref{sec:4}, we present formulas for the sums $P_t(2n)$, $Q_t(2n-1)$, $R_t(2n)$, $R_t(2n-1)$, and $T_t(2n)$.
Also we give recurrence relations between these sums.
In Section \ref{sec:5}, we prove most of the results from Section \ref{sec:4}.
In Section \ref{sec:6}, we start with the proof of Theorem (\ref{t:1}) by using the method of $D$ sums and Lemma \ref{l:3}. Then we prove Theorem \ref{t:3} and Corollary \ref{cor:1}. For brevity and clarity, we omit proofs of Theorems \ref{t:2} and \ref{t:4}. Namely, the proofs of Theorems \ref{t:2} and \ref{t:4} are similar to proofs of Theorems \ref{t:1} and \ref{t:3}, respectively.

\section{Some preliminary results}\label{sec:3}

We start with some preliminary results for Eqs.~(\ref{eq:1}), (\ref{eq:2}), (\ref{eq:3}), and (\ref{eq:4}) sums.

\begin{lemma}\label{l:1}
Let $n$ be a non-negative integer, and let $m$ be a positive integer.
Then we have
\begin{align}
P(2n+1,m)&=0\text{,}\label{eq:16}\\
Q(2n,m)&=nP(2n,m)\text{,}\label{eq:17}\\
T(2n+1,m)&=0\text{,}\label{eq:18}\\
T(2n,m)&=\frac{1}{n+1}R(2n,m)\text{.}\label{eq:19}
\end{align}
\end{lemma}
Furthermore, we give similar results for the
sums $P_t(n)$, $Q_t(n)$, $R_t(n)$ and $T_t(n)$.

\begin{lemma}\label{l:2}
Let $n$ be a non-negative integer, and let $t$ be a non-negative integer such that $t \leq \lfloor \frac{n}{2}\rfloor$. 
Then we have
\begin{align}
P_t(2n+1)&=0\text{,}\label{eq:20}\\
Q_t(2n)&=nP_t(2n)\text{,}\label{eq:21}\\
T_t(2n+1)&=0\text{,}\label{eq:22}\\
T_t(2n)&=\frac{1}{n+1}R_t(2n)\text{.}\label{eq:23}
\end{align}
\end{lemma}
We prove only Lemma \ref{l:1}.
The proof of Lemma \ref{l:2} is similar to the proof of Lemma \ref{l:1}. Therefore, the proof of Lemma \ref{l:2} is omitted.

\subsection{Proof of Lemma \ref{l:1}}
\begin{proof}
Changing $k$ to $n-k$ in  Eq.~(\ref{eq:1}), it follows  that $P(n,m)=(-1)^nP(n,m)$.
If $n$ is odd, then it must be $P(n,m)=-P(n,m)$. This is equivalent to $P(n,m)=0$ for an odd $n$. The Eq.~(\ref{eq:16}) follows, as desired.

Similarly, changing $k$ to $n-k$ in  Eq.~(\ref{eq:4}), it follows  that $T(n,m)=(-1)^nT(n,m)$.
If $n$ is odd, then it must be $T(n,m)=-T(n,m)$ which is equivalent to $T(n,m)=0$. This proves  Eq.~(\ref{eq:18}).

By Eq.~(\ref{eq:2}), we know that\[Q(2n,m)=\sum_{k=0}^{2n}(-1)^k{\binom{2n}{k}}^m\binom{2k}{k}\binom{4n-2k}{2n-k}(2n-k)\text{.}\]
Changing $k$ to $2n-k$, the last equation above becomes 
\[Q(2n,m)=\sum_{k=0}^{2n}(-1)^k{\binom{2n}{k}}^m\binom{2k}{k}\binom{4n-2k}{2n-k}k\text{.}\]
By adding these two equations,  Eq.~(\ref{eq:17}) follows.

Let us now prove  Eq.~(\ref{eq:19}).
By  Eq.~(\ref{eq:3}), we know that \[R(2n,m)=\sum_{k=0}^{2n}(-1)^k{\binom{2n}{k}}^m C_k\binom{4n-2k}{2n-k}\text{.}\]
Changing $k$ to $2n-k$, the last equation above becomes 
\[R(2n,m)=\sum_{k=0}^{2n}(-1)^k{\binom{2n}{k}}^m C_{2n-k}\binom{2k}{k}\text{.}\]
By adding the last two equations above and using  the fact \cite[Eq.~(18), p.\ 8]{JM3}\\ $C_k\binom{4n-2k}{2n-k}+C_{2n-k}\binom{2k}{k}=2(n+1)C_k\,C_{2n-k}$ ,  Eq.~(\ref{eq:19}) follows.
\end{proof}

\section{Main lemmas, propositions and corollaries}\label{sec:4}

Let $n$ and $t$ be  non-negative integers such that $t\leq \lfloor \frac{n}{2}\rfloor$.
By Eqns.~(\ref{eq:1}),(\ref{eq:2}), (\ref{eq:3}), (\ref{eq:4}), and Definition \ref{def:3}, we know that
\begin{align}
P_t(n)&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}\binom{2k}{k}\binom{2n-2k}{n-k}\text{,}\label{eq:24}\\
Q_t(n)&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(n-k)\binom{2k}{k}\binom{2n-2k}{n-k}\text{,}\label{eq:25}\\
R_t(n)&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}C_k\binom{2n-2k}{n-k}\text{,}\label{eq:26}\\
T_t(n)&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}C_kC_{n-k}\text{.}\label{eq:27}
\end{align} 
We present the following five main lemmas for calculating
the sums $P_t(2n)$, $Q_t(2n-1)$, $R_t(2n)$, $R_t(2n-1)$, and $T_t(2n)$.
\begin{lemma}\label{l:3}
Let $n$ and $t$ be non-negative integers such that $t\leq n$.
Then
\begin{equation*}
P_t(2n)=(-1)^t\frac{\binom{2n}{n}\binom{2t}{t}\binom{2n-2t}{n-t}}{\binom{2n-t}{t}}\text{.} 
\end{equation*}
\end{lemma}

\begin{lemma}\label{l:4}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t\leq n-1$.
Then
\begin{equation*}
Q_t(2n-1)=(-1)^t\frac{2(2n-1)\binom{2(n-1)}{n-1}\binom{2t}{t}\binom{2(n-1-t)}{n-1-t}}{\binom{2n-1-t}{t}}\text{.}
\end{equation*}
\end{lemma}
\begin{lemma}\label{l:5}
Let $n$ and $t$ be non-negative integers such that $t\leq n$.
Then
\begin{equation*}
R_t(2n)=(-1)^t\frac{\binom{2n}{n}\binom{2t}{t}\binom{2n-2t}{n-t}}{\binom{2n+1-t}{t}}\text{.}
\end{equation*}
\end{lemma}

\begin{lemma}\label{l:6}
Let $n$ and $t$ be non-negative integers such that $t\leq n$.
Then
\begin{equation*}
T_t(2n)=(-1)^t\frac{C_n\binom{2t}{t}\binom{2n-2t}{n-t}}{\binom{2n+1-t}{t}}\text{.}
\end{equation*}
\end{lemma}

\begin{lemma}\label{l:7}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t\leq n-1$.
Then
\begin{equation*}
R_t(2n-1)=(-1)^t\frac{\binom{2n-1}{n}\binom{2t}{t}\binom{2n-2t-1}{n-t}}{\binom{2n-t}{t}}\text{.}
\end{equation*}
\end{lemma}

Sums $Q_t(n)$, $R_t(n)$, and $T_t(n)$ are auxiliary sums for the sum  $P_t(n)$.
We give recurrences between these sums.
We start with two propositions.
\begin{proposition}\label{p:1}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t<\frac{n}{2}$. Then
\begin{equation*}
Q_t(n)=4(n-2t)P_t(n-1)+2(n-2t)(-1)^n R_t(n-1)+tP_t(n)\text{.}
\end{equation*}
\end{proposition}

\begin{proposition}\label{p:2}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t<\frac{n}{2}$. Then
\begin{equation*}
(n-t+1)R_t(n)=P_t(n)+4(n-2t)R_t(n-1)-2(n-2t)T_t(n-1)\text{.}
\end{equation*}
\end{proposition}

Proposition \ref{p:1} has the following two consequences.
\begin{corollary}\label{cor:2}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t\leq n-1$. Then
\begin{equation*}
R_t(2n-1)=\frac{1}{4}P_t(2n)\text{.}
\end{equation*}
\end{corollary}

\begin{corollary}\label{cor:3}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t\leq n-1$. Then
\begin{equation*}
Q_t(2n-1)=2(2n-1-2t)(2P_t(2n-2)-R_t(2n-2))\text{.}
\end{equation*}
\end{corollary}

Proposition \ref{p:2} also has two consequences.
\begin{corollary}\label{cor:4}
Let $n$ and $t$ be non-negative integers such that $t\leq n$. Then
\begin{equation*}
R_t(2n)=\frac{2n-2t+1}{2n-t+1}P_t(2n)\text{.}
\end{equation*}
\end{corollary}

\begin{corollary}\label{cor:5}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t\leq n-1$. Then
\begin{equation*}
R_t(2n-1)=\frac{2(2n-2t-1)(2n-1)}{n(2n-t)}R_t(2n-2)\text{.}
\end{equation*}
\end{corollary}

Furthermore, by Corollaries \ref{cor:3} and \ref{cor:4}, it follows that
\begin{corollary}\label{cor:6}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t\leq n-1$. Then
\begin{equation*}
Q_t(2n-1)=\frac{2(2n-1)(2n-1-2t)}{2n-1-t}P_t(2n-2)\text{.}
\end{equation*}
\end{corollary}
Finally, by Corollaries \ref{cor:2}, \ref{cor:4}, and \ref{cor:5}, we give the following recurrence for $P_t(2n)$.
\begin{corollary}\label{cor:7}
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t< n$. Then
\begin{equation*}
P_t(2n)=\frac{8(2n-1)(2n-2t-1)^2}{n(2n-t)(2n-t-1)}P_t(2n-2)\text{.}
\end{equation*}
\end{corollary}
We prove Lemma \ref{l:3} by telescoping the recurrence from Corollary \ref{cor:7}.  
Once we obtain Lemma \ref{l:3}, proofs of  Lemmas \ref{l:4}, \ref{l:5}, and \ref{l:7} follow from Corollaries \ref{cor:6}, \ref{cor:4}, and \ref{cor:2},
respectively.
Note that Lemma \ref{l:6} follows from  Eq.~(\ref{eq:23}) and Lemma \ref{l:5}.
Therefore, proofs of Lemmas \ref{l:4}, \ref{l:5}, \ref{l:6}, and \ref{l:7} are omitted.
Since we do not use the sum $ Q_t(2n-1)$ for calculating the sum $P_t(2n)$, proofs of Corollaries \ref{cor:3} and \ref{cor:6} are omitted too. The other corollaries are proved.

\section{Proofs of main lemmas, propositions and corollaries}\label{sec:5}

First, we prove  Propositions \ref{p:1} and \ref{p:2}.
To do this, we use two known binomial identities.
The first is \cite[Eq.~(1.2), p.\ 5]{Koshy}
\begin{equation}
(n-k)\binom{n}{k}=n\binom{n-1}{k}\text{,}\label{eq:28}
\end{equation}
where $k$ is an arbitrary integer.
The second identity is 
\begin{equation}
\binom{2k}{k}=4\binom{2(k-1)}{k-1}-2C_{k-1}\text{,}\label{eq:29}
\end{equation}
where $k$ is a positive integer.
Eq.~(\ref{eq:29}) follows from the recurrence relation for the central binomial coefficients \cite[p.\ 26]{Koshy} and the definition of  the Catalan numbers.

\subsection{Proof of Proposition \ref{p:1}}

\begin{proof}
By Eqns.~(\ref{eq:24}) and (\ref{eq:25}), we have 
\begin{align}
Q_t(n)&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}((n-k-t)+t)\binom{2k}{k}\binom{2n-2k}{n-k}\notag\\
&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(n-k-t)\binom{2k}{k}\binom{2n-2k}{n-k}+tP_n(t)\text{.}\label{eq:30}
\end{align}
Note that the last term of the sum on the right-side of  Eq.~(\ref{eq:30}) equals zero. By using  Eq.~(\ref{eq:28}), it follows that $\binom{n-2t}{k-t}(n-k-t)=(n-2t)\binom{n-1-2t}{k-t}$. Combining  these two facts, it follows that
\begin{gather}
\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(n-k-t)\binom{2k}{k}\binom{2n-2k}{n-k}\notag\\=(n-2t)\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}\binom{2k}{k}\binom{2n-2k}{n-k}\text{.}\label{eq:31}
\end{gather}

Since $k\leq n-1-t$ in Eq.~(\ref{eq:31}), it follows that $k<n$.
By using  Eq.~(\ref{eq:29}), we know that
\begin{equation}
\binom{2(n-k)}{n-k}=4\binom{2(n-1-k)}{n-1-k}-2C_{n-1-k}.  \label{eq:32}
\end{equation}

By using  Eq.~(\ref{eq:32}), we have
\begin{gather}
\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}\binom{2k}{k}\binom{2n-2k}{n-k}\label{eq:33}\\
=4\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}\binom{2k}{k}\binom{2(n-1-k)}{n-1-k}\label{eq:34}\\
-2\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}\binom{2k}{k}C_{n-1-k}.  \label{eq:35}
\end{gather}

By Eq.~(\ref{eq:24}),  Eq.~(\ref{eq:34}) equals $4P_t(n-1)$. Changing $k$ to $n-1-k$ and by using
Eq.~(\ref{eq:26}),  Eq.~(\ref{eq:35}) becomes $-2(-1)^{n-1}R_t(n-1)$.
Therefore, combining these facts,  Eq.~(\ref{eq:33}) becomes
\begin{equation}\label{eq:36}
4P_t(n-1)+2(-1)^nR_t(n-1).
\end{equation}

By using Eqns.~(\ref{eq:33}) and (\ref{eq:36}),  Eq.~(\ref{eq:31}) becomes
\begin{gather}
\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(n-k-t)\binom{2k}{k}\binom{2n-2k}{n-k}\notag\\=
4(n-2t)P_t(n-1)+2(-1)^n(n-2t)R_t(n-1).  \label{eq:37}
\end{gather}

Finally, Eqns.~(\ref{eq:30}) and (\ref{eq:37}) complete the proof of Proposition \ref{p:1}.

\end{proof}

\subsection{Proof of Proposition \ref{p:2}}
\begin{proof}
By  Eq.~(\ref{eq:26}), we have
\begin{align}
R_t(n)&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}C_k\binom{2n-2k}{n-k}\notag\\
&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}\frac{(1+k)-k}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k}\notag\\
&=\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(1-\frac{k}{k+1})\binom{2k}{k}\binom{2n-2k}{n-k}.  \label{eq:38}
\end{align}

By  Eq.~(\ref{eq:24}),  Eq.~(\ref{eq:38}) becomes
\begin{align}
R_t(n)&=P_t(n)+\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(-k)\,C_k\binom{2n-2k}{n-k}\notag\\
&=P_t(n)+\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}((n-t-k)+(t-n))\,C_k\binom{2n-2k}{n-k}.   \label{eq:39}
\end{align}
By  Eq.~(\ref{eq:26}),  Eq.~(\ref{eq:39}) becomes
\begin{equation}
R_t(n)=P_t(n)+\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(n-t-k)\,C_k\binom{2n-2k}{n-k}+(t-n)R_t(n).  \label{eq:40}
\end{equation}
The Eq.~(\ref{eq:40}) is equivalent to the following equation
\begin{equation}
(n-t+1)R_t(n)=P_t(n)+\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(n-t-k)\,C_k\binom{2n-2k}{n-k}.   \label{eq:41}
\end{equation}

Similarly as in  Eq.~(\ref{eq:31}), we have
\begin{gather}
\sum_{k=t}^{n-t}(-1)^k\binom{n-2t}{k-t}(n-t-k)\,C_k\binom{2n-2k}{n-k}\label{eq:42} \\=(n-2t)\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}\,C_k\binom{2n-2k}{n-k}.  \label{eq:43}
\end{gather}
By using  Eq.~(\ref{eq:32}), it follows that
\begin{gather}
\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}\,C_k\binom{2n-2k}{n-k}\label{eq:44}\\
=4\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}\,C_k\binom{2(n-1-k)}{n-1-k}\label{eq:45}\\
-2\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}C_k\,C_{n-1-k}.  \label{eq:46}
\end{gather}

By  Eq.~(\ref{eq:26}),  Eq.~(\ref{eq:45}) is equal to $4R_t(n-1)$. By  Eq.~(\ref{eq:27}),  Eq.~(\ref{eq:46}) is equal to $-2T_t(n-1)$. Therefore, by Eqns.~(\ref{eq:44}), (\ref{eq:45}), and (\ref{eq:46}), it follows that
\begin{equation}
\sum_{k=t}^{n-1-t}(-1)^k\binom{n-1-2t}{k-t}\,C_k\binom{2n-2k}{n-k}=4R_t(n-1)-2T_t(n-1).   \label{eq:47}
\end{equation}

By Eqns.~(\ref{eq:47}), (\ref{eq:42}), and (\ref{eq:43}),  Eq.~(\ref{eq:41}) becomes 
\begin{align*}
(n-t+1)R_t(n)&=P_t(n)+(n-2t)(4R_t(n-1)-2T_t(n-1))\\
&=P_t(n)+4(n-2t)R_t(n-1)-2(n-2t)T_t(n-1).  
\end{align*}
This completes the proof of Proposition \ref{p:2}.

\end{proof}

\subsection{Proofs of Corollaries \ref{cor:2}, \ref{cor:4}, and \ref{cor:5}}

We begin with the proof of Corollary \ref{cor:2}.
Corollary \ref{cor:2} is a consequence of Proposition \ref{p:1} and Lemma \ref{l:2}.
\begin{proof}
Let $n$ be a positive integer.
By setting $n:=2n$ in Proposition \ref{p:1}, we obtain that
\begin{equation}
Q_t(2n)=4(2n-2t)P_t(2n-1)+2(2n-2t)(-1)^{2n} R_t(2n-1)+tP_t(2n), \label{eq:48}
\end{equation}
where $0\leq t<\frac{2n}{2}=n$.

By Eqns.~(\ref{eq:20}) and (\ref{eq:21}) from Lemma \ref{l:2},  Eq.~(\ref{eq:48}) is equivalent to
\begin{align}
n P_t(2n)&=2(2n-2t)R_t(2n-1)+tP_t(2n),   \notag\\
4(n-t)R_t(2n-1)&=(n-t)P_t(2n).   \label{eq:49}
\end{align}
Since $t<n$, we can divide both sides of Eq.~(\ref{eq:49}) by $4(n-t)$.
Therefore,  Eq.~(\ref{eq:49}) becomes
\[R_t(2n-1)=\frac{1}{4}P_t(2n).  \]
This completes the proof of  Corollary \ref{cor:2}.
\end{proof}

Corollary \ref{cor:4} is a consequence of Proposition \ref{p:2}, Corollary \ref{cor:2}, and Lemma \ref{l:2}.
We now prove Corollary \ref{cor:4}.
\begin{proof}
Let $n$ be a positive integer.
By setting $n:=2n$ in Proposition \ref{p:2}, we obtain 
\begin{equation}
(2n-t+1)R_t(2n)=P_t(2n)+4(2n-2t)R_t(2n-1)-2(2n-2t)T_t(2n-1), \label{eq:50}
\end{equation}
where $0\leq t<\frac{2n}{2}=n$.

By  Eq.~(\ref{eq:22}) from the Lemma \ref{l:2}, the integer $T_t(2n-1)$ vanishes. Then  Eq.~(\ref{eq:50}) is equivalent to
\begin{equation}
(2n-t+1)R_t(2n)=P_t(2n)+4(2n-2t)R_t(2n-1).  \label{eq:51}
\end{equation}

By  Corollary \ref{cor:2},  Eq.~(\ref{eq:51}) becomes as follows:
\begin{align*}
(2n-t+1)R_t(2n)&=P_t(2n)+4(2n-2t)\frac{1}{4}P_t(2n),  \\
(2n-t+1)R_t(2n)&=(2n-2t+1)P_t(2n).  
\end{align*}
Since $t<n$, we can divide both sides of the last equation above by $2n-t+1$.
It follows that
\begin{equation}
R_t(2n)=\frac{2n-2t+1}{2n-t+1}P_t(2n).  \label{eq:52} 
\end{equation}

Therefore, we proved Corollary \ref{cor:4} for all positive integers $n$ and for all non-negative integers $t$ such that $t<n$.

By  Eq.~(\ref{eq:24}), we know that
\begin{equation}
P_n(2n)=(-1)^n\binom{2n}{n}^2,\label{eq:53}
\end{equation}
where $n$ is a non-negative integer.
By  Eq.~(\ref{eq:26}), it follows that
\begin{equation}
R_n(2n)=(-1)^nC_n\binom{2n}{n}, \label{eq:54}
\end{equation}
where $n$ is a non-negative integer.
Therefore, by using Eqns.~(\ref{eq:53})  and (\ref{eq:54}), it follows that  Eq.~(\ref{eq:52}) holds for $t=n$.
Also, this proves the case $n=0$.
Therefore, Corollary \ref{cor:4} follows, as desired.
\end{proof}

Finally, let us prove Corollary \ref{cor:5}.
Corollary \ref{cor:4} is a consequence of Proposition \ref{p:2} and Lemma \ref{l:2}.
\begin{proof}
Let $n$ be a positive integer.
By setting $n:=2n-1$ in Proposition \ref{p:2}, we obtain that
\begin{equation}
(2n-t)R_t(2n-1)=P_t(2n-1)+4(2n-1-2t)R_t(2n-2)-2(2n-1-2t)T_t(2n-2)\text{;}\label{eq:55}
\end{equation}
where $0\leq t<\frac{2n-1}{2}$.

By  Eq.~(\ref{eq:20}) from Lemma \ref{l:2}, the integer $P_t(2n-1)$ vanishes in  Eq.~(\ref{eq:55}).
By  Eq.~(\ref{eq:23}) from Lemma \ref{l:2}, the integer $T_t(2n-2)$ is equal to $\frac{1}{n}R_t(2n-2)$. Therefore,  Eq.~(\ref{eq:54}) becomes as follows:
\begin{align}
(2n-t)R_t(2n-1)&=4(2n-1-2t)R_t(2n-2)-2(2n-1-2t)\frac{1}{n}R_t(2n-2) \notag\\
(2n-t)R_t(2n-1)&=2(2n-1-2t)R_t(2n-2)(2-\frac{1}{n}) \notag\\
(2n-t)R_t(2n-1)&=2(2n-1-2t)R_t(2n-2)\,\frac{2n-1}{n}.  \label{eq:56}
\end{align}
Since $t\leq n-1$, we can divide the both sides of  Eq.~(\ref{eq:56}) by $2n-t$.
The Eq.~(\ref{eq:56}) becomes
\[R_t(2n-1)=\frac{2(2n-1)(2n-1-2t)}{n(2n-t)}R_t(2n-2).  \]
This completes the proof of  Corollary \ref{cor:5}.
\end{proof}


\subsection{Proof of Corollary \ref{cor:7}}

Corollary \ref{cor:7} is a consequence of Corollaries \ref{cor:2}, \ref{cor:4}, and \ref{cor:5}.

\begin{proof}
Let $n$ be a positive integer. 

By setting $n:=n-1$ in Corollary \ref{cor:4}, we obtain
\begin{equation}
R_t(2n-2)=\frac{2n-2t-1}{2n-t-1}P_t(2n-2), \label{eq:57}
\end{equation}
where $t$ is a non-negative integer such that $t\leq n-1$.
\end{proof}

By using Corollary \ref{cor:2} and  Eq.~(\ref{eq:57}), Corollary \ref{cor:5} becomes as follows:
\begin{align}
\frac{1}{4}P_t(2n)&=\frac{2(2n-1)(2n-1-2t)}{n(2n-t)}\cdot\frac{2n-2t-1}{2n-t-1}P_t(2n-2), \notag\\
P_t(2n)&=\frac{8(2n-1)}{n}\cdot\frac{(2n-2t-1)^2}{(2n-t)(2n-1-t)}P_t(2n-2) . \label{eq:58}
\end{align}
This completes the proof of Corollary \ref{cor:7}.

\subsection{Proof of Lemma \ref{l:3}}

\begin{proof}
By  Eq.~(\ref{eq:53}), we know that
\begin{equation}\label{eq:59}
P_t(2t)=(-1)^t\binom{2t}{t}^2,
\end{equation}
where $t$ is a non-negative integer.
Let $n$ be a positive integer, and let $t$ be a non-negative integer such that $t<n$.
We telescope  Eq.~(\ref{eq:58}) from  Corollary \ref{cor:7}.

We have 
\begin{align*}
P_t(2n)&=\frac{8(2n-1)}{n}\cdot\frac{(2n-2t-1)^2}{(2n-t)(2n-1-t)}P_t(2n-2)\\
&=8^{n-t}\frac{(2n-1)(2n-3)\cdots(2t+1)}{n(n-1)\cdots(t+1)}\cdot\frac{\bigl((2n-2t-1)!!\bigr)^2}{(2n-t)\cdots(t+1)}P_t(2t) .
\end{align*}

By using  Eq.~(\ref{eq:59}), the last equation above becomes
\begin{equation}\label{eq:60}
P_t(2n)=8^{n-t}\frac{(2n-1)(2n-3)\cdots(2t+1)}{n(n-1)\cdots(t+1)}\cdot \frac{\bigl((2n-2t-1)!!\bigr)^2}{(2n-t)\cdots(t+1)}(-1)^t\frac{((2t)!)^2}{(t!)^4} .
\end{equation}

Then  Eq.~(\ref{eq:60}) becomes as follows:
\begin{align*}
P_t(2n)&=(-1)^t 8^{n-t}\frac{(2n-1)(2n-3)\cdots(2t+1)}{n!\,(2n-t)!}\cdot \frac{\bigl((2n-2t-1)!!\bigr)^2}{(t!)^2}((2t)!)^2, \\
&=(-1)^t 2^{n-t}\frac{(2n-1)(2n-3)\cdots(2t+1)}{n!\,(2n-t)!}\cdot\frac{\bigl( 2^{n-t}(2n-2t-1)!!\bigr)^2((2t)!)^2}{(t!)^2}\\
&=(-1)^t 2^{n-t}\frac{(2n-1)(2n-3)\cdots(2t+1)}{n!\,(2n-t)!}\cdot\frac{\bigl( 2^{n-t}(n-t)!\,(2n-2t-1)!!\bigr)^2((2t)!)^2}{((n-t)!)^2 \cdot (t!)^2}\\
&=(-1)^t 2^{n-t}\frac{(2n-1)(2n-3)\cdots(2t+1)}{n!\,(2n-t)!}\cdot\frac{\bigl( (2n-2t)!!\,(2n-2t-1)!!\bigr)^2((2t)!)^2}{((n-t)!)^2\cdot (t!)^2}\\
&=(-1)^t 2^{n-t}\frac{(2n-1)(2n-3)\cdots(2t+1)}{n!\,(2n-t)!}\cdot\frac{((2n-2t)!)^2((2t)!)^2}{((n-t)!)^2\cdot (t!)^2}\\
&=(-1)^t 2^{n-t}\frac{n(n-1)\cdots(t+1)}{n(n-1)\cdots(t+1)}\cdot\frac{(2n-1)(2n-3)\cdots(2t+1)\bigl( (2n-2t)!\bigr)^2((2t)!)^2}{n!\cdot (2n-t)!\cdot (t!)^2 \cdot ((n-t)!)^2}\\
&=(-1)^t \frac{2n(2n-2)\cdots(2t+2)}{n(n-1)\cdots(t+1)}\cdot\frac{(2n-1)(2n-3)\cdots(2t+1)\bigl( (2n-2t)!\bigr)^2((2t)!)^2}{n!\cdot (2n-t)!\cdot (t!)^2\cdot ((n-t)!)^2}\\
&=(-1)^t \frac{2n(2n-1)\cdots(2t+1)\cdot(2t)!}{n(n-1)\cdots(t+1)\cdot t!}\cdot\frac{\bigl( (2n-2t)!\bigr)^2(2t)!}{n!\cdot (2n-t)!\cdot t!\cdot ((n-t)!)^2} .
\end{align*}

\begin{align*}
P_t(2n)&=(-1)^t \frac{(2n)!}{n!}\cdot\frac{\bigl( (2n-2t)!\bigr)^2(2t)!}{n!\cdot (2n-t)!\cdot t! \cdot((n-t)!)^2}\\
&=(-1)^t \binom{2n}{n}\cdot \frac{(2n-2t)!}{((n-t)!)^2}\cdot \frac{(2n-2t)!(2t)!}{(2n-t)!\cdot t!}\\
&=(-1)^t \binom{2n}{n}\cdot \binom{2n-2t}{n-t}\cdot \frac{(2n-2t)!\cdot t!}{(2n-t)!} \cdot \frac{(2t)!}{(t!)^2} \\
&=(-1)^t \binom{2n}{n}\cdot \binom{2n-2t}{n-t}\cdot \frac{1}{\binom{2n-t}{t}} \cdot \binom{2t}{t} .
\end{align*}
Therefore, it follows that
\begin{equation}\label{eq:61}
P_t(2n)=(-1)^t \frac{ \binom{2n}{n}\binom{2t}{t}\binom{2n-2t}{n-t}}{\binom{2n-t}{t}},
\end{equation}
where $n>t$.
Eqns.~(\ref{eq:59}) and (\ref{eq:61}) complete the proof of Lemma  \ref{l:3}.
\end{proof}

Now  Eq.~(\ref{eq:12}) directly follows from Lemma \ref{l:3}.
\begin{remark}\label{rem:1}
Note that Lemma \ref{l:6} generalizes  Eq.~(\ref{eq:7}). By setting $t=0$ in Lemma \ref{l:6}, we obtain  Eq.~(\ref{eq:7}). Similarly, Lemma \ref{l:5} generalizes  Eq.~(\ref{eq:6}) for even $n$, and Lemma \ref{l:7} generalizes  Eq.~(\ref{eq:6}) for odd $n$.
\end{remark}

\section{Proofs of main results}\label{sec:6}

We begin with the proof of Theorem \ref{t:1}.

\subsection{Proof of Theorem \ref{t:1}}

\begin{proof}
By Eq.~(\ref{eq:5}), we know that Theorem \ref{t:1} is true for $m=1$.
Therefore, let us suppose $m\geq 2$.

Let $n$ be a fixed non-negative integer. Let $j$ be a non-negative integer such that $j\leq n$.
We prove that $D_P(2n,j,0)$ is divisible by $\binom{2n}{n}$ for all $j$ such that $j\leq n$.

By Relation \ref{eq:15}, it follows that 
\begin{align}
 D_P(2n,j,0)&=\sum_{u=0}^{\lfloor \frac{2n-2j}{2}\rfloor}\binom{2n-j}{u}\binom{2n-j-u}{j+u}P_{j+u}(2n)\notag\\
 &=\sum_{u=0}^{n-j}\binom{2n-j}{u}\binom{2n-j-u}{j+u}P_{j+u}(2n) . \label{eq:62}
\end{align}

Obviously, $0 \leq j+u\leq n$ in  Eq.~(\ref{eq:62}). By setting $t:=j+u$ in Lemma \ref{l:3}, it follows that
\begin{equation}\label{eq:63}
P_{j+u}(2n)=(-1)^{j+u} \frac{ \binom{2n}{n}\binom{2(j+u)}{j+u}\binom{2n-2j-2u}{n-j-u}}{\binom{2n-j-u}{j+u}} .
\end{equation}

By using Eq.~(\ref{eq:63}),  Eq.~(\ref{eq:62}) becomes as follows
\begin{align}
D_P(2n,j,0)&=\sum_{u=0}^{n-j}\binom{2n-j}{u}\binom{2n-j-u}{j+u}(-1)^{j+u} \frac{ \binom{2n}{n}\binom{2(j+u)}{j+u}\binom{2n-2j-2u}{n-j-u}}{\binom{2n-j-u}{j+u}}\notag\\
&=(-1)^j\binom{2n}{n}\sum_{u=0}^{n-j}(-1)^u\binom{2n-j}{u}\binom{2(j+u)}{j+u}\binom{2n-2j-2u}{n-j-u}.  \label{eq:64}
\end{align}
By  Eq.~(\ref{eq:64}), it follows that $D_P(2n,j,0)$ is divisible by $\binom{2n}{n}$ for all $j$ such that $j\leq n$.

We assert that $D_P(2n,j,t)$ is divisible by $\binom{2n}{n}$ for all non-negative integers $j$ and $t$ such that $j\leq n$. 

We assume that $n$ is a fixed non-negative integer. We use induction on $t$.
For $t=0$, we proved  that $D_P(2n,j,t)$ is divisible by $\binom{2n}{n}$ for all non-negative $j$ such that $j \leq n $.
Let $s$ be a non-negative integer.
Let us assume that $D_P(2n,j,t)$ is divisible by $ \binom{2n}{n}$ for $t=s$ and for all non-negative integers $j$ such that $j \leq n$. 
	What happens with $D_P(2n,j,s+1)$ ?	
	By Relation \ref{eq:10}, it follows that
	\begin{equation}
	D_P(2n,j,s+1)=\sum_{u=0}^{n-j} \binom{2n}{j+u}\binom{2n-j}{u}D_P(2n,j+u,s) . \label{eq:65}
	\end{equation}
	 Obviously, $0 \leq j+u \leq n$ in  Eq.~(\ref{eq:65}). By the induction hypothesis, $D_P(2n,j+u,s)$ is divisible by $\binom{2n}{n} $. By  Eq.~(\ref{eq:65}), it follows that $ D_P(2n,j,s+1)$ is divisible by $\binom{2n}{n} $.
	 
	This proves the induction step.
	Therefore,  $D_P(2n,j,t)$ is divisible by $\binom{2n}{n}$ for all non-negative  integers $j$ and $t$ such that $j \leq n $.
		
By Relation \ref{eq:9}, it follows that
\begin{equation}\label{eq:66}
P(2n,m)=D_P(2n,0,m-2),
\end{equation}
where $m$ is a positive integer such that $m \geq 2$.

Since $D_P(2n,0,m-2)$ is divisible by $\binom{2n}{n}$, by  Eq.~(\ref{eq:66}), it follows that
$P(2n,m)$ is divisible by $\binom{2n}{n}$ for all $m \geq 2$.
This completes the proof of Theorem \ref{t:1}.
\end{proof}

\begin{remark}\label{rem:2}
By setting $j=0$ in  Eq.~(\ref{eq:64}) and by using  Eq.~(\ref{eq:9}), it follows that
\begin{equation}\label{eq:67}
P(2n,2)=\binom{2n}{n}\sum_{u=0}^{n}(-1)^u\binom{2n}{u}\binom{2u}{u}\binom{2n-2u}{n-u} .
\end{equation}
\end{remark}

\begin{remark}\label{rem:3}
Let us suppose that $n$ is a positive integer. Then, at least one of binomial coefficients $\binom{2(j+u)}{j+u}$ and $\binom{2n-2j-2u}{n-j-u}$ must be even in  Eq.~(\ref{eq:64}). By Eq.~(\ref{eq:64}), we obtain $D_P(2n,j,0)$ is divisible by $2\binom{2n}{n}$ for all positive integers $n$ and all non-negative integers $j$ such that $j\leq n$. By the method of $D$ sums and  Eq.~(\ref{eq:5}), we can conclude that $P(2n,m)$ is divisible by $2\binom{2n}{n}$ for all positive integers $m$ and $n$.
\end{remark}

\begin{remark}\label{rem:4}
The proof of Theorem \ref{t:2} is similar to the proof of Theorem \ref{t:1}. We use Relation \ref{eq:15} and Lemma \ref{l:4}. If $n$ is a positive integer greater than $1$, it follows that $Q(2n-1,m)$ is divisible by $4(2n-1)\binom{2(n-1)}{n-1}$ for all positive integers $m$.
\end{remark}

\subsection{Proof of Theorem \ref{t:3}}

By  Eqns.~(\ref{eq:3}) and (\ref{eq:6}), we know that $R(2n,1)=\binom{2n}{n}^2$. By definition of the Catalan numbers, it follows that $n+1$ divides $\binom{2n}{n}$. Therefore, Theorem \ref{t:3} is true for $m=1$.
Let us suppose that $m$ is a positive integer greater than $2$.
Let $n$ be a fixed non-negative integer. Let $j$ be a non-negative integer such that $j\leq n$.
We use the method of $D$ sums, Lemma \ref{l:5}, and one additional result. 
Namely, let $a$ and $b$ be positive integers. It is known \cite [Corollary 1.5]{VG} that
\begin{equation}\label{eq:68}
\frac{a}{2(a+b)}\binom{2a}{a}\binom{2b}{b}\text{ is always an integer.}
\end{equation}
In other words, the integer $a\binom{2a}{a}\binom{2b}{b}$ is divisible by $2(a+b)$. Gessel gave a combinatorial interpretation of  Eq.~(\ref{eq:68}). See \cite[Section 7]{IG}.

 Our proof of  Theorem \ref{t:3} consists of two parts.

In the first part, we show Theorem \ref{t:3} is true for $m=2$ by using Eqns.~(\ref{eq:9}), (\ref{eq:15}), (\ref{eq:68}),  and Lemma \ref{l:5}.

In the second part, we show that $D_R(2n,j,1)$ is divisible by $(n+1)\binom{2n}{n}$ for all non-negative integers $j$ such that $j\leq n$. By Relation \ref{eq:10},  Eq.~(\ref{eq:68}), and induction, it follows that $D_P(2n,j,t)$ is divisible by $(n+1)\binom{2n}{n}$ for all positive integers $t$ and for all non-negative integers $j$ such that $j\leq n$. By Relation \ref{eq:9}, we obtain  Theorem \ref{t:3} is true for all $m\geq 3$.

\bigskip

\noindent \textbf{The first part}:
\begin{proof}
By Relation \ref{eq:15}, it follows that 
\begin{equation}
 D_R(2n,j,0)=\sum_{u=0}^{n-j}\binom{2n-j}{u}\binom{2n-j-u}{j+u}R_{j+u}(2n) .  \label{eq:69}
\end{equation}

Obviously, $0 \leq j+u\leq n$ in Eq.~(\ref{eq:69}). By setting $t:=j+u$ in Lemma \ref{l:5}, it follows that
\begin{equation}\label{eq:70}
R_{j+u}(2n)=(-1)^{j+u} \frac{ \binom{2n}{n}\binom{2(j+u)}{j+u}\binom{2n-2j-2u}{n-j-u}}{\binom{2n+1-j-u}{j+u}} . 
\end{equation}

By using Eq.~(\ref{eq:70}),  Eq.~(\ref{eq:69}) becomes as follows:
\begin{align}
D_R(2n,j,0)&=\sum_{u=0}^{n-j}\binom{2n-j}{u}\binom{2n-j-u}{j+u}(-1)^{j+u} \frac{ \binom{2n}{n}\binom{2(j+u)}{j+u}\binom{2n-2j-2u}{n-j-u}}{\binom{2n+1-j-u}{j+u}}\notag\\
&=(-1)^j\binom{2n}{n}\sum_{u=0}^{n-j}(-1)^u\frac{\binom{2n-j}{u}\binom{2n-j-u}{j+u}}{\binom{2n+1-j-u}{j+u}}\binom{2(j+u)}{j+u}\binom{2n-2j-2u}{n-j-u} . \label{eq:71}
\end{align}

By  Eq.~(\ref{eq:28}), it follows that
\begin{equation}\label{eq:72}
\frac{\binom{2n-j-u}{j+u}}{\binom{2n+1-j-u}{j+u}}=\frac{2n+1-2j-2u}{2n+1-j-u} . 
\end{equation}

By  Eqns.~(\ref{eq:72}) and (\ref{eq:28}), we have 
\begin{equation}
\binom{2n-j}{u}\frac{\binom{2n-j-u}{j+u}}{\binom{2n+1-j-u}{j+u}}=\frac{2n+1-2j-2u}{2n+1-j}\binom{2n+1-j}{u} . \label{eq:73}
\end{equation}

By using  Eq.~(\ref{eq:72}),  Eq.~(\ref{eq:71}) becomes
\begin{gather}
D_R(2n,j,0)=\notag\\
\frac{(-1)^j\binom{2n}{n}}{2n+1-j}\sum_{u=0}^{n-j}(-1)^u(2n+1-2j-2u)\binom{2n+1-j}{u}\binom{2(j+u)}{j+u}\binom{2n-2j-2u}{n-j-u} .  \label{eq:74}
\end{gather}
Let $M(n,j)$ denote the sum 
\begin{equation}
\sum_{u=0}^{n-j}(-1)^u(2n+1-2j-2u)\binom{2n+1-j}{u}\binom{2(j+u)}{j+u}\binom{2n-2j-2u}{n-j-u}.  \label{eq:75}
\end{equation}
Then  Eq.~(\ref{eq:74}) can be written as
\begin{equation}
D_R(2n,j,0)=\frac{(-1)^j\binom{2n}{n}}{2n+1-j}M(n,j).  \label{eq:76}
\end{equation}

Let us prove that $M(n,j)$ is divisible by $n+1$ for all non-negative integers $j$ such that $j\leq n$.
It is readily verified that 
\begin{equation}
(2n+1-2j-2u)\binom{2n-2j-2u}{n-j-u}=\frac{n+1-j-u}{2}\binom{2(n+1-j-u)}{n+1-j-u}.  \label{eq:77}
\end{equation}
By using  Eq.~(\ref{eq:77}),  Eq.~(\ref{eq:75}) becomes
\begin{equation}
M(n,j)=\sum_{u=0}^{n-j}(-1)^u\binom{2n+1-j}{u}\frac{n+1-j-u}{2}\binom{2(j+u)}{j+u}\binom{2(n+1-j-u)}{n+1-j-u}.  \label{eq:78}
\end{equation}
By  Eq.~(\ref{eq:68}), it follows that $\frac{n+1-j-u}{2}\binom{2(n+1-j-u)}{n+1-j-u}\binom{2(j+u)}{j+u}$ is divisible by $n+1$.
By Eqns.~(\ref{eq:68}) and (\ref{eq:78}), the sum $M(n,j)$ is divisible by $n+1$.
In particular, the sum $M(n,0)$ is divisible by $n+1$.

Let us prove that the sum $M(n,0)$ is divisible by $2n+1$.
By  Eq.~(\ref{eq:75}), we obtain
\begin{equation}
M(n,0)=\sum_{u=0}^{n}(-1)^u(2n+1-2u)\binom{2n+1}{u}\binom{2u}{u}\binom{2n-2u}{n-u}.  \label{eq:79}
\end{equation}
We have 
\begin{align}
(2n+1-2u)\binom{2n+1}{u}&=(2n+1)\binom{2n+1}{u}-2u\binom{2n+1}{u}\notag\\
&=(2n+1)\binom{2n+1}{u}-2(2n+1)\binom{2n}{u-1}\notag\\
&=(2n+1)(\binom{2n+1}{u}-2\binom{2n}{u-1}).  \label{eq:80}
\end{align}
Note that we used the identity $k\binom{n}{k}=n\binom{n-1}{k-1}$. See \cite[Eq.~(1.1), p.\ 5]{Koshy}.

By  Eq.~(\ref{eq:80}), it follows that $(2n+1-2u)\binom{2n+1}{u}$ is divisible by $2n+1$. By  Eq.~(\ref{eq:79}), it follows that $M(n,0)$ is divisible by $2n+1$.  Note that numbers $n+1$ and $2n+1$ are relatively prime.
Therefore, we conclude that $M(n,0)$  is divisible by $(n+1)(2n+1)$.

By Relation \ref{eq:9}, we know that
\begin{equation}
R(2n,2)=D_R(2n,0,0) . \label{eq:81}
\end{equation}
By setting $j=0$ in  Eq.~(\ref{eq:76}), it follows that
\begin{equation}
D_R(2n,0,0)=\frac{\binom{2n}{n}}{2n+1}M(n,0).  \label{eq:82}
\end{equation}
We know that $\frac{M(n,0)}{2n+1}$ is an integer divisible by $n+1$.

Therefore, by using Eqns.~(\ref{eq:81}) and (\ref{eq:82}), we conclude
$R(2n,2)$ is divisible by $(n+1)\binom{2n}{n}$.
This proves the first part of Theorem \ref{t:3}.
\end{proof}

We note that the
integers $\binom{2n}{n}$ and $2n+1$ are not relatively prime in general.

\bigskip

\noindent \textbf{The second part}:
\begin{proof}
By setting $t=0$ and $S=R$, Relation \ref{eq:10} becomes
\begin{equation}
D_R(2n,j,1)=\sum_{u=0}^{n-j} \binom{2n}{j+u}\binom{2n-j}{u}D_R(2n,j+u,0).  \label{eq:83}
\end{equation}

By setting $j:=j+u$ in  Eq.~(\ref{eq:76}),  Eq.~(\ref{eq:76}) becomes
\begin{equation}
D_R(2n,j+u,0)=\frac{(-1)^{j+u}\binom{2n}{n}}{2n+1-j-u}M(n,j+u), \label{eq:84}
\end{equation}
where $0\leq j+u\leq n$.

By using  Eq.~(\ref{eq:84}), Eq.~(\ref{eq:83}) becomes
\begin{equation}
D_R(2n,j,1)=(-1)^j\binom{2n}{n}\sum_{u=0}^{n-j}(-1)^u\frac{1}{2n+1-j-u}\binom{2n}{j+u}\binom{2n-j}{u}M(n,j+u).  \label{eq:85}
\end{equation}
It is readily verified that 
\begin{equation}
\frac{1}{2n+1-j-u}\binom{2n}{j+u}=\frac{1}{2n+1}\binom{2n+1}{j+u}.  \label{eq:86}
\end{equation}

By using  Eq.~(\ref{eq:86}),  Eq.~(\ref{eq:85}) becomes
\begin{equation}
D_R(2n,j,1)=\frac{(-1)^j\binom{2n}{n}}{2n+1}\sum_{u=0}^{n-j}(-1)^u\binom{2n+1}{j+u}\binom{2n-j}{u}M(n,j+u).  \label{eq:87}
\end{equation}

Let $N(n,j)$ denote the sum
\begin{equation}
\sum_{u=0}^{n-j}(-1)^u\binom{2n+1}{j+u}\binom{2n-j}{u}M(n,j+u) . \label{eq:88}
\end{equation}

By  Eq.~(\ref{eq:88}),  Eq.~(\ref{eq:87}) becomes
\begin{equation}
D_R(2n,j,1)=\frac{(-1)^j\binom{2n}{n}}{2n+1}N(n,j) . \label{eq:89}
\end{equation}

Recall that $M(n,j)$ is divisible by $n+1$ for all integers  $j$ such that $0\leq j\leq n$. Therefore, $M(n,j+u)$ is divisible by $n+1$ for all non-negative integers $u$ such that $u\leq n-j$. 
By  Eq.~(\ref{eq:88}), it follows that $N(n,j)$ is divisible by $n+1$ for all non-negative integers $j$ such that $j\leq n$.
Let us prove that $N(n,j)$ is divisible by $2n+1$.

By  Eq.~(\ref{eq:88}), it is sufficient to prove that $\binom{2n+1}{j+u}M(n,j+u)$ is divisible by $2n+1$.
By setting $j:=j+u$ in  Eq.~(\ref{eq:75}), it follows that
\begin{gather*}
M(n,j+u)=\notag\\
\sum_{v=0}^{n-j-u}(-1)^v(2n+1-2j-2u-2v)\binom{2n+1-j-u}{v}\binom{2(j+u+v)}{j+u+v}\binom{2n-2j-2u-2v}{n-j-u-v} . 
\end{gather*}

Let $I(n,j,u,v)$ denote $\binom{2(j+u+v)}{j+u+v}\binom{2n-2j-2u-2v}{n-j-u-v}$. Then $\binom{2n+1}{j+u}M(n,j+u)$ is equal to
\begin{equation}
\sum_{v=0}^{n-j-u}(-1)^v(2n+1-2j-2u-2v)\binom{2n+1}{j+u}\binom{2n+1-j-u}{v}I(n,j,u,v). \notag
\end{equation}

Let us prove that $(2n+1-2j-2u-2v)\binom{2n+1}{j+u}\binom{2n+1-j-u}{v}$ is divisible by $2n+1$.
It is readily verified that
\begin{equation}
\binom{2n+1}{j+u}\binom{2n+1-j-u}{v}=\binom{2n+1}{j+u+v}\binom{j+u+v}{v}.  \label{eq:90}
\end{equation}
By  Eq.~(\ref{eq:90}), it follows that
\begin{gather}
(2n+1-2j-2u-2v)\binom{2n+1}{j+u}\binom{2n+1-j-u}{v}\notag\\=(2n+1-2j-2u-2v)\binom{2n+1}{j+u+v}\binom{j+u+v}{v}.  \label{eq:91}
\end{gather}

Recall that, by  Eq.~(\ref{eq:80}), it follows that $(2n+1-2u)\binom{2n+1}{u}$ is divisible by $2n+1$.
Therefore, $(2n+1-2(j+u+v))\binom{2n+1}{j+u+v}$ is divisible by $2n+1$.
This means that the right-side of  Eq.~(\ref{eq:91}) is divisible by $2n+1$. Then the left-side of  Eq.~(\ref{eq:91}) is divisible by $2n+1$. 
This implies that $\binom{2n+1}{j+u}M(n,j+u)$ is divisible by $2n+1$. 
By  Eq.~(\ref{eq:88}), it follows that $N(n,j)$ is divisible by $2n+1$.
Hence we have proved that $N(n,j)$ is divisible by the integers  $n+1$ and $2n+1$. Since they are relatively prime, it follows that $N(n,j)$ is divisible by $(n+1)(2n+1)$.

Finally, by using  Eq.~(\ref{eq:89}), we obtain that $D_R(2n,j,1)$  is divisible by $(n+1)\binom{2n}{n}$ for all non-negative integers $j$ such that $j\leq n$.
We assert that $D_R(2n,j,t)$ is divisible by $(n+1)\binom{2n}{n}$ for all non-negative integers $j$ and for all positive integers $t$ such that $j\leq n$.
We use Relation \ref{eq:10} and induction as in the proof of Theorem \ref{t:1}. See  Eq.~(\ref{eq:65}).

By Relation \ref{eq:9}, we have
\begin{equation}
R(2n,t+2)=D_R(2n,0,t).  \label{eq:92}
\end{equation}
Since $t\geq 1$, this implies that $t+2\geq 3$. By  Eq.~(\ref{eq:92}), it follows that $R(2n,m)$ is divisible by $(n+1)\binom{2n}{n}$ for all integers $m$ such that $m\geq 2$. This proves the second part of Theorem \ref{t:3}.
Theorem \ref{t:3} follows, as desired.
\end{proof}

\begin{remark}\label{rem:5}
Corollary \ref{cor:1} follows from Theorem \ref{t:3} and  Eq.~(\ref{eq:19}) from Lemma \ref{l:1}.
\end{remark}

\begin{remark}\label{rem:6}
The proof of Theorem \ref{t:4} is similar to the proof of Theorem \ref{t:3}.
We use Lemma \ref{l:7} instead of Lemma \ref{l:5}. We do not use  Eq.~(\ref{eq:68}).
\end{remark}

\section{Acknowledgments}

I would like to thank  Professor Jeffrey  Shallit for valuable comments
which helped to improve the article. Thanks to my teacher Vanja Vuji\'{c}
for proofreading this paper.  Also, I would like to thank the referee
for useful suggestions.

\begin{thebibliography}{HD}

\bibitem{NC}
N. J. Calkin, Factors of sums of powers of binomial coefficients, \textit{Acta Arith.\ }\textbf{86} (1998), 17--26.

\bibitem{IG}
I. M. Gessel, Super ballot numbers, \textit{J. Symbolic Comput.\ }\textbf{14} (1992), 179--194.

\bibitem{VG}
V. J. W. Guo, Proof of two divisibility properties of binomial coefficients conjectured by Z. W. Sun, \textit{Electron.\ J. Combin.\ }\textbf{21} (2014), \# P54.

\bibitem{VG1}
V. J. W. Guo, F. Jouhet, and J. Zeng, Factors of alternating sums of
products of binomial and q-binomial coefficients, \textit{Acta Arith.} 
 \textbf{127} (2007), 17--31.

\bibitem{Koshy}
T. Koshy, \textit{Catalan Numbers with Applications}, Oxford University
Press, 2009.

\bibitem{JM1}
J. Miki\'{c}, A method for examining divisibility properties of some binomial sums, \textit{J. Inteqer Sequences} \textbf{21} (2018), \href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Mikic/mikic25.html}{Article 18.8.7}.

\bibitem{JM2}
J. Miki\'{c}, A proof of a famous identity concerning the convolution of the central binomial coefficients, \textit{J. Integer Sequences} \textbf{19} (2016), \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Mikic/mikic3.html}{Article 16.6.6}.

\bibitem{JM3}
J. Miki\'{c}, Two  new identities involving the Catalan numbers and sign-reversing involutions, \textit{J. Integer Sequences }\textbf{22} (2019), \href{https://cs.uwaterloo.ca/journals/JIS/VOL22/Mikic/mikic43.html}{Article 19.7.7}.

\bibitem{MPWZ}
M. Petkov\v{s}ek, H. Wilf, and D. Zeilberger, $A = B$, A. K. Peters,
1996.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary  05A10 ; Secondary 05A19.

\noindent\emph{Keywords:} method of $D$ sums, central binomial coefficient, Catalan number, recurrence relation,  induction,  alternating binomial sum.

\bigskip
\hrule 
\bigskip

\vspace*{+.1in}
\noindent
Received May 21 2019;
revised version received  June 5 2019; November 16 2019; November 17 2019.
Published in {\it Journal of Integer Sequences}, December 30 2019.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}