\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 
Congruences for a Class of Alternating \\
\vskip .1in
Lacunary Sums of Binomial Coefficients
}
\vskip 1cm
\large
Karl Dilcher\\
Department of Mathematics and Statistics\\
Dalhousie University\\
Halifax, Nova Scotia B3H 3J5 \\
Canada\\
\href{mailto:dilcher@mathstat.dal.ca}{\tt dilcher@mathstat.dal.ca} \\
\end{center}

\vskip .2 in

\begin{abstract}
An 1876 theorem of Hermite, later extended by Bachmann, gives congruences
modulo primes for lacunary sums over the rows of Pascal's triangle. 
This paper gives an analogous result for alternating sums over a certain
class of rows. The proof makes use of properties of certain linear recurrences.
\end{abstract}

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


\section{Introduction}

Given the importance of binomial coefficients and combinatorial sums in many
areas of mathematics, it is not surprising that divisibility properties and 
congruences of these combinatorial objects have been 
extensively studied. For instance, numerous older results can be found in
Dickson's {\it History\/} \cite[Ch.~IX]{Di}, while a more modern treatment 
of the subject is given by Granville
\cite{Gr}. One such result is the following congruence due to Hermite \cite{He}
and, in the general case, Bachmann \cite[p.~46]{Ba}.

\begin{theorem}[Hermite and Bachmann]
Let $p$ be a prime and $k$ a positive integer. Then
\begin{equation}\label{1.1}
\sum_{0<j(p-1)<k}\binom{k}{j(p-1)} \equiv 0 \pmod{p}.
\end{equation}
\end{theorem}

Bachmann \cite[p.~53]{Ba} and before him Hermite
\cite{He} used this congruence to derive recurrence relations for the integer
parts of Bernoulli numbers.

It is the purpose of this paper to derive an {\it alternating\/} sum analog to 
a special case of \eqref{1.1}. This also has
consequences in the theory of Bernoulli numbers and polynomials. In fact,
a congruence for the alternating sum in the special case where $k$ is a
multiple of $p-1$, given below as Corollary~1, is instrumental in a forthcoming
study of possible multiple zeros of Bernoulli polynomials \cite{Dil}.

While the congruence \eqref{1.1} is not difficult to prove, the following 
main result of this paper requires considerably more effort.

\begin{theorem}
Let $p$ be an odd prime and $q$ a positive integer. Then
\begin{equation}\label{1.2}
\sum_{j=0}^{\lfloor q/2\rfloor}\binom{q(p-1)}{2j(p-1)} 
\equiv\begin{cases}
1 \pmod{p}, & \hbox{if $q$ odd};\\
2 \pmod{p}, & \hbox{if $q$ even, $p+1\nmid q$};\\
\frac{3}{2} \pmod{p}, & \hbox{if $p+1\mid q$}.
\end{cases}
\end{equation}
\end{theorem}

In order to derive the desired congruence for an alternating sum, we first 
note that from \eqref{1.1} with $k=q(p-1)$ we immediately get
\begin{equation}\label{1.2a}
\sum_{j=0}^q\binom{q(p-1)}{j(p-1)} \equiv 2 \pmod{p}.
\end{equation}
Then we use the obvious identity
$$
\sum_{j=0}^q(-1)^j\binom{q(p-1)}{j(p-1)}
=-\sum_{j=0}^q\binom{q(p-1)}{j(p-1)}
+2\sum_{j=0}^{\lfloor\frac{q}{2}\rfloor}\binom{q(p-1)}{2j(p-1)},
$$
and \eqref{1.2} and \eqref{1.2a} immediately give the following

\begin{corollary}
Let $p$ be an odd prime and $q$ a positive integer. Then
\begin{equation}\label{1.3}
\sum_{j=0}^q (-1)^j\binom{q(p-1)}{j(p-1)}
\equiv\begin{cases}
0 \pmod{p}, & \hbox{if $q$ odd};\\
2 \pmod{p}, & \hbox{if $q$ even, $p+1\nmid q$};\\
1 \pmod{p}, & \hbox{if $p+1\mid q$}.
\end{cases}
\end{equation}
\end{corollary}
When $q$ is odd, it follows by symmetry that this alternating sum vanishes;
this also implies the first case in \eqref{1.2}; the case where $q$ is even
is more difficult.
The congruences \eqref{1.1}, \eqref{1.2}, and \eqref{1.3} have obvious 
interpretations in terms of lacunary sums of elements in certain rows of
Pascal's triangle.

In order to prove Theorem~2, we first derive a number of lemmas in Section~2,
followed by the proof of the theorem in Section~3. 

\section{Auxiliary Results}

We begin by stating the following classical divisibility and congruence 
results for binomial coefficients; see also \cite{Gr}.

\begin{lemma}
{\rm (a) (Kummer \cite{Ku})} The exact power of the prime $p$ which divides
$\binom{n}{m}$ is given by the number of ``carries" when $m$ and $n-m$ are
added in base $p$.

{\rm (b) (Lucas \cite{Lu})} For all primes $p$ and nonnegative integers 
$n,k,a,b$ with $0\leq a,b <p$ we have
\begin{equation}\label{4}
\binom{np+a}{kp+b} \equiv \binom{n}{k}\binom{a}{b} \pmod{p}.
\end{equation}
\end{lemma}

With these results we prove the following

\begin{lemma}
Let $p$ be an odd prime and $q$, $j$ integers with $2\leq q\leq 2p$ and 
$1\leq j\leq q-1$. Then
\begin{equation}\label{5}
\binom{q(p-1)}{j(p-1)}\equiv\begin{cases}
0 \pmod{p}, & \text{ if } q\neq p+1;\\
\binom{p-1}{j-1}^2 \pmod{p}, & \text{if } q = p+1.
\end{cases}
\end{equation}
\end{lemma}

\begin{proof}
First, let $2\leq q\leq p$. Then we can write in base $p$,
$$
(q-j)(p-1) = (q-j-1)p+(p-(q-j)),\quad j(p-1) = (j-1)p+(p-j),
$$
and we see that upon adding these two numbers we have one carry in base $p$,
and we are done by Lemma~1(a).

When $q\geq p+2$, counting the carries would be more difficult, and we use
instead Lucas' result \eqref{4} in its iterated form, i.e., the result 
applied also to $\binom{n}{k}$. We write $q=p+1+s$ with $1\leq s\leq p-1$.
Then clearly
\begin{equation}\label{6}
q(p-1) = p^2+(s-1)p+(p-s-1).
\end{equation}
When $1\leq j\leq p$, we write $j(p-1)=(j-1)p+(p-j)$, and with \eqref{4} and
\eqref{6} we get
$$
\binom{q(p-1)}{j(p-1)}\equiv \binom{1}{0}\binom{s-1}{j-1}\binom{p-s-1}{p-j}
\equiv 0 \pmod{p},
$$
since either the second binomial coefficient on the right vanishes (when
$j>s$), or the third one vanishes (when $j\leq s$). Next, when $j=p+1$, we
have $j(p-1)=(p-1)p+(p-1)$, and
$$
\binom{q(p-1)}{(p+1)(p-1)}\equiv \binom{1}{0}\binom{s-1}{p-1}\binom{p-s-1}{p-1}
\equiv 0 \pmod{p}
$$
for similar reasons as above. Thirdly, when $p+2\leq j\leq q-1$, we write
$j=p+1+t$, $1\leq t<s$. Then in base $p$ we have 
$j(p-1)=p^2 +(t-1)p+(p-t-1)$, and thus
$$
\binom{q(p-1)}{j(p-1)}\equiv \binom{1}{1}\binom{s-1}{t-1}\binom{p-s-1}{p-t-1}
\equiv 0 \pmod{p}
$$
since the last binomial coefficient on the right vanishes. This proves
\eqref{5} for $q\neq p+1$.

Finally, when $q=p+1$, we write  $q(p-1)=(p-1)p+(p-1)$ and 
$j(p-1)=(j-1)p+(p-j)$ so that, again by \eqref{4},
$$
\binom{(p+1)(p-1)}{j(p-1)}\equiv \binom{p-1}{j-1}\binom{p-1}{p-j}
=\binom{p-1}{j-1}^2 \pmod{p},
$$
and this completes the proof of the lemma.
\end{proof}

The next lemma is the central ingredient in the proof of Theorem~2. The proof
uses a variant of a standard method.

\begin{lemma}
Let $p$ be an odd prime and $\zeta$ a primitive $(2p-2)$th root of unity.
If we define
\begin{equation}\label{7}
S_p(q) := \sum_{k=1}^{2p-2}\left(1+\zeta^k\right)^{(p-1)q}
\end{equation}
for $q=1,2,\ldots$, then
\begin{equation}\label{8}
S_p(q) = (2p-2)\sum_{j=0}^{\lfloor q/2\rfloor}\binom{q(p-1)}{2j(p-1)}.
\end{equation}
\end{lemma}

\begin{proof}
We use the well-known fact that
\begin{equation}\label{9}
\sum_{k=1}^{2p-2}\zeta^{mk} = \begin{cases}
0, & \hbox{if}\quad 2p-2 \nmid m;\\
2p-2, & \hbox{if}\quad 2p-2 \mid m.
\end{cases}
\end{equation}
Now, using a binomial expansion, we get with \eqref{7},
\begin{align*}
S_p(q) 
&=\sum_{k=1}^{2p-2}\sum_{m=0}^{q(p-1)}\binom{q(p-1)}{m}\left(\zeta^k\right)^m\\
&=\sum_{m=0}^{q(p-1)}\binom{q(p-1)}{m}\sum_{k=1}^{2p-2}\zeta^{mk}.
\end{align*}
The result now follows from \eqref{9}.
\end{proof}

By the theory of linear recurrence relations with constant coefficients we
know from the right-hand side of \eqref{7} that for fixed $p$ the sequence 
$\{S_p(q)\}$, $q=1,2,\ldots$, is a
linear recurrence sequence of order at most $2p-2$, and that the characteristic
polynomial of this sequence has $(1+\zeta^k)^{p-1}, k=1,2,\ldots, 2p-2$, as
its roots. This motivates the following lemma.

\begin{lemma}
Let $p$ be an odd prime and $f_p(x)$ the unique monic polynomial that has
the numbers $(1+\zeta^k)^{p-1}$, $k=1,2,\ldots, 2p-2$, as its roots. Then
\begin{equation}\label{10}
f_p(x)\equiv x\sum_{n=0}^{2p-3} a_nx^{2p-3-n} \pmod{p},
\end{equation}
where for $0\leq n\leq p-2$ we have
\begin{equation}\label{11}
a_n \equiv \begin{cases}
(m+1)^2, \pmod{p} & \hbox{if}\quad n=2m;\\
(m+1)(m+2), \pmod{p} & \hbox{if}\quad n=2m+1,
\end{cases}
\end{equation}
and for $p-1\leq n\leq 2p-3$,
\begin{equation}\label{12}
a_n \equiv -a_{2p-3-n} \pmod{p}.
\end{equation}
\end{lemma}

\noindent
{\bf Remark.} The expression in \eqref{11} can also be written more concisely
as
$$
a_n \equiv 
\left\lfloor\tfrac{n+2}{2}\right\rfloor\left\lfloor\tfrac{n+3}{2}\right\rfloor
\pmod{p}.
$$
The right-hand side is the shifted sequence \seqnum{A002620} in \cite{Sl}.

\begin{proof}[Proof of Lemma~4]
Using the well-known fact that $(1+x)^p\equiv 1+x^p\pmod{p}$, we have
$$
(1+\zeta^j)^{p-1} = \frac{(1+\zeta^j)^p}{1+\zeta^j}
\equiv \frac{1+\zeta^{jp}}{1+\zeta^j}
= \frac{1+(\zeta^{p-1})^j\zeta^j}{1+\zeta^j} \pmod{p}
$$
for $i\neq p-1$. Then, with $\zeta^{p-1}=-1$, we have
\begin{equation}\label{13}
(1+\zeta^j)^{p-1} \equiv \begin{cases}
1 \pmod{p}, & \hbox{if $j$ even, $j\neq p-1$};\\
0 \pmod{p}, & \hbox{if $j=p-1$};\\
\frac{1-\zeta^j}{1+\zeta^j} \pmod{p}, & \hbox{if $j$ odd}.
\end{cases}
\end{equation}
Hence 
\begin{equation}\label{14}
f_p(x) \equiv x(x-1)^{p-2}
\sum_{j=0}^{p-2}\left(x-\frac{1-\zeta^{2j+1}}{1+\zeta^{2j+1}}\right)\pmod{p}.
\end{equation}
First, using the expansion
\begin{equation}\label{15}
\binom{p-2}{k}=\frac{(p-2)(p-3)\cdots(p-2-k+1)}{1\cdot 2\cdots k}
\equiv (-1)^k(k+1) \pmod{p},
\end{equation}
which can also be found in \cite[p.~272]{Di}, we have
\begin{equation}\label{16}
(x-1)^{p-2}=\sum_{k=0}^{p-2}\binom{p-2}{k}(-1)^kx^{p-2-k}
\equiv \sum_{k=0}^{p-2}(k+1)x^{p-2-k} \pmod{p}.
\end{equation}
Next, if we set
\begin{equation}\label{17}
x_j:=\frac{1-\zeta^{2j+1}}{1+\zeta^{2j+1}}
\end{equation}
and solve for $\zeta^{2j+1}$, we get
$$
\zeta^{2j+1} = \frac{1-x_j}{1+x_j},
$$
and by raising this to the $(p-1)$th power, we see that the $x_j$,
$j=0, 1, \ldots,p-2$, are all the roots of the polynomial equation
$$
(1-x)^{p-1}=-(1+x)^{p-1},
$$
since $\zeta$ is a primitive $(2p-2)$th root of unity. But since
\begin{equation}\label{18}
\sum_{j=0}^{\frac{p-1}{2}}\binom{p-1}{2j}x^{2j} 
= \frac{(1+x)^{p-1}+(1-x)^{p-1}}{2},
\end{equation}
we see that the expressions in \eqref{17} are exactly the zeros of the 
polynomials on the left of \eqref{18}, and thus
\begin{equation}\label{19}
\sum_{j=0}^{p-2}\left(x-\frac{1-\zeta^{2j+1}}{1+\zeta^{2j+1}}\right)
= \sum_{j=0}^{\frac{p-1}{2}}\binom{p-1}{2j}x^{2j}
\equiv \sum_{j=0}^{\frac{p-1}{2}}x^{2j} \pmod{p},
\end{equation}
where we have used the congruence $\binom{p-1}{k}\equiv (-1)^k\pmod{p}$,
which can be obtained as in \eqref{15}, or see \cite[p.~272]{Di}. If we 
define the sequence $\{\delta_j\}$ by $\delta_j=1$ when $j$ is even and
$\delta_j=0$ when $j$ is odd, then the product of the polynomials in \eqref{16}
and \eqref{19} becomes
$$
\sum_{n=0}^{2p-3}\left(\sum_{k=0}^n(k+1)\delta_{n-k}\right)x^{2p-3-k}
= \sum_{n=0}^{2p-3} a_n x^{2p-3-n},
$$
where the inner sum is not usually taken over the whole range. In fact, it 
is easy to see that
\begin{equation}\label{20}
a_n = \sum_{k=0}^n (k+1)\delta_{n-k} \quad\hbox{for}\quad 0\leq n\leq p-2,
\end{equation}
and
\begin{equation}\label{21}
a_n = \sum_{k=n-p+1}^{p-2} (k+1)\delta_{n-k} \quad\hbox{for}\quad p-1\leq n\leq 2p-3.
\end{equation}
Now, for $n\leq p-2$ we get from \eqref{20},
\begin{align*}
a_{2m} &= \sum_{k=0}^m(2k+1) = (m+1)^2,\\
a_{2m+1} &= \sum_{k=1}^{m+1}2k = (m+1)(m+2),
\end{align*}
which is just \eqref{11}. In \eqref{21} we shift the order of summation, to
obtain
$$
a_n = \sum_{k=0}^{2p-3-n} (k+n-p+2)\delta_{p-1-k}
\equiv \sum_{k=0}^{2p-3-n} (k+n+2)\delta_k \pmod{p}
$$
since $p-1-k\equiv k\pmod{2}$. Finally we reverse the order of summation, 
so that
\begin{align*}
a_n &\equiv \sum_{k=0}^{2p-3-n} (2p-3-n-k+n+2)\delta_{(2p-3-n)-k} \\
&\equiv -\sum_{k=0}^{2p-3-n} (k+1)\delta_{(2p-3-n)-k} \pmod{p}.
\end{align*}
This, with \eqref{20}, accounts for \eqref{12}, which completes the proof of
the lemma.
\end{proof}

We are now ready to prove our main result.

\section{Proof of Theorem~2}

In view of Lemma~3 it suffices to determine the $S_p(q), q=1,2,\ldots$ We
first find the initial values $\pmod{p}$ of this sequence. By the first part
of Lemma~2 we immediately get the first two parts of \eqref{1.2} for 
$q\leq 2p$. By the second part of \eqref{5} we have for $q=p+1$,
\begin{align}\label{22}
2\sum_{j=0}^{\lfloor q/2\rfloor}\binom{q(p-1)}{2j(p-1)}
&\equiv 4+2\sum_{j=1}^{\frac{p-1}{2}}\binom{p-1}{2j-1}^2 \\
&=4+\binom{2p-2}{p-1}-(-1)^{\frac{p-1}{2}}\binom{p-1}{\frac{p-1}{2}} \pmod{p},\nonumber
\end{align}
where we have used a well-known explicit formula; see, e.g., 
\cite[Eq.~(3.74)]{Go}. For the first binomial coefficient on the right we have,
by \eqref{4},
$$
\binom{2p-2}{p-1}=\binom{1\cdot p+(p-2)}{0\cdot p+(p-1)}
\equiv \binom{1}{0}\binom{p-2}{p-1} = 0 \pmod{p},
$$
and as a special case of a well-known theorem of Morley (see, e.g., \cite{Gr}
or \cite[p.~105]{HW}) we have
$$
(-1)^{\frac{p-1}{2}}\binom{p-1}{\frac{p-1}{2}} \equiv 4^{p-1} \equiv 1\pmod{p}.
$$
Hence with \eqref{22} we get the third part of \eqref{1.2} for $q=p+1$.
The identity \eqref{8} now immediately gives
\begin{equation}\label{23}
S_p(q) \equiv\begin{cases}
-2 \pmod{p}, & \hbox{if $q$ odd};\\
-4 \pmod{p}, & \hbox{if $q$ even, $p+1\nmid q$};\\
-3 \pmod{p}, & \hbox{if $p+1\mid q$};
\end{cases}
\end{equation}
for $q\leq 2p$. It remains to show that \eqref{23} holds for all integers
$q\geq 1$. 

We are done if we can show that the sequence $\{S_p(q)\}_{q\geq 1}$, as given
in \eqref{23}, satisfies (for {\it all\/} $q$) the recurrence relation
$\pmod{p}$ whose characteristic polynomial is given by \eqref{10}; in other
words, we need to show that
\begin{equation}\label{24}
a_0S_p(n)+a_1S_p(n-1)+\ldots +a_{2p-3}S_p(n-2p+3) \equiv 0 \pmod{p}
\end{equation}
for all $n\geq 2p-2$, with the $a_j$ as given in Lemma~4. We may obviously
consider the sequence $\{-S_p(q)\}$, and since by \eqref{12} the coefficients
$a_0, a_1, \ldots, a_{2p-3}$ add up to $0\pmod{p}$, we may subtract a fixed
constant from all terms. Hence for a fixed prime $p\geq 3$ we are done if
we can show that
\begin{equation}\label{25}
a_0u_n+a_1u_{n-1}+\ldots +a_{2p-3}u_{n-2p+3} \equiv 0 \pmod{p}
\end{equation}
for all $n\geq 2p-2$, where
$$
u_q = -S_p(q)-3 = \begin{cases}
-1, & \hbox{if $q$ odd};\\
1, & \hbox{if $q$ even, $p+1\nmid q$};\\
0, & \hbox{if $p+1\mid q$}.
\end{cases}
$$
This means that $\{u_q\}_{q\geq 1}$ is the alternating sequence $(-1)^q$, with
1 subtracted whenever $p+1\mid q$. This is the motivation for computing the
alternating sum of all the $a_j$, which by \eqref{12} is
\begin{align*}
2\sum_{n=0}^{p-2}(-1)^na_n &= 2\sum_{m=0}^{\frac{p-3}{2}}(a_{2m}-a_{2m+1})
= 2\sum_{m=0}^{\frac{p-3}{2}}\bigl((m+1)^2-(m+1)(m+2)\bigr) \\
&= -2\sum_{m=1}^{\frac{p-1}{2}}m = -\frac{(p-1)(p+1)}{4},
\end{align*}
so that
\begin{equation}\label{26}
\sum_{n=0}^{2p-3}(-1)^na_n \equiv \frac{1}{4} \pmod{p}.
\end{equation}
Now, if $n$ is between $k(p+1)$ (for some $k$) and $k(p+1)+p-4$, then in the
finite sequence of indices $n-2p+3, n-2p+4,\ldots, n-1, n$, there are 
exactly two multiples of $p+1$. 

First, if $n=k(p+1)+j$ is even, with $0\leq j\leq p-4$,
then we have to subtract $a_j+a_{p+1+j}$ from \eqref{26} since $u_n$ and
$u_{n-p-1}$ are 0 instead of 1.
Since $n$ is even, $j$ is also even, say $j=2m$, and so by \eqref{11} we have 
$a_j\equiv (m+1)^2\pmod{p}$, while by \eqref{12} and \eqref{11},
\begin{align*}
a_{p+1+j} &\equiv -a_{p-4-j} 
\equiv -\left(\frac{p-5-2m}{2}+1\right)\left(\frac{p-5-2m}{2}+2\right) \\
&\equiv -\bigl((m+1)+\tfrac{1}{2}\bigr)\bigl((m+1)-\tfrac{1}{2}\bigr) \\
&= -(m+1)^2+\tfrac{1}{4} \equiv -a_j +\tfrac{1}{4} \pmod{p},
\end{align*}
so that by \eqref{26} we have
\begin{equation}\label{27}
\sum_{n=0}^{2p-3}(-1)^na_n -a_j - a_{p+1+j} \equiv 0 \pmod{p}.
\end{equation}

Second, if $n$ is odd, we have to add $a_j+a_{p+1+j}$ to \eqref{26} since
$u_n$ and $u_{n-p-1}$ are 0 instead of $-1$. Since $n$ is odd, so is $j$, 
say $j=2m+1$, and so by \eqref{11} we have $a_j\equiv (m+1)(m+2)\pmod{p}$,
while by \eqref{12} and \eqref{11},
$$
a_{p+1+j}\equiv -a_{p-4-j}\equiv -\left(\frac{p-5-2m}{2}+1\right)^2
\equiv -\bigl(m+\tfrac{3}{2}\bigr)^2 \pmod{p},
$$
so that
$$
a_j+a_{p+1+j} \equiv -\tfrac{1}{4} \pmod{p},
$$
and thus with \eqref{26} we have
$$
\sum_{n=0}^{2p-3}(-1)^na_n +a_j + a_{p+1+j} \equiv 0 \pmod{p}.
$$
This, together with \eqref{27}, means that \eqref{25} holds for $n=k(p+1)+j$,
$0\leq j\leq p-4$.

It remains to consider the case $p-3\leq j\leq p$; in this case there is
only one multiple of $p+1$ among the indices $n-2p+3,\ldots, n-1, n$, and we
have to add or subtract $a_j$, $p-3\leq j\leq p$, to, resp.\ from \eqref{26}.
Due to the ranges for which \eqref{11} and \eqref{12} are valid, all four 
cases need to be considered separately, namely
\begin{align*}
a_{p-3} &\equiv \left(\frac{p-3}{2}+1\right)^2 \equiv \tfrac{1}{4} \pmod{p},\\
a_{p-2} &\equiv \left(\frac{p-3}{2}+1\right)\left(\frac{p-3}{2}+2\right)
\equiv -\tfrac{1}{4} \pmod{p},\\
a_{p-1} &\equiv -a_{p-2} \equiv \tfrac{1}{4} \pmod{p},\\
a_p &\equiv -a_{p-3} \equiv -\tfrac{1}{4} \pmod{p}.
\end{align*}
Now with \eqref{26} we obtain
$$
\sum_{n=0}^{2p-3}(-1)^na_n \pm a_j \equiv 0 \pmod{p}.
$$
where the sign is chosen according to the parity of $j$, just as in the 
previous case.

Altogether, we have shown that the recurrence relation \eqref{25} is always
satisfied, and this completes the proof.



\begin{thebibliography}{25}

\bibitem{Ba} P.~Bachmann, {\it Niedere Zahlentheorie. Zweiter Teil\/}.
B.~G.~Teubner, Leipzig, 1910. Reprinted as two volumes in one, Chelsea, 1968.

\bibitem{Di} L.~E.~Dickson, {\it History of the Theory of Numbers\/}, Vol.~1,
Chelsea, 1919.

\bibitem{Dil} K.~Dilcher, On multiple zeros of Bernoulli polynomials,
preprint, 2007.

\bibitem{Gr} A.~Granville, Arithmetic properties of binomial coefficients.
I. Binomial coefficients modulo prime powers. {\it Organic Mathematics\/}
(Burnaby, BC, 1995), 253--276, CMS Conf. Proc., 20, Amer. Math. Soc.,
Providence, RI, 1997.

\bibitem{Go} H.~W.~Gould, {\it Combinatorial Identities\/},
revised edition, Gould Publications, Morgantown, W.Va., 1972.

\bibitem{He} Ch.~Hermite, Extrait d'une lettre \`a M. Borchardt, 
{\it J. Reine Angew. Math.} {\bf 81} (1876), 93--95.

\bibitem{HW} G.~H. Hardy and E.~M. Wright, {\it An Introduction to the
Theory of Numbers\/}, fifth ed., Oxford University Press, 1979.

\bibitem{Ku} E.~E.~Kummer, \"Uber die Erg\"anzungss\"atze zu den
allgemeinen Reciprocit\"atsgesetzen, {\it J. Reine Angew. Math.} {\bf 44}
(1852), 93--146.

\bibitem{Lu} E.~Lucas, Sur les congruences des nombres eul\'eriens et
des coefficients diff\'erentiels des fonctions trigonom\'etriques, suivant
un module premier, {\it Bull. Soc. Math. France} {\bf 6} (1878), 49--54.

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

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent {\it Keywords}: Binomial sums, binomial coefficients, congruences.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A002620} and \seqnum{A007318}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 22 2007;
revised version received  October 4 2007.
Published in {\it Journal of Integer Sequences}, October 5 2007.

\bigskip
\hrule
\bigskip

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


\end{document}