<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
On the Divisibility of Generalized \\
\vskip .1in
Central Trinomial Coefficients}
\vskip 1cm
\large
Tony~D.~Noe\\
14025~NW~Harvest~Lane\\
Portland,~OR~~97229\\
USA\\
\href {mailto:noe@sspectra.com} {\tt noe@sspectra.com}
\end{center}

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

\hyphenation {combinatorial}

\vskip .2in

\begin {abstract}
We present several methods of computing sequences of generalized
central trinomial coefficients.  We generalize the Schur and Holt
congruences for Legendre polynomials in order to prove divisibility
properties of these sequences and a conjecture of Deutsch and
Sagan.
% \cite {DS}
\end {abstract}

%\newtheorem {theorem} {Theorem}
%\newtheorem {lemma} {Lemma}


\section  {Introduction}

For integers $a, b,c$, we call the coefficient of $x^n$ in the expression 
\begin {equation}
(a+b x+c x^2)^n \label {Eq.Main}
\end {equation}
the generalized central trinomial coefficient, $T_n$.
The sequences $\{ T_n \}_{n \ge 0}$ have combinatorial interpretations and,
as shown in Table 1 at the end of this paper,
appear frequently in Sloane's On-Line Encyclopedia of Integer Sequences
\cite {Sloane}.
By using the binomial theorem twice and
the identity $\binom {n} {k} \binom {n-k} {n-2k} = \binom {2k} {k} \binom {n} {2k}$,
we obtain
\begin {equation}
T_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom {2k} {k} \binom {n} {2k} b^{n-2k} (ac)^k. \label {Eq.Basic}
\end {equation}
Assuming $b$ is fixed, note that for any $a$ and $c$ having a fixed
nonzero product, the sequences will be the same.  Hence, we assume
$a=1$.  Because $b=0$ is a degenerate case and the absolute value of
$T_n$ is the same for $b$ and $-b$, we can assume $b&gt;0$ for
divisibility purposes.

As we will see below, an important quantity that determines many
properties of the sequence is the the discriminant $d=b^2-4 a c$.
There are an infinite number of pairs $(b,c)$ that yield the same
discriminant.  Also, the discriminant is always of the form $4k$ or
$4k+1$ for some integer $k$.

We begin by considering several ways of evaluating these sequences. We
will see that the representation as values of Legendre polynomials is
crucial in studying the divisibility of the sequences by primes.



\section {Ordinary Generating Function}

Using the solution to an exercise in \cite [page 575] {GKP},
we compute the sequence from the ordinary generating function 
\begin {equation}
\frac {1}{\sqrt {1-2bx+dx^2}} = \sum_{k=0}^{\infty} T_k x^k.  \label {Eq.GenFunc}
\end {equation}
Euler \cite {Euler} found this generating function for the case $a=b=c=1$.  

Observe that when c is a perfect square, the quadratic in the radical
factors into the product of two linear terms $1-(b+2 \sqrt {c})x$ and
$1-(b-2 \sqrt {c})x$ having integer coefficients.  This factorization
allows us to represent equation~\eqref {Eq.GenFunc} as the convolution
of two sequences of the form
\begin {equation*}
\frac {1}{\sqrt {1-f x}} = \sum_{k=0}^{\infty} \frac {1}{4^k} \binom {2k} {k} f^k
\end {equation*}
for constant $f$.
For $f=1$, see sequence \seqnum {A001790}.
Forming the convolution, we obtain the interesting
\begin {equation*}
T_n = \frac {1}{4^n} \sum_{k=0}^{n} \binom {2n-2k} {n-k}\binom {2k} {k}  f^k g^{n-k},
\end {equation*}
where $f=b+2 \sqrt {c}$ and $g=b-2 \sqrt {c}$ are not required to be integers.


\section {Recursion Equation}

The exercise in \cite {GKP} states that the recurrence equation for the sequence is
\begin {equation}
T_0=1, \quad T_1=b, \quad T_n = \frac {(2n-1) b T_{n-1} - (n-1) d T_{n-2}}{n}, \label {Eq.Recur}
\end {equation}
which provides an efficient formula for computing $T_n$.  Euler \cite
{Euler} found this recursion equation for the case $a=b=c=1$.  Observe
that the recursion actually needs only $T_0$ to start; $T_1$ can be
computed.  The recursion also allows us to show that
\begin {equation*}
T_{n+1} \equiv b T_n \pmod {n}.
\end {equation*}



\section {Exponential Generating Function}

Using the infinite series expansion of the modified 
Bessel function of the first kind,
\begin {equation*}
I_0(x) = \sum_{k=0}^{\infty} \frac {(\frac {1} {4} x^2)^k} {(k!)^2}
\end {equation*}
and the infinite series expansion of the exponential function,
it is not hard to show that
the sequence can be computed from the exponential generating function
\begin {equation*}
e^{b x} I_0(2x \sqrt {c}) = \sum_{k=0}^{\infty} \frac {T_k x^k} {k!}.
\end {equation*}



\section {Legendre Polynomials}

When the discriminant $d$ is nonzero, the sequence can be defined in terms of the Legendre polynomials
\begin {equation}
T_n = d^{n/2} \; P_n \bigg ( \frac {b} {\sqrt {d}} \bigg ), \label {Eq.Legendre}
\end {equation}
which is easy to derive from the generating function for Legendre polynomials
\begin {equation*}
\frac {1}{\sqrt {1-2t x+t^2}} = \sum_{n=0}^{\infty} P_n(x) t^n.
\end {equation*}
Note that in equation~\eqref {Eq.Legendre}, after multiplying each term
of the polynomial $P_n(b / \sqrt {d} )$ by $d^{n/2}$, there will be no
occurrences of $\sqrt {d}$ because the degree of the polynomial is $n$
and its terms have either all even or all odd exponents if $n$ is even
or odd, respectively.

The cases of $d=1$ and $d=0$ have particularly simple forms.  When
$d=1$, which occurs when $b=2k+1$ and $c=k(k+1)$ for integer $k \ge 0$,
we obtain $T_n = P_n(b)$.  When $d=0$, equation~\eqref {Eq.Main} can be
written as $(1+b x/2)^{2n}$ and the sequence is
\begin {equation}
T_n = \bigg (\frac {b} {2} \bigg )^n \binom {2n} {n}. \label {Eq.Binomial}
\end {equation}



\section {Schur and Holt Congruences}

The remainder of this paper contains many polynomial congruences.
A statement such as
\begin {equation*}
a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \equiv 0 \pmod {p}
\end {equation*}
in the indeterminant $x$ means that $a_k \equiv 0 \pmod {p}$ for all $k$.
The coefficients $a_k$ are allowed to be fractions if
the denominator is not divisible by $p$.

Papers by Carlitz \cite {Carlitz} and Wahab \cite {Wahab} have
congruences for Legendre polynomials modulo an odd prime $p$.  In
particular, Carlitz cites the congruence of Schur: if $n$ is written in
base~$p$ as
\begin {equation}
n=n_0 + n_1 p + n_2 p^2 + \cdots + n_r p^r \quad (0 \le n_i &lt; p), \label  {Eq.BaseP}
\end {equation}
then
\begin {equation}
P_n(x) \equiv P_{n_0}(x) \; (P_{n_1}(x))^p \;  (P_{n_2}(x))^{p^2} \ldots  (P_{n_r}(x))^{p^r}  \pmod {p}. \label {Eq.Schur}
\end {equation}
This beautiful congruence,
which is reminiscent of Lucas' theorem for binomial coefficients,
is proved by Wahab \cite [Theorem 6.1] {Wahab}.
The congruence implies that the divisibility of $P_n(x)$ by
$p$ is completely determined by the divisibility of $P_k(x)$ by
$p$ for $0 \le k &lt; p$.
We may use Fermat's little theorem to write congruence~\eqref {Eq.Schur} as
\begin {equation*}
P_n(x) \equiv P_{n_0}(x) \; P_{n_1}(x^p) \;  P_{n_2}(x^{p^2}) \ldots  P_{n_r}(x^{p^r})  \pmod {p}.
\end {equation*}
If we replace $x$ by an integer $s&gt;0$,
then Schur's congruence still holds and we use 
Fermat's little theorem to obtain a congruence without exponents:
\begin {equation}
P_n(s) \equiv P_{n_0}(s) \; P_{n_1}(s) \; P_{n_2}(s) \ldots  P_{n_r}(s)  \pmod {p}. \label {Eq.LegenProd}
\end {equation}

Another result mentioned by Carlitz and Wahab is due to Holt \cite {Holt}:
\begin {equation}
P_k(x) \equiv P_{p-k-1}(x)  \pmod {p} \label {Eq.Holt}
\end {equation}
for $k&lt;p$.
A surprising implication of this congruence is that for $(p-1)/2 &lt; k &lt; p$,
the polynomial $P_k(x)  \pmod {p}$ has degree less than $k$.
It also means, in conjunction with the Schur congruence~\eqref {Eq.Schur},
that the divisibility of $P_n(x)$ by $p$ is completely determined by
the divisibility of $P_k(x)$ by $p$ for $0 \le k \le (p-1)/2$.



\section {Scaled Legendre Polynomials}

We would like to use the Schur and Holt congruences to prove
divisibility properties of the sequence $T_n$ using equation~\eqref
{Eq.Legendre}.  However, the factor of $d^{n/2}$ in that equation makes
using the congruences dubious.  To remedy this problem, we define a
scaled Legendre polynomial having a parameter $d$:
\begin {equation}
Q_n(x,d) = d^{n/2} \; P_n \bigg ( \frac {x} {\sqrt {d}} \bigg )
= \frac {1} {2^n} \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \binom {n} {k} \binom {2n-2k} {n-2k} d^k x^{n-2k}, \label {Eq.Q}
\end {equation}
which, except for the factor of $d^k$ in the summation,
is the same as the usual Legendre polynomial definition.
The first few polynomials are $Q_0(x,d)=1, Q_1(x,d)=x,$ and
$Q_2(x,d)=\frac {1} {2} (3x^2-d)$.
This formulation also allows the case of $d=0$.
Note that if we replace $b$ by the indeterminant $x$ in
recursion equation~\eqref {Eq.Recur},
the scaled Legendre polynomials are generated.
Equation~\eqref {Eq.Legendre} becomes
\begin {equation*}
T_n = Q_n(b,d).
\end {equation*}

In the appendix we prove the Schur and Holt congruences for these
scaled Legendre polynomials.  Using the same reasoning as in the
previous section, congruence~\eqref {Eq.LegenProd} becomes
\begin {equation}
Q_n(s,d) \equiv Q_{n_0}(s,d) \; Q_{n_1}(s,d) \; Q_{n_2}(s,d) \ldots  Q_{n_r}(s,d)  \pmod {p}, \label {Eq.LegenProd2}
\end {equation}
which can be used with $s=b$ to obtain the important congruence
\begin {equation}
T_n \equiv T_{n_0} \; T_{n_1} \; T_{n_2} \; \ldots  \; T_{n_r}  \pmod {p}. \label {Eq.Fundamental}
\end {equation}
Let $u=(p-1)/2-k$ for $k&lt;p$.
Then, assuming $p \nmid d$, Holt's congruence~\eqref {Eq.Holt} becomes
\begin {equation*}
d^u \; Q_k(x,d) \equiv Q_{p-k-1}(x,d)  \pmod {p}
\end {equation*}
for scaled Legendre polynomials, which leads to
\begin {equation}
d^u \; T_k \equiv T_{p-k-1}  \pmod {p}. \label {Eq.Holt2}
\end {equation}



\section {Divisibility Properties}

The divisibility properties of these sequences are quite interesting.
However, as shown in equation~\eqref {Eq.Binomial}, the case $d=0$
concerns essentially just the central binomial coefficients,  whose
divisibility is handled by Kummer's theorem \cite [Theorem 5.12] {DS}.

In the following theorems, we assume that $\{ T_n \}_{n \ge 0}$ is a
sequence of generalized central trinomial coefficients with $b&gt;0$ and
discriminant $d \ne 0$.  For specific integer $n&gt;0$ and prime $p$, let
$(n)_p = (n_i)$ denote the base $p$ representation of $n$, as in
equation~\eqref {Eq.BaseP}.  We begin with the case $p=2$, which cannot
be handled with Legendre polynomials due to the powers of 2 in their
denominators.

\begin {theorem} \label {T.Base2}	%-------------------------------------------------------------------------- theorem 1
If $p=2$, then $T_n \equiv b \pmod {p}$.
\end {theorem}
\begin {proof} 
In the sum in equation~\eqref {Eq.Basic}, the $k=0$ term is $b^n$; the
other terms are $0 \pmod {2}$ because $\binom {2k} {k}$ is even for
$k&gt;0$.  The theorem follows from $b^n \equiv b \pmod {2}$ for $n&gt;0$.
\end {proof}

When $p$ is an odd prime there are four cases to consider: whether or
not $p \mid b$ and whether or not $p \mid d$.  We do not treat the case
of $p \nmid b d$ except in the general case treated by Theorem~\ref
{T.5}.  The following three theorems cover the three remaining cases.
The easiest case is $p$ dividing both $b$ and $d$, which we treat
first.

\begin {theorem} \label {T.2}	%-------------------------------------------------------------------------------- theorem 2
If $p$ is an odd prime with $p \mid b$ and $p \mid d$, then $p \mid T_n$.
\end {theorem}
\begin {proof}
Because $d=b^2-4c$, $p \mid b$ and $p \mid d$ imply $p \mid c$.  Then,
using equation~\eqref {Eq.Basic}, it is easy to see that $p$ divides
every term of the sum.  Hence, $p \mid T_n$.
\end {proof}

\begin {theorem}	%---------------------------------------------------------------------------------------------- theorem 3
Let $p$ be an odd prime with $p \mid b$ and $p \nmid d$.
Then the following are true:   \\
\indent (1) if $n_i$ is odd for some $0 \le i \le r$, then $p \mid T_n$,  \\
\indent (2) if $n_i$ is even and $n_i \le (p-1)/2$ for all $0 \le i \le r$, then $p \nmid T_n$,  \\
\indent (3) if $p \mid T_n$, then either $n_i$ is odd or $n_i &gt; (p-1)/2$ for some $0 \le i \le r$.
\end {theorem}
\begin {proof}
Part 1: Using equation~\eqref {Eq.Basic}, $b$ is a factor in every term
of the sum when $n$ is odd. Hence, because $p \mid b$, we obtain $p
\mid T_n$ for odd $n$.  By congruence~\eqref {Eq.Fundamental}, this
divisibility extends to all $n$ such that $n_i$ is odd for some $0 \le
i \le r$.

Part 2:  If $n_i$ is even for all $i$, then $n$ is even.
For even $n$, the last term of equation~\eqref {Eq.Basic} is $\binom
{2n} {n} c^{n/2}$; all the other terms are divisible by $p$ because
those terms have a factor of $b$, which $p$ divides.  Note that
$d=b^2-4c$, $p \mid b$, and $p \nmid d$ imply $p \nmid c$.  Because we
assume $n_i \le (p-1)/2$ for all $i$, there are no carries when $n$ is
added to $n$ in base $p$. Hence, by Kummer's theorem, $ p \nmid \binom
{2n} {n}$.  Thus, $p$ does not divide $\binom {2n} {n} c^{n/2}$ and we
obtain $p \nmid T_n$.

Part 3: this is just the contrapositive of part
2.
\end {proof}

\begin {theorem} \label {T.4}	%-------------------------------------------------------------------------------- theorem 4
Let $p$ be an odd prime with $p \nmid b$ and $p \mid d$, then $p \mid T_n$ if and only if $(p+1)/2 \le n_i \le p-1$ for some $0 \le i \le r$.
\end {theorem}
\begin {proof}
From congruence~\eqref {Eq.Fundamental}, we see that $p \mid T_n$ iff
$p \mid T_{n_i}$ for some $0 \le i \le r$.  Hence, we assume that
$n&lt;p$.  Recall that $T_n = Q_n(b,d)$.  We see from equation~\eqref
{Eq.Q}, that all the terms of $Q_n(b,d)$ except the first are divisible
by $p$ because $p \mid d$.  The coefficient of the first term is
$\binom {2n} {n} b^n/2^n$.  Assuming $(p+1)/2 \le n \le p-1$, the sum
$n+n$ has a carry in base $p$. Therefore, Kummer's theorem implies that
$p$ divides $\binom {2n} {n}$.  We conclude that $p \mid T_{n}$.  For
the converse, we prove the contrapositive.  Assume $0 \le n \le
(p-1)/2$.  The coefficient of the first term of equation~\eqref {Eq.Q}
is $\binom {2n} {n} b^n/2^n$, which is not divisible by $p$ because
$2n$ and $b$ are not divisible by $p$.  Hence, $p \nmid T_n$.
\end{proof}

\indent
The next theorem generalizes Deutsch and Sagan \cite [Corollary 4.8] {DS},
which they prove for the case $a=b=c=1$.

\begin {theorem} \label {T.5}	%--------------------------------------------------------------------------------- theorem 5
Let $p$ be a prime.  
Then $p \mid T_n$ if and only if $p \mid T_{n_i}$ for some $0 \le i \le r$.
\end {theorem}
\begin {proof}
For $p=2$, $n_i$ is either 0 or 1, and at least one $n_i$ is 1 because $n&gt;0$.
Using Theorem~\ref {T.Base2},
we conclude $p \mid T_n$ if and only if $p \mid T_1$.
For odd prime $p$, the theorem follows from congruence~\eqref {Eq.Fundamental}.
\end {proof}

\indent
For the case $a=b=c=1$, Deutsch and Sagan \cite [Conjecture 5.8] {DS}
and David W. Wilson conjecture that, for $n&lt;p$, $p$ divides $T_n$ if
and only if $p$ divides $T_{n-p-1}$.  The next theorem proves and
generalizes the conjecture.

\begin {theorem}	%----------------------------------------------------------------------------------------------- theorem 6
Let $p$ be an odd prime with $p \nmid d$ and $n &lt; p$.
Then $p \mid T_n$ if and only if $p \mid T_{p-n-1}$.
\end {theorem}
\begin {proof}
Due to symmetry, we may assume $n&lt;(p-1)/2$.  Assuming $p \mid T_n$,
congruence~\eqref {Eq.Holt2} yields $0 \equiv T_{p-n-1} \pmod {p}$,
which means $p \mid T_{p-n-1}$.  Conversely, assuming $p \mid
T_{p-n-1}$, congruence~\eqref {Eq.Holt2} yields $ d^u T_n \equiv 0
\pmod {p}$, which means $p \mid T_n$ if $p \nmid d$.
\end {proof}

The following three theorems compute the values of $T_p, T_{p-1},$ and
$T_{p-2} \pmod {p}$.  We see that if $p \nmid b d$, then $p$ does not
divide $T_p, T_{p-1},$ and $T_{p-2}$.  Theorem~\ref {T.8}  is a rare
instance in which Legendre polynomials and the Legendre symbol appear
together.

\begin {theorem}	%----------------------------------------------------------------------------------------------- theorem 7
If $p$ is a prime, then $T_p \equiv b \pmod {p}$
\end {theorem}
\begin {proof}
The theorem follows from equation~\eqref {Eq.Basic},
the fact that $\binom {p} {2k} \equiv 0 \pmod {p}$ for all indices $k&gt;0$,
and Fermat's little theorem.
\end {proof}

\begin {theorem} \label {T.8}	%--------------------------------------------------------------------------------- theorem 8
For odd prime $p$,
\begin {equation*}
T_{p-1} \equiv d^{(p-1)/2} \; P_{p-1} \bigg ( \frac {b} {\sqrt {d}} \bigg ) \equiv \bigg (\frac {d} {p} \bigg ) \pmod {p},
\end {equation*}
where $ (\frac {d} {p} )$ is the Legendre symbol.
\end {theorem}
\begin {proof}
The first congruence is equation~\eqref {Eq.Legendre}.  By
congruence~\eqref {Eq.Holt2} and the fact that $T_0 = 1$, we obtain
$T_{p-1} \equiv d^{(p-1)/2} \; T_0 \equiv d^{(p-1)/2}  \pmod {p}$.  By
Euler's criterion, $(\frac {d} {p} ) \equiv d^{(p-1)/2}  \pmod {p}$.
Hence, $T_{p-1} \equiv (\frac {d} {p} ) \pmod {p}$.
\end {proof}

\begin {theorem}	%----------------------------------------------------------------------------------------------- theorem 9
For odd prime $p$,
\begin {equation*}
T_{p-2} \equiv b d^{(p-3)/2} \pmod {p}.
\end {equation*}
\end {theorem}
\begin {proof}
If $p=3$, then $T_1=b$.  If $p \ge 5$ and $p \mid d$, then clearly
$T_{p-2} \equiv 0 \pmod p$ by Theorems~\ref {T.2} and~\ref {T.4}. If $p
\nmid d$, then the theorem follows from $T_1=b$ and congruence~\eqref
{Eq.Holt2}.
\end {proof}



\section {Appendix}

Here we prove the generalization of the Schur congruence~\eqref
{Eq.Schur} and Holt congruence~\eqref {Eq.Holt} for the scaled Legendre
polynomials $Q(x,d)$ defined by \eqref {Eq.Q}.  In several cases, the
parameter $d$ forces the proofs to be somewhat different than the ones
by Holt \cite {Holt} and Wahab \cite {Wahab}.  In all cases, $p$ is an
odd prime and all congruences are modulo $p$.  We use $Q_n$ as
shorthand for the polynomial $Q_n(x,d)$.  As mentioned above, $Q_n$
satisfies the recursion equation
\begin {equation}
n Q_n = (2n-1)x Q_{n-1} - (n-1)d Q_{n-2}  \label {Eq.QRecur}
\end {equation}
starting with $Q_0=1$.
Note that because all the denominators in $Q_n$ are powers of 2,
which are relatively prime to $p$,
we replace equation~\eqref {Eq.QRecur} by the congruence
\begin {equation}
n Q_n \equiv (2n-1)x Q_{n-1} - (n-1)d Q_{n-2}.  \label {Eq.QRecurMod}
\end {equation}
We begin by proving four lemmas that are stated, but not proved in
Wahab \cite[Lemma 6.2] {Wahab}.  The first proof is almost identical to
Holt's proof.

\begin {lemma} \label {L.1}		%-----------------------------------------------------------------------------lemma 1
If $0 \le r&lt;p$, then $Q_{k p+r} \equiv Q_{r} Q_{k p}$.
\end {lemma}
\begin {proof}
The case $r=0$ is obvious, so assume $0&lt;r&lt;p$.
Letting $n=k p+r$ in congruence~\eqref {Eq.QRecurMod}, we obtain
\begin {equation*}
r Q_{k p+r} \equiv (2r-1)x Q_{k p+r-1} - (r-1)d Q_{k p+r-2}.
\end {equation*}
Observe that with $r=1$ we obtain
\begin {equation*}
Q_{k p+1} \equiv x Q_{k p} \equiv Q_1 Q_{k p}
\end {equation*}
because $Q_1=x$.  Similarly, with $r=2$ we have
\begin {equation*}
2 Q_{k p+2} \equiv 3x Q_{k p+1} -
d Q_{k p} \equiv (3x^2-d) Q_{k p} \equiv 2 Q_2 Q_{k p},
\end {equation*}
which allows us to conclude that $Q_{k p+2} \equiv Q_2 Q_{k p}$.  Assuming 
\begin {equation*}
Q_{k p+r-1} \equiv Q_{r-1} Q_{k p} \quad \text{and} 
\quad Q_{k p+r-2} \equiv Q_{r-2} Q_{k p}, 
\end {equation*}
the general case is
\begin {equation*}
r Q_{k p+r} \equiv (2r-1) Q_{k p+r-1} - (r-1)d Q_{k p+r-2} \equiv [(2r-1) Q_{r-1} - (r-1)d Q_{r-2}] Q_{k p}.
\end {equation*}
However, the bracketed expression is merely the right-hand-side of
\eqref {Eq.QRecurMod} with $n=r$.  Hence,
\begin {equation*}
r Q_{k p+r} \equiv r Q_r Q_{k p}.
\end {equation*}
Because $0&lt;r&lt;p$, $r$ is relatively prime to $p$, and we conclude $Q_{k p+r} \equiv Q_r Q_{k p}$.
\end {proof}

The next lemma shows the effect of the parameter $d$ in the scaled
Legendre polynomials.  The parameter $d$ also forces the proof to be
slightly different than Holt's proof.

\begin {lemma} \label {L.2}		%-----------------------------------------------------------------------------lemma 2
If $1 \le r&lt;p$ and $p \nmid d$,
then $d^{r-1} Q_{k p-r} \equiv Q_{r-1} Q_{k p-1}$.
\end {lemma}
\begin {proof}
The case $r=1$ is obvious.
Letting $n=k p-r+1$ in congruence~\eqref {Eq.QRecurMod}, we obtain
\begin {equation*}
(-r+1) Q_{k p-r+1} \equiv (-2r+1)x Q_{k p-r} + r d Q_{k p-r-1},
\end {equation*}
which is rearranged to yield
\begin {equation}
r d Q_{k p-r-1} \equiv (2r-1)x Q_{k p-r} - (r-1) Q_{k p-r+1}.
\label {Eq.Lemma2}
\end {equation}
With $r=1$ we obtain, using $Q_1=x$,
\begin {equation*}
d Q_{k p-2} \equiv x Q_{k p-1} \equiv Q_1 Q_{k p-1}.
\end {equation*}
Similarly, with $r=2$ we have
\begin {equation*}
2d Q_{k p-3} \equiv 3x Q_{k p-2} - Q_{k p-1}.
\end {equation*}
Multiplying by $d$, and using the result with $r=1$, gives us
\begin {equation*}
2d^2 Q_{k p-3} \equiv 3x^2 Q_{k p-1} - d Q_{k p-1} 
\equiv (3x^2-d) Q_{k p-1} \equiv 2 Q_2 Q_{k p-1},
\end {equation*}
and we conclude that $d^2 Q_{k p-3} \equiv Q_2 Q_{k p-1}$.
For the case $r \ge 3$, we assume 
\begin {equation}
d^{r-2} Q_{k p-r+1} \equiv Q_{r-2} Q_{k p-1} \quad \text {and} \quad 
d^{r-3} Q_{k p-r+2} \equiv Q_{r-3} Q_{k p-1}, \label {Eq.Assume}
\end {equation}
and substitute $r-1$ for $r$ in the general case \eqref {Eq.Lemma2}, to obtain
\begin {equation*}
(r-1) d Q_{k p-r} \equiv (2r-3)x Q_{k p-r+1} - (r-2) Q_{k p-r+2}.
\end {equation*}
Multiplying by $d^{r-2}$, and using the assumptions \eqref {Eq.Assume},
gives us
\begin {equation*}
d^{r-1} (r-1) Q_{k p-r} \equiv [(2r-3)x Q_{r-2} - (r-2) d Q_{r-3}] Q_{k p-1}.
\end {equation*}
However, the bracketed expression is merely the 
right-hand-side of \eqref {Eq.QRecurMod} for $n=r-1$.  Hence,
\begin {equation*}
d^{r-1} (r-1) Q_{k p-r} \equiv (r-1) Q_{r-1} Q_{k p-1}
\end {equation*}
For $r \ne 1$, $r-1$ is relatively prime to $p$,
and we conclude $d^{r-1} Q_{k p-r} \equiv Q_{r-1} Q_{k p-1}$.  
\end {proof}

Although the statement of the next lemma is the same as Holt's,
the proof is different.

\begin {lemma} \label {L.3}		%-----------------------------------------------------------------------------lemma 3
If $0 \le r&lt;p$, then $Q_{p+r} \equiv x^p Q_{r}$.
\end {lemma}
\begin {proof}
By Lemma~\ref {L.1}, we have $Q_{p+r} \equiv Q_r Q_p$.  From the
definition of $Q_p$ in equation~\eqref {Eq.Q}, it is obvious that $p$
divides every term of the sum except the first.  The remaining term is
$\binom {2p} {p} x^p / 2^p$.  Hence, $Q_p \equiv A x^p$ for some
constant $A$ that is the solution to the congruence $2^p A \equiv
\binom {2p} {p}$.  By Fermat's little theorem, $2^p \equiv 2$.  Also,
$\binom {2p} {p} \equiv \binom {2} {1} = 2$.  We conclude that $A
\equiv 1$, proving the lemma.
\end {proof}

The following lemma is a generalization of Holt's congruence mentioned
earlier in this paper.  Its statement and proof are different than
Holt's version.

\begin {lemma} \label {L.4}		%-----------------------------------------------------------------------------lemma 4
If $0 \le r&lt;p$ and $p \nmid d$, then $Q_{p-r-1} \equiv d^u Q_{r}$,
where $u = (p-1)/2-r$.
\end {lemma}
\begin {proof}
Letting $k=1$ and substituting $r+1$ for $r$ in Lemma~\ref {L.2}, we have 
\begin {equation}
d^r Q_{p-r-1} \equiv Q_r Q_{p-1}.  \label {Eq.Lemma4}
\end {equation}
From the definition of $Q_{p-1}$ in equation~\eqref {Eq.Q}, we use Kummer's theorem to show that $p$ divides every term of the sum except the last.  The remaining term is the constant 
$$\frac { (-1)^m} {2^{p-1}} \binom {p-1} {m} d^m,$$
where $m=(p-1)/2$.  But $ \binom {p-1} {m} \equiv (-1)^m$ for any m,
making the constant $d^m / 2^{p-1}.$  Calling this constant $A$ and
using Fermat's little theorem as in the previous lemma, we obtain $A
\equiv d^{(p-1)/2}$.  Thus, equation~\eqref {Eq.Lemma4} becomes
\begin {equation*}
d^r Q_{p-r-1} \equiv d^{(p-1)/2} Q_r.
\end {equation*}
Dividing by $d^r$ proves the lemma.
\end {proof}

The following lemma is proved by Wahab for the usual Legendre polynomials.

\begin {lemma} \label {L.5}		%-----------------------------------------------------------------------------lemma 5
$Q_{k p} \equiv (Q_k)^p$.
\end {lemma}
\begin {proof}
By the definition of scaled Legendre polynomials \eqref {Eq.Q},
\begin {equation*}
2^{k p} Q_{k p}(x,d) = 
\sum_{j=0}^{\lfloor k p/2 \rfloor} (-1)^j \binom {k p} {j} 
\binom {2k p-2j} {k p-2j} d^j x^{k p-2j}.
\end {equation*}
However, $\binom {k p} {j} \equiv 0$ for $j \ne i p$ and
$\binom {k p} {i p} \equiv \binom {k} {i}$.  Consequently,
\begin {equation*}
2^{k p} Q_{k p}(x,d) \equiv
\sum_{i=0}^{\lfloor k/2 \rfloor} (-1)^{i p} \binom {k} {i} 
\binom {2k-2i} {k-2i} d^{i p} x^{k p-2i p}.
\end {equation*}
Using Fermat's little theorem several times, we obtain
\begin {equation*}
2^{k p} Q_{k p}(x,d) \equiv 2^k Q_k(x^p,d) \equiv 2^{k p} (Q_k(x,d))^p.
\end {equation*}
Dividing by $2^{k p}$ proves the lemma.
\end {proof}

The following theorem proves Schur's congruence for scaled Legendre
polynomials.  The proof is identical to Wahab's for the usual Legendre
polynomials.

\begin {theorem}	%----------------------------------------------------------------------------------------------theorem 10
If $n=n_0 + n_1 p + n_2 p^2 + \cdots + n_r p^r$, with $0 \le n_i &lt; p$, then
\begin {equation*}
Q_n \equiv Q_{n_0} \; (Q_{n_1})^p \;  (Q_{n_2})^{p^2} \ldots  (Q_{n_r})^{p^r}.
\end {equation*}
\end {theorem}
\begin {proof}
Induction on $n$ is used.  The statement is true for $0 \le n &lt; p$.
By Lemma~\ref {L.1},
\begin {equation*}
Q_n \equiv Q_{n_0} \; Q_{n_1 p + n_2 p^2 + \cdots + n_r p^r}.
\end {equation*}
By Lemma~\ref {L.5},
\begin {equation*}
Q_n \equiv Q_{n_0} \; (Q_{n_1 + n_2 p + \cdots + n_r p^{r-1}})^p.
\end {equation*}
By the inductive assumption,
\begin {equation*}
Q_n \equiv Q_{n_0} \; [ Q_{n_1} \; (Q_{n_2})^p \cdots (Q_{n_r})^{p^{r-1}} ]^p.
\end {equation*}
Hence,
\begin {equation*}
Q_n \equiv Q_{n_0} \; (Q_{n_1})^p \; (Q_{n_2})^{p^2} \cdots (Q_{n_r})^{p^r}.
\end {equation*}
\end {proof}



\section {Acknowledgment}
The author thanks Bruce E. Sagan for his valuable comments.  The author
also thanks the referee for carefully reading this paper and making
many helpful comments.



\begin {thebibliography} {9}

\bibitem {Carlitz}
Leonard~Carlitz, Congruences properties of the polynomials of Hermite,
Laguerre and Legendre, {\it  Math. Zeitschr.} \textbf {59} (1954), 474--483.

\bibitem {DS}
Emeric~Deutsch and Bruce~E.~Sagan, Congruences for Catalan and 
Motzkin numbers and related sequences,
{\it J. Number Theory}  \textbf {117} (2006), 191--215.

\bibitem {Euler}
Leonhard~Euler,  Observationes analyticae,
{\it Novi Commentarii Acad. Sci. Imper. 
Petropolitanae} \textbf{11} (1765) 1767, 124--143. 
Reprinted in \emph {Opera Omnia}, Series I, vol. 15, 50--69.

\bibitem {GKP}
Ronald~L.~Graham, Donald~E.~Knuth, and Oren~Patashnik, \emph {Concrete Mathematics}. Addison-Wesley, Reading, MA, 1994, 2nd edition.

\bibitem {Holt}
J.~B.~Holt,  On the irreducibility of Legendre polynomials, II,
{\it Proc. London Math. Soc.} (2),  \textbf {12} (1913), 126--132.

\bibitem {Sloane}
N.~J.~A.~Sloane, {\em \htmladdnormallink {The On-Line Encyclopedia of Integer Sequences}{http://www.research.att.com/~njas/sequences}}, published electronically at www.research.att.com/$\sim$njas/sequences.

\bibitem {Wahab}
J.~H.~Wahab, New cases of irreducibility for Legendre polynomials,
{\it Duke Math J.} \textbf {19} (1952), 165--176.

\end {thebibliography}


\begin {table} \begin {center}
\label {Ta1}
{\footnotesize
\begin {tabular} {|r|r|r|r|c|l|}
\hline
&amp; &amp; &amp; &amp; &amp; \\[-5pt]
$a$ &amp; $b$ &amp; $c$ &amp; $d$ &amp; A-number &amp; Comments\\
&amp; &amp; &amp; &amp; &amp; \\[-5pt]
\hline
1 &amp; 1 &amp; 1 &amp; -3 &amp; \seqnum {A002426} &amp; central trinomial coefficients \\
1 &amp; 1 &amp; 2 &amp; -7 &amp; \seqnum {A084601} &amp;  \\
1 &amp; 1 &amp; 3 &amp; -11 &amp; \seqnum {A084603} &amp;  \\
1 &amp; 1 &amp; 4 &amp; -15 &amp; \seqnum {A084605} &amp;  \\
1 &amp; 1 &amp; 5 &amp; -19 &amp; \seqnum {A098264} &amp;  \\
1 &amp; 1 &amp; 6 &amp; -23 &amp; \seqnum {A098265} &amp;  \\
1 &amp; 1 &amp; 8 &amp; -31 &amp; \seqnum {A098329} &amp;  \\
1 &amp; 1 &amp; 12 &amp; -47 &amp; \seqnum {A098439} &amp;  \\
1 &amp; 1 &amp; 15 &amp; -59 &amp; \seqnum {A098440} &amp;  \\
1 &amp; 1 &amp; 16 &amp; -63 &amp; \seqnum {A098441} &amp;  \\
1 &amp; 1 &amp; 24 &amp; -95 &amp; \seqnum {A098442} &amp;  \\
1 &amp; 1 &amp; -1 &amp; 5 &amp; \seqnum {A098331} &amp;  \\
1 &amp; 1 &amp; -2 &amp; 9 &amp; \seqnum {A098332} &amp;  \\
1 &amp; 1 &amp; -3 &amp; 13 &amp; \seqnum {A098333} &amp;  \\
1 &amp; 1 &amp; -4 &amp; 17 &amp; \seqnum {A098334} &amp;  \\
1 &amp; 2 &amp; 1 &amp; 0 &amp; \seqnum {A000984} &amp; binomial($2n,n$) \\
1 &amp; 2 &amp; 2 &amp; -4 &amp; \seqnum {A006139} &amp;  \\
1 &amp; 2 &amp; 3 &amp; -8 &amp; \seqnum {A084609} &amp;  \\
1 &amp; 2 &amp; 4 &amp; -12 &amp; \seqnum {A098453} &amp;  \\
1 &amp; 2 &amp; 5 &amp; -16 &amp; \seqnum {A084770} &amp;  \\
1 &amp; 2 &amp; -1 &amp; 8 &amp; \seqnum {A098335} &amp;  \\
1 &amp; 2 &amp; -2 &amp; 12 &amp; \seqnum {A098336} &amp;  \\
1 &amp; 2 &amp; -3 &amp; 16 &amp; \seqnum {A012000} &amp; $4^n P_n(1/2)$ \\
1 &amp; 2 &amp; -4 &amp; 20 &amp; \seqnum {A098337} &amp;  \\
1 &amp; 3 &amp; 1 &amp; 5 &amp; \seqnum {A026375} &amp;  \\
1 &amp; 3 &amp; 2 &amp; 1 &amp; \seqnum {A001850} &amp; $P_n(3)$, central Delannoy numbers  \\
1 &amp; 3 &amp; 5 &amp; -11 &amp; \seqnum {A098444} &amp;  \\
1 &amp; 3 &amp; -1 &amp; 13 &amp; \seqnum {A098338} &amp;  \\
1 &amp; 3 &amp; -2 &amp; 17 &amp; \seqnum {A098339} &amp;  \\
1 &amp; 3 &amp; -3 &amp; 21 &amp; \seqnum {A098340} &amp;  \\
1 &amp; 3 &amp; -4 &amp; 25 &amp; \seqnum {A098341} &amp;  \\
1 &amp; 4 &amp; 1 &amp; 12 &amp; \seqnum {A081671} &amp;  \\
1 &amp; 4 &amp; 2 &amp; 8 &amp; \seqnum {A080609} &amp;  \\
1 &amp; 4 &amp; 3 &amp; 4 &amp; \seqnum {A069835} &amp; $2^n P_n(2)$ \\
1 &amp; 4 &amp; 4 &amp; 0 &amp; \seqnum {A059304} &amp; $2^n$ binomial($2n,n$) \\
1 &amp; 4 &amp; 5 &amp; -4 &amp; \seqnum {A098443} &amp;  \\
1 &amp; 4 &amp; 6 &amp; -8 &amp; \seqnum {A106258} &amp;  \\
1 &amp; 5 &amp; 1 &amp; 21 &amp; \seqnum {A098409} &amp;  \\
1 &amp; 5 &amp; 4 &amp; 9 &amp; \seqnum {A084771} &amp;  \\
1 &amp; 5 &amp; 6 &amp; 1 &amp; \seqnum {A006442} &amp; $P_n(5)$  \\
1 &amp; 6 &amp; 1 &amp; 32 &amp; \seqnum {A098410} &amp;  \\
1 &amp; 6 &amp; 9 &amp; 0 &amp; \seqnum {A098658} &amp; $3^n$ binomial($2n,n$) \\
1 &amp; 7 &amp; 1 &amp; 45 &amp; \seqnum {A104454} &amp;  \\
1 &amp; 7 &amp; 12 &amp; 1 &amp; \seqnum {A084768} &amp; $P_n(7)$ \\
1 &amp; 8 &amp; 16 &amp; 0 &amp; \seqnum {A098430} &amp; $4^n$ binomial($2n,n$) \\
1 &amp; 9 &amp; 20 &amp; 1 &amp; \seqnum {A084769} &amp; $P_n(9)$ \\
\hline
\end {tabular}
}
\caption {Generalized Central Trinomial Coefficients}
\end {center} \end {table} 

\clearpage

\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 05A19; Secondary 11B07.

\noindent \emph {Keywords:} central trinomial coefficient, Legendre polynomials, divisibility, congruences.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum {A000984},
\seqnum {A001790},
\seqnum {A001850},
\seqnum {A002426},
\seqnum {A006139},
\seqnum {A006442},
\seqnum {A012000},
\seqnum {A026375},
\seqnum {A059304},
\seqnum {A069835},
\seqnum {A080609},
\seqnum {A081671},
\seqnum {A084601},
\seqnum {A084603},
\seqnum {A084605},
\seqnum {A084609},
\seqnum {A084768},
\seqnum {A084769},
\seqnum {A084770},
\seqnum {A084771},
\seqnum {A098264},
\seqnum {A098265},
\seqnum {A098329},
\seqnum {A098331},
\seqnum {A098332},
\seqnum {A098333},
\seqnum {A098334},
\seqnum {A098335},
\seqnum {A098336},
\seqnum {A098337},
\seqnum {A098338},
\seqnum {A098339},
\seqnum {A098340},
\seqnum {A098341},
\seqnum {A098409},
\seqnum {A098410},
\seqnum {A098430},
\seqnum {A098439},
\seqnum {A098440},
\seqnum {A098441},
\seqnum {A098442},
\seqnum {A098443},
\seqnum {A098444},
\seqnum {A098453},
\seqnum {A098658},
\seqnum {A104454},
and
\seqnum {A106258}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 2 2005;
revised version received June 28 2006. 
Published in {\it Journal of Integer Sequences}, July 5 2006.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                






</pre></body></html>