% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.54}{25(1)}{2018}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\pdfoutput=1

%\usepackage{amssymb,amsfonts,amsmath,eepic,colordvi,latexsym}
\usepackage{latexsym}
\usepackage[centertags]{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{newlfont}
\usepackage{graphics}
\usepackage{color}

%%%%%
\usepackage[usenames,dvipsnames]{xcolor}

\usepackage[demo]{graphicx} % Remove demo in your file
\usepackage{wrapfig,floatrow}
\usepackage{lipsum} % provides dummy text\usepackage{wrapfig,floatrow}
\usepackage[font=small,labelfont=bf,margin=5mm]{caption}

\RequirePackage{xparse, graphicx, caption, picins}
\DeclareDocumentCommand \addpic{O{0.4\textwidth} m g}{\parpic[r]{%
\begin{minipage}{#1}
    \includegraphics[width=\textwidth]{#2}%
    \IfNoValueTF{#3}{}{\captionof{figure}{\footnotesize #3}}
\end{minipage}
}}


% we recommend the graphicx package for importing figures

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}



\newtheorem{thm}{Theorem}%[section]
\newtheorem{cor}[thm]{Corollary}%wy
\newtheorem{lem}[thm]{Lemma}%wy
\newtheorem{prop}[thm]{Proposition} %wy
\newtheorem{fig}{Figure} %wy
\newtheorem{conj}[thm]{Conjecture} %wy
\newtheorem{iden}[thm]{Identity}  %wy




\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\area}{\operatorname{\texttt{area}}}
\newcommand{\dinv}{\operatorname{\texttt{dinv}}}
\newcommand{\rank}{\operatorname{rank}}

\font\ita=cmssi12



% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A classification of Motzkin numbers modulo 8}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Ying Wang\\
\small School of Mathematical Sciences\\[-0.8ex]
\small Capital Normal University\\[-0.8ex]
\small Beijing 100048, PR China\\
\small\tt wangying.cnu@gmail.com\\
\and
Guoce Xin\thanks{This work is partially supported by National Natural Science Foundation of China (11171231).}\\
\small School of Mathematical Sciences\\[-0.8ex]
\small Capital Normal University\\[-0.8ex]
\small Beijing 100048, PR China\\
\small\tt guoce.xin@gmail.com
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jun 10, 2017}{Dec 9, 2017}{Mar 16, 2018} \\
\small Mathematics Subject Classifications: 05A10, 11B50}


\allowdisplaybreaks


\begin{document}

\maketitle




\begin{abstract}
The well-known Motzkin numbers were conjectured by Deutsch and Sagan to be nonzero modulo $8$. The conjecture was first proved by Sen-Peng Eu, Shu-chung Liu and Yeong-Nan Yeh by using the factorial representation of the Catalan numbers.
We present a short proof by
finding a recursive formula for Motzkin numbers modulo~$8$. Moreover, such a recursion leads to a full classification of Motzkin numbers modulo $8$.


  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Motzkin numbers, congruence classes
\end{abstract}

\section{Introduction}
Much work has been done in calculating the congruences of various combinatorial numbers modulo a prime power $p^r$. We begin by introduce some notations. We will use the $p$-adic notations $[n]_p =\langle n_d n_{d-1} \cdots n_0 \rangle_p$ to denote the sequence of digits representing $n$ in base $p$ \cite{Lucas}.
The \emph{$p$-adic order} or \emph{$p$-adic valuation} $\omega_p(n)$ of $n$ is defined by $$\omega_p(n)=\max\{t\in \mathbb{N}: p^t | n \}.$$
In words, it is the highest power of $p$ dividing $n$, or equivalently, the number of $0$'s to the right of the rightmost nonzero digit in $[n]_p$. The value $\omega_p(n)$ indicates the divisibility by powers of $p$,  which can be found in many previous studies \cite{L. E. Dickson}.

Many results have been established for the binomial coefficients.
The most famous as well as age-old one is the Pascal's fractal which is formed by the parities of the binomial coefficients $\binom{n}{k}$ \cite{S.Wolfram}.
Pascal's triangle also has versions modulo 4 and 8 \cite{K. S. Davis and W. A. Webb,J. G. Huard}. The behavior of Pascal's triangle modulo higher powers of $p$ is more complicated. Some rules for this behavior are discussed by Granville \cite{A. Granville}.
Kummer computed the $p$-adic order of $\binom{m+n}{m}$ \cite{E.E.Kummer}, by counting the number of carries that occur when $[m]_p$ and $[n]_p$ are added. The elegant result of Lucas \cite{Lucas} states that $\binom{n}{k} \equiv_p \prod_i \binom{n_i}{k_i}$ where $n_i$ and $k_i$ come from $[n]_p$ and $[k]_p$, and $\equiv_p$ denotes the congruence class modulo $p$. A generalization of Lucas' theorem for a prime power was established by Davis and Webb \cite{K. S. Davis}.

The most useful combinatorial numbers other than the binomial coefficients are the well-known \emph{Catalan numbers}
$$C_n= \frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{n!(n+1)!}, \quad n \in \mathbb{N}.$$
They have more than 200 combinatorial interpretations, as collected by Stanley in \cite{Stanley-Catalan}. The congruence class of $C_n$ modulo $2^r$ was
studied in \cite{Sen-Peng Eu-Shu-chung Liu,Kauers-Krattenthaler-Muller,Liu-Yeh,xin-catalan2r}.
Several other combinatorial numbers have been studied for their congruences, for example, Ap\'{e}ry numbers \cite{I. M. Gessel,Y. Mimura}, Central Delannoy numbers \cite{Eu-Liu-Yeh} and weighted Catalan numbers \cite{Postnikov-Sagan}.

In this paper we will focus on the well-known \emph{Motzkin numbers}
\begin{align}
  \label{e-Mn}
  M(n)=M_{n}= \sum_{k\geqq 0} \binom{n}{2k} C_{k}, \quad n\in \mathbb{N}.
\end{align}
Their congruences were only studied very recently. Klazar and Luca proved that the Motzkin numbers are never periodic modulo any prime number \cite{Luca-Klazar}. Deutsch and Sagan \cite{Deutsch-Sagan} studied the congruences of $M_n$ modulo $2,3$ and $5$ and made the following two ex-conjectures.

\begin{conj}[\cite{Deutsch-Sagan}]
  \label{conj-1}
  We have $M_n\equiv_{4}0$ if and only if $n=(4i+1)4^{j+1}-1$ or $n=(4i+3)4^{j+1}-2$, where $i$ and $j$ are nonnegative integers.
\end{conj}

\begin{conj}[\cite{Deutsch-Sagan}]
  \label{conj-2}
The Motzkin numbers are never congruent to $0$  modulo $8$.
\end{conj}

The two conjectures were first proved by Eu-Liu-Yeh
in \cite{Sen-Peng Eu-Shu-chung Liu}. They first derived the congruence class of the Catalan numbers $C_n$ modulo $8$ by using their factorial representations. Then they proved Conjecture \ref{conj-1} by careful analyzing formula \eqref{e-Mn}  modulo $8$. Finally they proved Conjecture \ref{conj-2} by confirming that $M(n)\equiv_8 4$ when $n$ belongs to the two cases in Conjecture \ref{conj-1}.

Our main result is the following explicit formula for $M_n$ modulo $8$, from which Conjectures \ref{conj-1} and \ref{conj-2} clearly follow.
\begin{thm}\label{t-in-mod8}
The congruence class of $M(n)$ modulo $8$ can be  characterized as follows:
\begin{align*}
   M(4s) &\equiv_8 \left\{ \begin{array}{ll}
    1-4\mathcal{Z}(\alpha)-2\chi(\|{\alpha}\| \equiv_2 1)+4\alpha, & s=2\alpha, \\
    1-4\mathcal{Z}(\alpha)-2\chi(\|{\alpha}\| \equiv_2 1), & s=2\alpha+1.
  \end{array}
  \right.\\
   M(4s+1) & \equiv_8  \left\{ \begin{array}{ll}
    1-4\mathcal{Z}(\alpha)-2\chi(\|{\alpha}\| \equiv_2 1)+4\alpha, & s=2\alpha,\\
    1-4\mathcal{Z}(\alpha)-2\chi(\|{\alpha}\| \equiv_2 1)+4, & s=2\alpha+1.
  \end{array}
  \right.\\
  M(4s+2) & \equiv_8 \left\{ \begin{array}{ll}
     4, & s=(4\alpha+3)2^{2j}-1, \\
    2-4\|{\alpha}\|, & s=(4\alpha+1)2^{2j}-1, \\
    -1+4\mathcal{Z}(\alpha)+2\chi(\|{\alpha}\| \equiv_2 1), & s=(4\alpha+3)2^{2j+1}-1, \\
    3+4\mathcal{Z}(\alpha)+2\chi(\|{\alpha}\| \equiv_2 1)+4\alpha,  & s=(4\alpha+1)2^{2j+1}-1.
  \end{array}
  \right.\\
  M(4s+3) & \equiv_8 \left\{ \begin{array}{ll}
     -2+4\|{\alpha}\|,  & s=(4\alpha+3)2^{2j}-1, \\
    4, & s=(4\alpha+1)2^{2j}-1, \\
     -1+4\mathcal{Z}(\alpha)+2\chi(\|{\alpha}\| \equiv_2 1), & s=(4\alpha+3)2^{2j+1}-1, \\
    -1+4\mathcal{Z}(\alpha)+2\chi(\|{\alpha}\| \equiv_2 1)+4\alpha, & s=(4\alpha+1)2^{2j+1}-1.
  \end{array}
  \right.
\end{align*}
Here $\chi(S)$ equals $1$ if the statement $S$ is true and equals $0$ if otherwise,  $\|{\alpha}\|$ is the sum of the digits of $[\alpha]_2$, and $\mathcal{Z}(\alpha)$ is the number of zero runs of $\alpha$ as described later in Proposition \ref{p-Ln}.
\end{thm}

Our approach is along the line of \cite{xin-catalan2r}, by using
the following recursive formula:
$$C_{n+1} =\sum_{i=0}^{\lfloor n/2 \rfloor} \binom{n}{2i} 2^{n-2i} C_{i}.$$
This formula can be easily proved by using Zeilberger's creative telescoping method \cite{Zeil}, or by two different combinatorial interpretations of $C_n$ (see \cite{xin-catalan2r}).
By combining the above formula with \eqref{e-Mn}, we derive the  following recursive formulas for $M(n)$.
\begin{align}
M(2k+2)-M(2k) &\equiv_{8} (-1)^k M(k) +f(k), \label{e-motzkin-even}\\
f(k) &=4\left(\binom{k+1}{2}-(-1)^kk\right) M(k-1) -4 \binom{k}{2} M(k-2);\nonumber \\
M(2k+1) &\equiv_{8} (2k+1)M(2k)+g(k), \label{e-motzkin-odd}\\
g(k)&=-2\binom{2k+1}{2} M(2k-1)+4\binom{2k+1}{3} M(2k-2).\nonumber
\end{align}
By using these recursive formulas, we give a simple way to compute the congruences of $M(n)$ modulo $2,4,8$.

The paper is organized as follow. In Section 2, we derive the recurrence formulas of $M_n$, which are the staring point of our approach. We also introduce basic tools for further calculations. In Section 3, we compute the congruences classes of Motzkin numbers modulo 2 and 4. Finally, we compute the congruences classes of Motzkin numbers modulo 8 in Section 4.

\section{Weighted Motzkin paths and the recursion}

Let $F(x;u)=\sum_{n\ge 0} M_u(n) x^n $ be the unique power series defined by the functional equation
$$ F(x;u)= \frac{1}{1-ux-x^2 F(x;u)}.$$
Then $F(x;u)$ is the generating function of weighted Motzkin paths (see, e.g. \cite{Sulanke-Xin}). That is, $M_u(n)$ counts weighted lattice paths from $(0,0)$ to $(n,0)$ that never go below the horizontal axis and use only steps $U=(1,1)$ $H=(1,0)$, or $D=(1,-1)$ and weights $1,u,1$ respectively.

The well-known Motzkin number $M(n)$ is our $M_1(n)$, and the Catalan number $C_n$ is our $M_0(2n)$. We also have
$C_{n+1}=M_2(n)$, which is written as
\begin{align}
M_0(2n)= M_2(n-1), \qquad \text{ for } n\ge 1 \label{e-M2n}.
\end{align}

\begin{lem}
For any constants $u$ and $v$, we have
\begin{align}
 M_{u+v}(n) &= \sum_{i=0}^n \binom{n}{i} v^i M_{u}(n-i), \label{e-u+v}\\
% (wrong) M_{v}(n) &=M_{v+2}(n-1) +v M_{v}(n-1) \qquad \text{ for } n\ge 1, \label{e-2+v} \\
M_u(2k+1) &= \sum_{i=1}^{n} \binom{2k+1}{i} (-2)^{i-1} u^{i} M_u(2k+1-i). \label{e-Mu-odd}
\end{align}
\end{lem}
\begin{proof}
Equation \eqref{e-u+v} is routine.
For \eqref{e-Mu-odd}, we need the easy fact $M_{-u}(n)=(-1)^n M_u(n)$. By setting $v=-2u$ in \eqref{e-u+v}, we obtain
\begin{align*}
  M_{-u}(n) = M_u(n)+ \sum_{i=1}^n \binom{n}{i} (-2u)^i M_u(n-i).
\end{align*}
Thus for $n=2k+1$, we obtain
$$ M_u(2k+1) = \sum_{i=1}^{n} \binom{2k+1}{i} (-2)^{i-1} u^{i} M_u(2k+1-i).$$
This is equation \eqref{e-Mu-odd}.
\end{proof}

\begin{thm}\label{t-main-rec}
We have the recursion \eqref{e-motzkin-even} and \eqref{e-motzkin-odd} with initial condition $M(0)=1$.

\end{thm}
\begin{proof}
Setting $u=1$ in \eqref{e-Mu-odd} and simplifying gives
$$ M(2k+1) \equiv_{8} (2k+1)M(2k) -2\binom{2k+1}{2} M(2k-1)+4\binom{2k+1}{3} M(2k-2).$$
This is \eqref{e-motzkin-odd}.
Note that no recursion for $M(2k)$ can be obtained in this way.

For \eqref{e-motzkin-even}, we start with
\begin{align*}
  M(2k) &= \sum_{i=0}^k \binom{2k}{2i} C_{k-i}\\
        &= \sum_{i=0}^k \sum_{j=0}^i 2^{2j}\binom{k}{2j} \binom{k-2j}{i-j} C_{k-i},
\end{align*}
which can be easily proved using Zeilberger's creative telescoping method \cite{Zeil}.
When reduced to modulo $8$, this gives
\begin{align*}
M(2k) &\equiv_{8} \sum_{i=0}^{k} \binom{k}{i} C_{k-i} +4 \binom{k}{2} \sum_{i=1}^{k-1} \binom{k-2}{i-1} C_{k-i}\\
      &\equiv_{8} 1+\sum_{i=0}^{k-1} \Big(\sum_{j=1}^i \binom{k-j}{i-j+1} \Big) M_2(k-i-1)+4 \binom{k}{2} \sum_{i'=0}^{k-2} \binom{k-2}{i'} M_2(k-2-i')\\
      &\equiv_{8} 1+\sum_{j=1}^{k-1} \sum_{i=j}^{k-1} \binom{k-j}{i-j+1} M_2((k-j)-(i-j+1))+4 \binom{k}{2} M_3(k-2)\\
      &\equiv_{8} 1+\sum_{j=1}^{k-1}M_3(k-j)+4 \binom{k}{2} M_3(k-2).
\end{align*}
(We remark that the computation modulo $2^r$ when $r\geq 4 $ becomes complicated.) Thus,
\begin{align*}
M(2k+2)&-M(2k) \equiv_{8} M_3(k)+ 4 \binom{k+1}{2} M_3(k-1)-4 \binom{k}{2} M_3(k-2)\\
              &\equiv_{8} M_{-1}(k) +4 \binom{k}{1} M_{-1}(k-1) +4 \binom{k+1}{2} M(k-1) -4 \binom{k}{2} M(k-2) \\
              &\equiv_{8} (-1)^k M(k) +4\left(\binom{k+1}{2}-(-1)^kk\right) M(k-1) -4 \binom{k}{2} M(k-2).
\end{align*}
This is just equation \eqref{e-motzkin-even}.
\end{proof}

We derive explicit formulas of $M(n) \mod 2^r$ successively for $r=1,2,3$. The idea is based on the fact that
$$ 2^{r-r'} M(n) \mod 2^r = 2^{r-r'} (M(n) \mod 2^{r'}), \qquad \text{ for } r'<r.     $$
This fact will be frequently used without mentioning.
\begin{lem}\label{l-gen-rec}
We keep the notations from Theorem \ref{t-main-rec}. Assume that we have obtained explicit formulas for $M(n) \mod 2^{r-1}$. Then there are explicit formulas for $f(k)$ and $g(k)$. Moreover, the recursion is reduced as follows.
\begin{align}
M(2k+1) &\equiv_{8} (2k+1)M(2k)+g(k),\label{e-2k+1}\\
M(4s) & \equiv_{2^r} M(0)+\sum_{j=2}^{2s-1} f(j) -  \sum_{j=1}^{s-1} (2 j M(2j) +g(j)), \label{e-4s}\\
M(4s+2) &\equiv_{2^r} M(2\beta -2)+  \sum_{i=0}^a \left(M(\beta 2^{i+2} -4) +f(\beta 2^{i+1}-2) \right),\label{e-4s-2}
\end{align}
where in \eqref{e-4s-2}, $s+1=\beta 2^{a}$ for some odd number $\beta$ and $a\ge 0$.
\end{lem}
\begin{proof}
By \eqref{e-2k+1}, we can eliminate those $M(2k+1)$ so that our formulas only involve $f(k),g(k)$ and $M(2k)$. We have to split by cases $k=2s$ and $k=2s+1$ in \eqref{e-motzkin-even}:
\begin{align*}
M(4s+4)-M(4s+2) & \equiv_{2^r} - M(2s+1) +f(2s+1)  \\
 &  \equiv_{2^r} -(2s+1) M(2s) -g(s) +f(2s+1), \\
M(4s+2)-M(4s) & \equiv_{2^r} M(2s) +f(2s) \equiv_{2^r} M(2s) +f(2s).
\end{align*}

Taking the sum of the above two equations gives the following recursion:
\begin{align}
M(4s+4)-M(4s) \equiv_{2^r} -2 s M(2s) -g(s)+f(2s)+f(2s+1). \tag{\ref{e-4s}'} \label{e-4s'}
\end{align}
(Note that we have explicit formulas of $-2s M(2s) \mod 2^r$ by the induction hypothesis.) This is equivalent to \eqref{e-4s}.

Next for $M(4s+2)$ we rewrite as follows:
\begin{align*}
  M(4(s+1)-2)-M(4s) & \equiv_{2^r} M(2(s+1)-2) +f(2s).
\end{align*}
If $s=\beta 2^a -1$ with $\beta$ odd and $a\ge 0$, then the above equation can be rewritten as
\begin{align}
  M(\beta 2^{a+2} -2)-M(\beta 2^{a+1}-2) & \equiv_{2^r} M(\beta 2^{a+2} -4) +f(\beta 2^{a+1}-2).\tag{\ref{e-4s-2}'} \label{e-4s-2'}
\end{align}
This is equivalent to \eqref{e-4s-2}.
\end{proof}

We remark that \eqref{e-4s'} and \eqref{e-4s-2'} are easier to use than \eqref{e-4s} and \eqref{e-4s-2}.

\section{Motzkin numbers modulo $2,4$}
Recall that $\omega_2(n)=a$ if $n=(2\alpha+1)2^a$. Note that $\omega_2(0)$ is not defined. The following properties are easy to check and will be frequently used without mentioning.
\begin{lem}
For nonnegative integer $\alpha$ we have
$$ \omega_2(2\alpha+1)=0, \qquad \omega_2(2\alpha)= \omega_2(\alpha)+1, \qquad \alpha \omega_2(\alpha) \equiv_2 0;$$
$$ \omega_2(\alpha!)=\sum_{i=1}^\alpha \omega_2(i), \qquad \omega_2((2\alpha+1)!)=\omega_2((2\alpha)!) = \omega_2(\alpha!)+\alpha.$$
\end{lem}
\begin{proof}
The first, second and fourth formulas follow easily by definition. The third formula follows from the first two formulas by discussing the parity of $ \alpha $. Finally,
$$ \omega_2((2\alpha+1)!)  =\omega_2((2\alpha)!)= \omega_2((2\alpha)!!))=\omega_2(\alpha!)+\alpha,$$
where in the second equality, we removed all the odd factors to get $(2\alpha)!!=2^\alpha \alpha!.$
\end{proof}

\subsection{Motzkin numbers modulo $2$}

\begin{prop}\label{p-mod2}
We have
\begin{align*}
  M(2k+1) \equiv_2 M(2k) & \equiv_{2} \omega_2(2k+2).
\end{align*}
In particular $M(4s)\equiv_2 M(4s+1) \equiv_2 1$.
\end{prop}
\begin{proof}
We apply Theorem \ref{t-main-rec} and Lemma \ref{l-gen-rec} and follow the notations there. Clearly,
we have $f(k)\equiv_2 0$ and $g(k) \equiv_2 0$. Thus we have
\begin{align*}
M(4s) & \equiv_{2} M(0)=1=\omega_2(4s+2), \\
M(4s+2) &\equiv_{2} M(2\beta -2)+  \sum_{i=0}^a \left(M(\beta 2^{i+2} -4)  \right) =a+2 =\omega_2(4s+4),
\end{align*}
where in the second equation, $s+1=\beta 2^{a}$ for some odd number $\beta$ and $a\ge 0$. The proposition then follows.
\end{proof}

\subsection{Motzkin numbers modulo 4}
\begin{lem}\label{l-mod-4}
We have the following characterization of Motzkin numbers modulo $4$.
\begin{align*}
 M(4s) &\equiv_4 1+2\omega_2(s!) \equiv_4 1+2L(s)+2s, \\
 M(4s+1) &\equiv_4 M(4s), \\
  M(4s+2) & \equiv_4 \left\{\begin{aligned}
  2\alpha +2,\qquad & \hbox{s=(2$\alpha+1) 2^{2a}-1$,\ $a\ge 0$},\\
  2\alpha+2 L(\alpha) +3,\ & \hbox{s=(2$\alpha+1) 2^{2a+1}-1$,\ $a\ge 0$}.
\end{aligned}
\right.\\
  M(4s+3) &\equiv_4 -M(4s+2) +2,
    \end{align*}
where $L(r)= \sum_{i=1}^{r-1} M(2i)$.

Consequently, $M(n)\equiv_{4}0$ if and only if $n=(4i+1)4^{j+1}-1$ or $n=(4i+3)4^{j+1}-2$ for some nonnegative integers $i$ and $j$. That is, Conjecture 1 holds true.
\end{lem}
\begin{proof}
We first show that the second part follows from the first part. Clearly,
$M(n)\equiv_4  0$ if and only if either i) $M(n)=M(4r+2)\equiv_4 2\alpha+2 \equiv_ 4 0$ for $r=(2\alpha+1)4^a-1$. Hence, $\alpha =2i+1$ for some $i$ and
  $n=(4i+3) 4^{a+1}-2 $; Or ii) $M(n)=M(4r+3)\equiv_4 -M(4r+2)+2 \equiv_4  2\alpha \equiv_4 0$ for $r=(2\alpha+1)4^a-1$. Hence, $\alpha=2i$ for some $i$ and $n=(4i+1) 4^{a+1}-1$.

Now we prove the first part by Theorem \ref{t-main-rec} and Lemma \ref{l-gen-rec}. First, we have
\begin{align*}
f(k)\equiv_4 0 \quad \textrm{and } \  g(k) &\equiv_{4} -2k(2k+1) M(2k-1) \equiv_{4} 2k \omega_2(2k)\equiv_4 2 k,
\end{align*}
where we have used Proposition \ref{p-mod2}. Thus, the recurrence reduces to
 \begin{align}
  M(2k+2)  & \equiv_{4} M(2k)+(-1)^k M(k),  \label{e-M4even}  \\
  M(2k+1) & \equiv_{4} (2k+1) M(2k)+2k. \label{e-M4odd}
\end{align}
Clearly, the odd case reduces to the even case by \eqref{e-M4odd}.

For $M(4s)$ we have
\begin{align*}
  M(4s+4)-M(4s) &\equiv_4 -M(2s+1)+M(2s) \equiv_4 -2sM(2s)-2s\\
  &\equiv_4 2 \chi(s=2\alpha+1)(1+ \omega_2(\alpha+1) +1) \equiv_4 2\omega_2(s+1),
\end{align*}
which is equivalent to $M(4s)\equiv_4 1+ 2 \omega_2(s!)\equiv_4 1+2L(s)+2s $.

For $M(4s+2)$, we write $s=\beta 2^a -1$ for a unique odd number $\beta$. We have
\begin{align*}
  M(4s+2) &\equiv_{4} M(2\beta -2)+  \sum_{i=0}^a M(\beta 2^{i+2} -4)\\
 &\equiv_{4} M(2\beta -2)+  \sum_{i=0}^a (1+2L(\beta2^{i}-1)+2(\beta2^{i}-1))\\
 &\equiv_{4}\chi( \beta=2\alpha+1)1+2L(\alpha)+2\alpha-(a+1)+\sum_{i=0}^a (2i+2L(\alpha)+2^{i+1})\\
 &\equiv_{4}2(a+2)L(\alpha)+2\alpha-a+a(a+1)+2\\
 &\equiv_{4}2(a+2)L(\alpha)+2\alpha+a^2-2\\
  &\equiv_{4}\left\{\begin{aligned}
  2\alpha +2,\qquad & \ \hbox{$a$ is even},\\
  2\alpha+2 L(\alpha) +3, & \ \hbox{$a$ is odd}.
  \end{aligned}
\right.
\end{align*}
This completes the proof.
\end{proof}

Indeed since $L(s)$ appears in computations  modulo 8,we  summarize its properties as follows.
\begin{lem}\label{l-Ls}
Let $ L(s)= \sum^{s-1}_{i=0} M(2i)$, with $L(0)=0$. Then
$$L(2s)\equiv_2 L(s), \qquad  L(2s+1)\equiv_2 1+L(s), \qquad L(s)=h_2(s!)+s,$$
$$ L(2s) \equiv_4 1-(-1)^s+L(s), \qquad L(2s+1)\equiv_4 1-L(s).$$
\end{lem}
\begin{proof}
The modulo 2 result is obvious since $L(s) \equiv_2 \sum_{i=0}^{s-1} \omega_2(2i+2)= \omega_2(s!)+s$.

For the modulo 4 result, we have, by definition,
\begin{align*}
  L(2s) &\equiv_4  \sum_{i=0}^{2s-1} M(2i)  =  \sum_{i=0}^{s-1} ( M(4i+2)+M(4i)) \\
 (\text{by }\eqref{e-M4even} )     &\equiv_4 \sum_{i=0}^{s-1} (2M(4i)+M(2i)) \\
      &\equiv_4 \sum_{i=0}^{s-1} (2+ M(2i)) \\
      &\equiv_4 2s+L(s)\\
       &\equiv_4  1-(-1)^s+L(s).
\end{align*}
By the above formula and Lemma \ref{l-mod-4}, we have
\begin{align*}
  L(2s+1)=L(2s)+M(4s) =2s+L(s) +1+2s+2L(s) =1-L(s).
\end{align*}
This completes the proof.
\end{proof}
Let
$[n]_2=n_kn_{k-1}\cdots n_1n_0$ be the binary expansion of $n\ge 1$. Then $n=n_k 2^k+\cdots +n_1\cdot 2+n_0$. Denote by $\|{n}\|=n_k+\cdots+n_1+n_0$, the sum of the binary digits of $n$. A $0$-run of $[n]_2$ is a  maximal $0$-subword $n_in_{i+1}\cdots n_j$ for some $0\le i<j\le k$, such that $n_{j+1}=1$ and $n_{i-1}\ne 0$ (including the case $i=0$).
Denote by $\mathcal{Z}(n)$ the number of $0$-runs of $[n]_2$. We have the following explicit result.
\begin{prop}\label{p-Ln}
We have
$$ L(n) \equiv_ 2 \ \|{n}\|, \ \textrm{ and } L(n) \equiv_ 4 2\mathcal{Z}(n) + \chi(\|{n}\| \equiv_ 2 1).$$
%
% Then $L(n)$ is equal to the number of $1$'s in $[n]_2$ when modulo $2$, and is equal to number of $0$-runs of $[n]_2$ times 2 plus $\chi(\sum_{i=0}^{k}n_i\equiv_ 2 1)$ when modulo $4$.
\end{prop}
\begin{proof}
The modulo $2$ case is straightforward by Lemma \ref{l-Ls}.

For the modulo $4$ case, we proceed by induction on $n$. The proposition clearly holds for the base case $n=1$. Assume it holds for all numbers smaller than $n$. We show that it holds for $n$ by considering the following two cases.

Case 1: If $n=2s+1$, then $[n]_2$ is obtained from $[s]_2$ by adding a $1$ at the end. By Lemma \ref{l-Ls} and the induction hypothesis for $s$, we have
$$L(2s+1)\equiv_4 1- L(s) \equiv_4 1- 2 \mathcal{Z}(s)-\chi(\|{s}\| \equiv_2 1) \equiv_4  2 \mathcal{Z}(s)+1-\chi(\|{s}\| \equiv_2 1), $$
which clearly equals to $2\mathcal{Z}(n)+\chi(\|{n}\|\equiv_2 1)$.

Case 2: If $n=2s$, then $[n]_2$ is obtained from $[s]_2$ by adding a $0$ at the end. i) If $s$ is odd, then by Lemma \ref{l-Ls} and the induction hypothesis for $s$, we have
$$ L(2s) \equiv_4 1-(-1)^s+L(s) = 2+L(s)=2(\mathcal{Z}(s)+1)+\chi(\|{s}\|\equiv_2 1),$$
which clearly equals to $2\mathcal{Z}(n)+\chi(\|{n}\|\equiv_2 1)$.
ii) Similarly, if $s$ is even, then
$$ L(2s) \equiv_4 1-(-1)^s+L(s) = L(s)=2\mathcal{Z}(s)+\chi(\|{s}\|\equiv_2 1).$$
This also equals to $2\mathcal{Z}(n)+\chi(\|{n}\|\equiv_2 1)$.
\end{proof}

We remark that the sequence $L(n) \mod 2$ turns out to be the Thue-Morse sequence. See \cite{Thue-Morse} for a survey on the Thue-Morse sequence.
%\end{rem}

\section{Motzkin numbers modulo 8}

\begin{lem}\label{l-mod8-rec}
The recursion from Theorem \ref{t-main-rec} reduces modulo 8 to
\begin{align*}
M(2k+2)-M(2k) &\equiv_{8} (-1)^k M(k)+ f(k), \ \text{where } f(k) = 4\chi(k\equiv_4 3)\omega_2((k+1)/2),\\
M(2k+1) &\equiv_{8} (2k+1)M(2k) +g(k),\\
     & \qquad \qquad\qquad \qquad \quad \text{where }  g(k) =   \chi(k =2\alpha+ 1)(4\alpha-2M(4\alpha)).
\end{align*}
\end{lem}
\begin{proof}
By Theorem \ref{t-main-rec}, we have
\begin{align*}
f(k)&\equiv_8 4\left(\binom{k+1}{2}-(-1)^k k \right) M(k-1) -4 \binom{k}{2} M(k-2).
\end{align*}
i) When $k=2\alpha$, we have
\begin{align*}
  f(2\alpha) &\equiv_8 4(\alpha-2\alpha) M(2\alpha-1) -4 \alpha M(2\alpha-2) \\
             &\equiv_8 4\alpha \ \omega_2(2\alpha)-4\alpha \ \omega_2(2\alpha) \equiv_8 0.
\end{align*}
ii) When $k=2\alpha+1$, we have
\begin{align*}
f(2\alpha+1)&\equiv_8 4(\alpha+1+ 2\alpha+1) M(2\alpha ) -4 \alpha M(2\alpha-1) \\
 &\equiv_8 4\alpha\  \omega_2(2\alpha+2 ) -4 \alpha \ \omega_2(2\alpha) \\
 &\equiv_8 4\chi(\alpha \equiv_ 2 1) \omega_2(\alpha+1) \equiv_ 8 4\chi(k \equiv_4 3) \omega_2((k+1)/2).
\end{align*}

We also have
\begin{align*}
g(k) & \equiv_8   -2\binom{2k+1}{2} M(2k-1)+4\binom{2k+1}{3} M(2k-2).
\end{align*}
i) When $k=2\alpha$, we have
\begin{align*}
g(2\alpha)&\equiv_8  -4\alpha M(4\alpha-1) \equiv_8 4 \alpha \ \omega_2(4\alpha) \equiv_8 0.
\end{align*}
ii) When $k=2\alpha+1$, we have
\begin{align*}
g(2\alpha+1) &\equiv_8
-2(2\alpha+3) M(4\alpha+1) + 4 M(4\alpha)\\
&\equiv_8 4\alpha M(4\alpha)-2M(4\alpha)\\
&\equiv_ 8 4\alpha -2M(4\alpha).
\end{align*}
This completes the proof.
\end{proof}

Now we are ready to prove Theorem \ref{t-in-mod8}, which, by Proposition \ref{p-Ln}, can be restated as Propositions \ref{p-M4s} and \ref{t-mod8} blow.
\begin{prop}\label{p-M4s}
We have
\begin{align}\label{e-4s-8}
   M(4s) \equiv_8 \left\{ \begin{array}{ll}
    1-2L(\alpha)+4\alpha, & s=2\alpha, \\
    1-2L(\alpha), & s=2\alpha+1.
  \end{array}
  \right.
 \end{align}
\end{prop}
\begin{proof}
We apply Lemmas \ref{l-gen-rec} and \ref{l-mod8-rec} to obtain
\begin{align*}
M(4s+4)-M(4s) &\equiv_8 f(2s)+f(2s+1)-2sM(2s)-g(s) \\
&\equiv_8 -2sM(2s)+\chi(s=2\alpha+ 1)(4\omega_2(2\alpha+2)-4\alpha+2M(4\alpha)).
\end{align*}
i) When $s=2\alpha$, we have
\begin{align*}
M(4s+4)-M(4s) &\equiv_8 -4\alpha M(4\alpha) \equiv_8 4 \alpha \ \omega_2(4\alpha+2) \equiv_8 4\alpha.
\end{align*}
ii) When $s=2\alpha+1$, we have
\begin{align*}
M(4s+4)-M(4s) &\equiv_8 -2(2\alpha+1)M(4\alpha +2)+(4\omega_2(2\alpha+2)-4\alpha+2M(4\alpha))\\
&\equiv_8 -2(M(4\alpha +2)-M(4\alpha))-4\alpha \ \omega_2(4\alpha+4)+ 4 \omega_2(2\alpha+2)+4\alpha\\
(\text{by } \eqref{e-M4even})&\equiv_8 -2(M(2\alpha))+4(\alpha+1)\omega_2((\alpha+1))+4(\alpha+1)\\
&\equiv_8 -2M(2\alpha)+4(\alpha+1),
\end{align*}
where the last step is easily checked by considering the parity of $\alpha$.

Finally, let $M'(4s)$ be defined by the right hand side of \eqref{e-4s-8}. Then $M'(0)=1$ and
\begin{align*}
  M'(8\alpha+4)-M'(8\alpha) &\equiv_8 4\alpha,\\
  M'(8\alpha+8)-M'(8\alpha+4) &\equiv_8 1-2L(\alpha+1)+4(\alpha+1)-1+2L(\alpha)\\
  &\equiv_8 4(\alpha+1)-2M(2\alpha).
\end{align*}
Thus $M(4s)=M'(4s)$ and the proposition follows.
\end{proof}

The next results relies on Proposition \ref{p-M4s}.
\begin{prop}\label{t-mod8}
We have
\begin{align*}
   M(4s+1) & \equiv_8  \left\{ \begin{array}{ll}
    1-2L(\alpha)+4\alpha, & s=2\alpha,\\
    1-2L(\alpha)+4, & s=2\alpha+1.
  \end{array}
  \right.\\
  M(4s+2) & \equiv_8 \left\{ \begin{array}{ll}
     4, & s=(4\alpha+3)2^{2j}-1, \\
    2-4L(\alpha), & s=(4\alpha+1)2^{2j}-1, \\
    -1+2L(\alpha),& s=(4\alpha+3)2^{2j+1}-1, \\
    3+2L(\alpha)+4\alpha, & s=(4\alpha+1)2^{2j+1}-1.
  \end{array}
  \right.\\
  M(4s+3) & \equiv_8 \left\{ \begin{array}{ll}
     -2+4L(\alpha), & s=(4\alpha+3)2^{2j}-1, \\
    4, & s=(4\alpha+1)2^{2j}-1, \\
     -1+2L(\alpha), & s=(4\alpha+3)2^{2j+1}-1, \\
    -1+2L(\alpha)+4\alpha, & s=(4\alpha+1)2^{2j+1}-1.
  \end{array}
  \right.
\end{align*}
\end{prop}
\begin{proof}
By Lemma  \ref{l-mod8-rec}, the odd case is reduced to the even case.

For $M(4s+1)$, we have
\begin{align*}
  M(4s+1)&\equiv_8 (4s+1)M(4s)\\
  &\equiv_8 4s+M(4s)\\
  &\equiv_8 \left\{ \begin{array}{ll}
    1-2L(\alpha)+4\alpha, & s=2\alpha, \\
    1-2L(\alpha)+4, & s=2\alpha+1.\\
  \end{array}
  \right.
\end{align*}

For $M(4s+2)$, let $\beta$ be odd. We simplify \eqref{e-4s-2'} using Lemma \ref{l-mod8-rec} and \eqref{e-4s-8}.
\begin{align}
M(\beta 2^{a+2} -2)-M(\beta 2^{a+1}-2) & \equiv_{8} M((2\alpha+1) 2^{a+2} -4) +f((2\alpha+1) 2^{a+1}-2) \nonumber \\
&\equiv_{8} \left\{ \begin{array}{ll}
    1-2L((\beta-1)/2)+2(\beta-1) & a=0, \\
    1-2L(\beta 2^{a-1}-1) & a>0.
  \end{array}
  \right. \label{e-4s-2-rec}
\end{align}
Lemma \ref{l-Ls} gives $L(2s+1)+L(s)\equiv_4 1$. Thus we have
\begin{align*}
 M(\beta 2^{a+3} -2)-M(\beta 2^{a+1}-2)&\equiv_8 2-2\left(L(\beta 2^{a-1}-1)+L(\beta 2^{a}-1)\right)  \equiv_ 8 0,  \qquad a>0.
\end{align*}
This reduces $M(\beta 2^{a+1}-2)$ to the $a=0$ and $a=1$ case.

Moreover, setting $a=1$ in \eqref{e-4s-2-rec} gives
\begin{align*}
M(8\beta-2) \equiv_8 M(4\beta-2) +1-2L(\beta-1);
\end{align*}
Setting $a=0$ in \eqref{e-4s-2-rec} gives
\begin{align*}
  M(4\beta-2) \equiv_8 M(2\beta-2)+1-2L((\beta-1)/2)+2(\beta-1).
\end{align*}
i) When $\beta =4\alpha+1$, we have
\begin{align*}
M((4\alpha+1)2^{2a+2}-2) \equiv_8 M(4(4\alpha+1)-2) &\equiv_8 M(8\alpha) +  1-2L(2\alpha) \\
  &\equiv_8 1-2L(\alpha)+4\alpha + 1-2(2\alpha+L(\alpha)) \\
  &\equiv_8 2-4L(\alpha).
\end{align*}
Consequently,
\begin{align*}
M((4\alpha+1)2^{2a+3}-2) \equiv_8 M(8(4\alpha+1)-2) &\equiv_8 2-4L(\alpha) +1-2L(4\alpha)\\
         &\equiv_8 3-4L(\alpha)-2(4\alpha+2\alpha+L(\alpha)) \\
         &\equiv_8 3+2L(\alpha)+4\alpha.
\end{align*}
ii) When $\beta=4\alpha+3$, we obtain
\begin{align*}
M((4\alpha+3)2^{2a+2}-2) \equiv_8 M(4(4\alpha+3)-2) &\equiv_8 M(8\alpha+4)+ 1-2L(2\alpha+1)+4(2\alpha+1)\\
&=1-2L(\alpha)+ 1-2(1-L(\alpha))+4\\
&=4.
\end{align*}
Consequently,
\begin{align*}
M((4\alpha+3)2^{2a+3}-2) \equiv_8 M(8(4\alpha+3)-2) &\equiv_8 4 +1-2L(4\alpha+2) \\
                  &\equiv_8 5-2(4\alpha+2)+L(2\alpha+1) \\
                  &\equiv_8 1-2(1-L(\alpha))\\
                  &\equiv_8 -1+2L(\alpha).
\end{align*}

Finally, we compute $M(4s+3)$.
By Lemma  \ref{l-mod8-rec}, we have
\begin{align*}
   M(4s+3)  &\equiv_{8} (4s+3)M(4s+2) +g(2s+1)\\
    &\equiv_{8} -M(4s+2) +4s-2M(4s)\\
    &\equiv_{8} -M(4s+2) +4s-2(1+2s+2L(s))\\
    &\equiv_{8} -M(4s+2)-2-4L(s).
\end{align*}
i) When $\beta =4\alpha+1$, we obtain
\begin{align*}
M((4\alpha+1)2^{2a+2}-1) &\equiv_8 -M((4\alpha+1)2^{2a+2}-2)-2-4L((4\alpha+1)2^{2a}-1) \\
  &\equiv_8 -2+4L(\alpha)-2-4L(\alpha)\\
   &\equiv_8 4.
\end{align*}
In the same way,
\begin{align*}
M((4\alpha+1)2^{2a+3}-1)  &\equiv_8 -M((4\alpha+1)2^{2a+3}-2) -2-4L((4\alpha+1)2^{2a+1}-1)\\
&\equiv_8 -3-2L(\alpha)-4\alpha-2-4L(\alpha)+4\\
&\equiv_8 -1+4\alpha+2L(\alpha).
\end{align*}
ii) When $\beta=4\alpha+3$, we have
\begin{align*}
M((4\alpha+3)2^{2a+2}-1)&\equiv_8- M((4\alpha+3)2^{2a+2}-2)-2-4L((4\alpha+3)2^{2a}-1)\\
&\equiv_8 -4-2-4L(\alpha)+4\\
&\equiv_8 -2+4L(\alpha).
\end{align*}
In the same way,
\begin{align*}
M((4\alpha+3)2^{2a+3}-1) &\equiv_8 -M((4\alpha+3)2^{2a+3}-2)-2-4L((4\alpha+3)2^{2a+1}-1)\\
                  &\equiv_8 1-2L(\alpha)-2-4L(\alpha)\\
                  &\equiv_8 -1+2L(\alpha).\qedhere
\end{align*}
\end{proof}




\begin{thebibliography}{10}
\bibitem{Thue-Morse}
J.-P. Allouche, J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in: C. Ding, T. Helleseth,
H. Niederreiter (Eds.), Sequences and Their Applications, Proceedings of SETA'98, Springer, New
York, 1999, pp. 1--16.

\bibitem{K. S. Davis}K. S. Davis and W. A. Webb, Lucas' theorem for prime powers, European J. Combin. 11 (1990), 229--233.

\bibitem{K. S. Davis and W. A. Webb}K. S. Davis and W. A. Webb, Pascal's triangle modulo 4, Fibonacci Quart. 29 (1991), 79--83.


\bibitem{Deutsch-Sagan} E. Deutsch and B. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory 117 (2006), 191--215.

\bibitem{L. E. Dickson}L. E. Dickson, History of the Theory of Numbers, Vol. I, Chelsea, 1919 (Chapter XI).


\bibitem {Sen-Peng Eu-Shu-chung Liu}
S.-P. Eu, S.-C. Liu, and Y.-N. Yeh, Catalan and Motzkin numbers modulo 4 and 8,
European J. Combin. 29 (2008), 1449--1466.

\bibitem{Eu-Liu-Yeh}S.-P. Eu, S.-C. Liu,and Y.-N. Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. 116 (2006), 135--144.

\bibitem{I. M. Gessel}I. M. Gessel, Some congruences for Ap\'{e}ry numbers, J. Number Theory 14 (1982), 362--368.

\bibitem{A. Granville}A. Granville, Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's Triangle, Amer. Math. Monthly 99 (1992), 318--381.

\bibitem{J. G. Huard}J. G. Huard, B. K. Spearman, and K. S. Williams, Pascal's triangle (mod 8), European J. Combin. 19 (1998), 45--62.


\bibitem{Kauers-Krattenthaler-Muller} M. Kauers, C. Krattenthaler, and T.W. Mu\"uller, A method for determining the mod-$2^k$ behaviour of recursive sequences, with applications to subgroup counting,  Electron. J. Combin. 18(2) (2011), \#P37.

\bibitem {Luca-Klazar} M. Klazar and F. Luca, On integrality and perioudicity of the Motzkin numbers, Aequationes Math. 69 (2005), 68--75.

\bibitem{E.E.Kummer} E. E. Kummer, \"{U}ber die Erg\"{a}nzungss\"{a}tze zu den allgemeinen Reciprocit\"{a}tsgesetzen, J. Reine Angew. Math. 44 (1852), 93--146.

\bibitem {Liu-Yeh} S.-C. Liu and J. C.-C. Yeh, Catalan numbers modulo $2^k$, J. Integer Sequences 13 (2010), Art. 10.5.4, 26 pp.

\bibitem {Lucas} E. Lucas, Sur les congruences des nombres eul\'{e}riens et des coeffcients diff\'{e}rentiels des fonctions trigonom\'{e}triques suivant un module premier, Bull. Soc. Math. France, 6 (1878), 49--54.

\bibitem{Y. Mimura}Y. Mimura, Congruence properties of Apery numbers, J. Number Theory 16 (1983), 138--146.
\bibitem{Postnikov-Sagan} A. Postnikov and B. Sagan, Note: What power of two divides a weighted Catalan number, J. Combin. Theory Ser. A 114 (2007), 970--977.

\bibitem{Stanley-Catalan}
R. P. Stanley, Catalan addendum. New problems for Enumerative Combinatorics. Vol. 2, available at \url{http://math.mit.edu/~rstan/ec/catadd.pdf}.

\bibitem{Sulanke-Xin}
R. Sulanke and G. Xin, Hankel determinants for some common lattice paths, Adv. in Appl. Math., 40 (2008), 149--167.

\bibitem {S.Wolfram}S. Wolfram, A New Kind of Science, Wolfram Media,  2002.
\bibitem {xin-catalan2r} Guoce Xin and Jing-Feng Xu, A short approach to Catalan numbers modulo $2^r$, Electron. J. Combin. 18(1) (2011), \#P177.
\bibitem {Zeil} D. Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991), 195--204.
\end{thebibliography}

\end{document}