<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}  

\usepackage{pstricks,pst-node,pst-tree}


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

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

\def\ds{\displaystyle}
\def\sign{\mbox{sign}}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}


\newcommand{\leg}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
\newcommand{\fraz}[2]{\genfrac{\{}{\}}{}{}{#1}{#2}}

\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\eps}{\varepsilon}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}


\begin{document}

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

\begin{center}
\vskip 1cm
{\LARGE\bf Congruences of Multiple Sums Involving \\
\vskip .05in
Sequences Invariant Under the Binomial \\
\vskip .15in
Transform}
\vskip 1cm
\large
Sandro Mattarei \\
Dipartimento di Matematica \\
Universit\`a di Trento \\
via Sommarive, 14\\
38100 Trento, Italy\\
{\href{mailto:mattarei@science.unitn.it}{\tt mattarei@science.unitn.it} }\\
\ \\
Roberto Tauraso \\
Dipartimento di Matematica \\
Universit\`a di Roma ``Tor Vergata'' \\
via della Ricerca Scientifica\\
00133 Roma, Italy\\
{\href{mailto:tauraso@mat.uniroma2.it}{\tt tauraso@mat.uniroma2.it} }
\end{center}

\vskip .2 in
\begin{abstract}
We prove several congruences modulo a power of a prime, such as
\[
\sum_{0&lt;k_1&lt;\cdots&lt;k_{n}&lt;p}\leg{p-k_{n}}{3}
\frac{(-1)^{k_{n}}}{k_1\cdots k_{n}}\equiv
\begin{cases}\displaystyle
-\frac{2^{n+1}+2}{6^{n+1}}\,p\,B_{p-n-1}\left({1/3}\right)
\pmod{p^2}, &amp;\text{if $n$ is odd,}
\\[.8em]
\displaystyle
-\frac{2^{n+1}+4}{n6^n}\,B_{p-n}\left({1/3}\right)
\pmod{p}, &amp;\text{if $n$ is even,}
\end{cases}
\]
where $n$ is a positive integer and $p$ is a prime such that $p&gt;\max(n+1,3)$.
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The classical binomial inversion formula states that the linear transformation
of sequences
\[
T(\{a_n\})=\left\{\sum_{k=0}^{n} {n\choose k}(-1)^{k} a_{k}\right\}
\]
is an involution, which means that $T\circ T$ is the identity map.
Thus, $T$ can only have two eigenvalues: $1$ and $-1$.
Denote by $\calS_+$ and $\calS_{-}$ the eigenspaces corresponding
to the eigenvalue $1$ and to the eigenvalue $-1$.
These eigenspaces contain many well-known sequences, among which are
\begin{gather*}
\{2,1,1,1,\ldots\},\;
\{2^{-n}\},\;
\{L_{n}\},\;
\{(-1)^n B_{n}\},\;
\{1/(n+1)\},\;
\left\{\binom{2n}{n}4^{-n}\right\}\in  \calS_{+},
\\
\{0,1,1,1,\ldots\},\;
\{2^n-(-1)^n\},\;
\{F_n\},\;
\left\{(-1)^n\leg{n}{3}\right\}\in \calS_{-}.
\end{gather*}
Here $\{F_n\}$, $\{L_n\}$, $\{B_n\}$ denote
the Fibonacci, Lucas and Bernoulli numbers.
For a more detailed analysis of the properties of $ \calS_{+}$ and $ \calS_{-}$
we refer the reader to the papers of Sun~\cite{Sunzh:01} and Wang~\cite{Wa:05}.
From now on we will use the subscript $k$ rather than the more traditional $n$, which takes another meaning here.

In this note we present several congruences
of multiple harmonic sums with coefficients involving these invariant sequences.
Our main result is the following.

\begin{thm}\label{thm:main}
Let $n$ be a positive integer, and let $p$ be a prime such that $p&gt;n+1$.
Suppose that either $n$ is odd and $\{a_k\}\in \calS_-$, or $n$ is even and $\{a_k\}\in \calS_{+}$.
Then
\[
\sum_{0&lt;k_1&lt;\cdots&lt;k_{n}&lt;p}
\frac{a_{p-k_{n}}-a_0/2}{k_1\cdots k_{n}}
\equiv
\frac{p(n+1)}{2}\, \sum_{0&lt;k_1&lt;\cdots&lt;k_{n+1}&lt;p}
\frac{a_{p-k_{n+1}}-a_0/2}{k_1\cdots k_{n+1}}\pmod{p^3}.
\]
\end{thm}

The term $a_0/2$ in the congruence is immaterial when $n$ is odd, because
all sequences in $\calS_-$ satisfy $a_0=0$.
Note that in the extremal case $n=p-2$, whence $n$ is odd, the congruence is actually an equality,
because $a_1=a_2$ for $\{a_k\}\in\calS_-$ and
\[
\sum_{0&lt;k_1&lt;\cdots&lt;k_{p-2}&lt;p}
\frac{a_{p-k_{p-2}}}{k_1\cdots k_{p-2}}
=
\frac{a_1}{(p-1)!}
\sum_{0&lt;k&lt;p}k
=
\frac{p(p-1)}{2}
\cdot\frac{a_1}{(p-1)!}.
\]

The following result is an immediate application of Theorem~\ref{thm:main}
and, in case $n$ is even, the simple fact that
$\sum_{0&lt;k_1&lt;\cdots&lt;k_{n}&lt;p}
1/(k_1\cdots k_{n})\equiv 0$ (mod $p$)
for $p&gt;n+1$.

\begin{cor}\label{cor:main}
Let $n$ be a positive integer, and let $p$ be a prime such that $p&gt;n+1$.
Suppose that $\{a_k\}\in \calS_{-}$ if $n$ is odd,
and that $\{a_k\}\in \calS_{+}$ if $n$ is even.
Then
\[
\sum_{0&lt;k_1&lt;\cdots&lt;k_{n}&lt;p}
\frac{a_{k_1}}{k_1\cdots k_{n}}
\equiv
-\sum_{0&lt;k_1&lt;\cdots&lt;k_{n}&lt;p}
\frac{a_{p-k_n}}{k_1\cdots k_{n}}
\equiv
0 \pmod{p}.
\]
\end{cor}

The first congruence in Corollary~\ref{cor:main} is obtained by applying the simultaneous substitution
$k_i\mapsto p-k_{n+1-i}$ to the summation indices, and so our real contribution is the second congruence.
That congruence was proved by Zhao and Sun~\cite{ZhSuzw:09} for the special case of the sequence
$\{a_k\}=\left\{(-1)^k\leg{k}{3}\right\}\in\calS_-$
and, in a different but essentially equivalent form, of the sequence
$\{a_k\}=\left\{(-1)^k\left(\leg{k+1}{3}-\leg{k-1}{3}\right)\right\}\in\calS_+$.
The method used by Zhao and Sun~\cite{ZhSuzw:09} can easily be adapted to deduce the validity of Corollary~\ref{cor:main}
for all sequences in $\calS_\pm$ which satisfy a second-order linear recurrence,
but our proof does not need this restriction.

In Section~\ref{sec:polynomial} we prove a polynomial congruence, stated in Lemma~\ref{lemma:Gg},
which reduces the evaluation modulo $p$ of multiple harmonic sums (with coefficients,
such as those involved in the above results) to certain single sums.
We show that another polynomial congruence, which is the crucial result of Zhao and Sun~\cite{ZhSuzw:09},
can be easily deduced from ours.
However, our congruence is more versatile, and we exploit it in the final section together with Theorem~\ref{thm:main} to prove the congruences involving
Bernoulli numbers stated in the abstract, and another matching pair of congruences with the parity of $n$ reversed.
These congruences both refine (modulo $p^2$) and complement (covering the case where $n$ has the opposite parity) the congruences proved
by Zhao and Sun~\cite{ZhSuzw:09}.

In the final Section~\ref{sec:Bernoulli}, after determining all sequences in $\calS_\pm$ which are (eventually) periodic,
we use Theorem~\ref{thm:main} and the tools developed in Section~3
to prove the pair of congruences stated in the abstract, and a naturally matching pair of congruences.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proof of Theorem~\ref{thm:main}}\label{sec:main}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

For the reader's benefit we recall some general information on the binomial transform.
Of course this can also be found in various sources, including papers of Prodinger, Sun and Wang~\cite{Pr:94,Sunzh:01,Wa:05}.
If $A(x)=\sum_{k\ge 0}a_kx^k$ is the ordinary generating function of the sequence $\{a_k\}$,
then it is easy to see that its binomial transform $T(\{a_k\})$ has generating sequence
$\frac{1}{1-x}A\left(\frac{x}{x-1}\right)$, and so $\{a_k\}\in\calS_\pm$
if and only if
\begin{equation}\label{eq:S+-}
\frac{1}{1-x}A\left(\frac{x}{x-1}\right)=\pm A(x).
\end{equation}
After applying the substitution $x=2y/(y-1)$
this condition takes the more symmetric form
\[
\frac{1}{1-y}A\left(\frac{-2y}{1-y}\right)=\pm
\frac{1}{1+y}A\left(\frac{2y}{1+y}\right).
\]
The left-hand side of this equation is the generating function of an associated sequence $\{b_k\}$=$T(\{2^ka_k\})$,
the binomial transform of $\{2^ka_k\}$.
We conclude that $\{a_k\}\in\calS_\pm$ occurs exactly when that generating sequence is an even or an odd function, respectively.
Equivalently, $\{a_k\}\in\calS_\pm$ occurs if and only if all odd-numbered terms $b_{2k+1}$, respectively all even-numbered terms $b_{2k}$,
of the associated sequence, vanish.
This statement is an equivalent formulation of a result of Sun~\cite[Corollary~3.3]{Sunzh:01}, but the above proof
avoids use of exponential generating functions, which was made by Sun~\cite{Sunzh:01} after a suggestion of Prodinger~\cite{Pr:94}.

After these preliminaries, our starting point is the following identity.

\begin{lem}\label{lemma:mn}
If $\{a_k\}\in \calS_\pm$, then for $m,n\geq 0$ we have
\[
\sum_{k=0}^{n}\left[{(m-1)n+k-1 \choose k}
\pm(-1)^{n-k}{m n \choose k}\right]a_{n-k}=0,
\]
where the sign is taken accordingly.
\end{lem}

\begin{proof}
The result can be obtained by taking $f_k={(m-1)n+k-1 \choose k}/{n\choose k}$ in the more general identity
\[
\sum_{k=0}^{n}{n\choose k}
\left[f_k\pm(-1)^{n-k} \sum_{i=0}^k {k\choose i}f_i\right]a_{n-k}=0,
\]
which holds for an arbitrary sequence $\{f_k\}\in\calS_{\pm}$, with sign in accordance, and was proved by Sun~\cite[Theorem~4.1]{Sunzh:01} by means of exponential generating functions (see also the paper of Wang~\cite{Wa:05}).
To make this paper self-contained we give a direct proof.
Denote by $[x^k]f(x)$ the coefficient of $x^k$ in the Laurent series $f(x)$.
Because
\[
{(m-1)n+k-1 \choose k}=[x^{k}]\frac{1}{(1-x)^{(m-1)n}}=
[x^{-1}]\frac{1}{x^{n+1}(1-x)^{(m-1)n}}\cdot x^{n-k}
\]
and
\[
(-1)^{n-k}{m n \choose k}=[x^{k}]\frac{(-1)^{n-k}}{(1-x)^{mn-k+1}}=
[x^{-1}]\frac{1}{x^{n+1}(1-x)^{(m-1)n+1}}\cdot \left(\frac{x}{x-1}\right)^{n-k},
\]
the left-hand side of the desired identity equals
\[
[x^{-1}]\frac{1}{x^{n+1}(1-x)^{(m-1)n}}\cdot
\left[A(x)\pm\frac{1}{1-x} A\left(\frac{x}{x-1}\right)\right],
\]
where $A(x)=\sum_{k\ge 0}a_kx^k$ is the generating function of the sequence $\{a_k\}$.
The conclusion now follows from Equation~\eqref{eq:S+-}.
\end{proof}

We define the {\em multiple harmonic sums} of order $n$ as
\[
H_r^{(n)}=\sum_{0&lt;k_1&lt;k_2&lt;\dots&lt;k_n\leq r}
\frac{1}{k_1 k_2 \cdots k_n},
\]
for $0&lt;n\le r$.
Interpreting the summation as ranging over the subsets of $\{1,\ldots,r\}$ of cardinality $n$,
it is natural and convenient to extend the definition to include order zero by setting
$H_r^{(0)}=1$ for $r\ge 0$,
and to stipulate that the sum vanishes unless $0\le n\le r$.
All congruences modulo powers of $p$ in this paper should be read in the ring of $p$-adic integers, thus admitting denominators prime to $p$.


\begin{proof}[Proof of Theorem~\ref{thm:main}]
Assume first that $n$ is odd and $\{a_k\}\in \calS_-$, where the proof is slightly simpler.
Because $a_0=0$ and $p$ is odd, according to Lemma~\ref{lemma:mn} we have
\[
\sum_{k=1}^{p-1}\left[\binom{(m-1)p+k-1}{k}
-(-1)^{k}{mp \choose k}\right]a_{p-k}=0.
\]
By expanding the binomial coefficients for $0&lt;k&lt;p$ we find
\[
\binom{(m-1)p+k-1}{k}=
\frac{(m-1)p}{k}\prod_{i=1}^{k-1}\left(1+\frac{(m-1)p}{i}\right)=
\frac{1}{k}\sum_{j\geq 1}\bigl((m-1)p\bigr)^jH_{k-1}^{(j-1)},
\]
and
\[
\binom{mp}{k}=\frac{mp}{k}(-1)^{k-1}\prod_{i=1}^{k-1}\left(1-\frac{mp}{i}\right)
=\frac{(-1)^k}{k}\sum_{j\geq 1}(-mp)^jH_{k-1}^{(j-1)}.
\]
Consequently, the numbers $S_j=\sum_{k=1}^{p-1}H_{k-1}^{(j-1)} a_{p-k}/k$
satisfy
\[
\sum_{j\geq 1}\bigl((m-1)^j-(-m)^j\bigr)\,p^jS_j=0
\]
for all nonnegative integers $m$.
Note that $S_j=0$ unless $1\le j\le p$.
Setting $f(x)=\sum_{j=1}^p p^jS_j(-x)^j$,
the above relations show that the polynomial $f(1-x)-f(x)$ vanishes for infinitely many values of $x$,
and hence is the zero polynomial.
After a translation, it follows that $f(1/2-x)-f(1/2+x)$ is the zero polynomial.
This means that the polynomial
$f(1/2-x)$
is invariant under the substitution $x\mapsto -x$, hence it is an even polynomial,
and so the coefficents of odd powers of $x$ vanish.
By expanding
\[
f\left(1/2-x\right)
=
\sum_{j\ge 1}p^jS_j\sum_n\binom{j}{n}(1/2)^{j-n}(-x)^n
=
\sum_n\left(\sum_{j\ge n}2^{n-j}p^jS_j\binom{j}{n}\right)(-x)^n,
\]
for each odd $n$ we obtain the congruence
\[
p^nS_n-\frac{1}{2}p^{n+1}(n+1)S_{n+1}
+\frac{1}{4}p^{n+2}\binom{n+2}{2}S_{n+2}
\equiv 0\pmod{p^{n+3}}.
\]
It follows, in particular, that $S_n\equiv 0\pmod{p}$ for each odd $n$, and hence
$S_{n+2}\equiv 0\pmod{p}$ as well.
Using this and the original congruence we conclude that
$2S_n\equiv p(n+1)S_{n+1}\pmod{p^3}$,
which is the desired conclusion.

Now consider the case where $n$ is even and $\{a_k\}\in \calS_+$.
Here Lemma~\ref{lemma:mn} yields
\[
\sum_{k=1}^{p-1}\left[{(m-1)p+k-1 \choose k}
+(-1)^{k}{mp \choose k}\right]a_{p-k}=-2a_p+\frac{1}{m}{mp \choose p}a_0.
\]
Expanding the binomial coefficients as in the first part of the proof we see
that the numbers $S_j=\sum_{k=1}^{p-1}H_{k-1}^{(j-1)} a_{p-k}/k$ satisfy
\[
\sum_{j\geq 1}\bigl((m-1)^j+(-m)^j\bigr)\,p^jS_j=-2a_p+\frac{1}{m}{mp \choose p}a_0
\]
for all nonnegative integers $m$.
Now consider the polynomial
\[
g(x)
=f(x)+a_p-\frac{a_0}{2}\binom{xp-1}{p-1}
=\sum_{j=1}^p p^jS_j(-x)^j +a_p-\frac{a_0}{2}\binom{xp-1}{p-1}.
\]
Note that
$\binom{xp-1}{p-1}=\binom{xp}{p}/x$
is a polynomial of degree $p-1$, and is invariant under the substitution $x\mapsto 1-x$.
Therefore, the relations found imply that $g(x)+g(1-x)$ vanishes for infinitely many values of $x$.
Hence $g(x)+g(1-x)$ is the zero polynomial, and hence so is $g(1/2+x)+g(1/2-x)$.
This means that the polynomial
$g(x+1/2)$
is an odd polynomial,
and so the coefficents of even powers of $x$ vanish.
Arguing as in the proof of part (i),
for each even $n&gt;0$ we obtain the congruence
\[
p^nS_n-\frac{1}{2}p^{n+1}(n+1)S_{n+1}
+\frac{1}{4}p^{n+2}\binom{n+2}{2}S_{n+2}
\equiv
[x^n]\,\frac{a_0}{2}\binom{(x+1/2)p-1}{p-1}
\pmod{p^{n+3}}.
\]
Because the right-hand side of this congruence depends only on the initial term $a_0$ of our sequence,
we can compute it by considering the special sequence
$a_k=(a_0/2)\cdot\{2,1,1,1,\ldots\}\in \calS_+$.
In this case we have $S_n=(a_0/2)H^{(n)}_{p-1}$, which is easily seen to vanish modulo $p$
as soon as $p&gt;n+1$,
for example by setting $x=1$ in Lemma 3.2 of the next section.
We conclude that
\[
S_n-\frac{1}{2}p(n+1)S_{n+1}\equiv \frac{a_0}{2}H^{(n)}_{p-1}-\frac{a_0}{4}p(n+1)H^{(n+1)}_{p-1}
\pmod{p^{3}},
\]
for an arbitrary sequence $\{a_k\}\in\calS_+$.
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Some polynomial congruences}\label{sec:polynomial}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The main result of this section is Lemma~\ref{lemma:Gg}, which shows that certain sums involving higher order harmonic numbers
are equivalent modulo $p$ to other sums which are easier to handle.
We first need a preliminary result.

\begin{lem}\label{lemma:exp}
For a positive integer $m$, the identity
\begin{equation*}%\label{eq:exp}
\sum_{0\le k&lt;m}\binom{y}{k}(-x)^k
=
1+\sum_{n&gt;0}(-y)^n\sum_{0&lt;k&lt;m}H^{(n-1)}_{k-1}\frac{x^k}{k}
\end{equation*}
holds in the polynomial ring $\Q[x,y]$ in two indeterminates.
\end{lem}

\begin{proof}
For $k&gt;0$, by expanding
\begin{align*}
\binom{y}{k}
&amp;=
\frac{y}{k}\binom{y-1}{k-1}
=
\frac{(-1)^{k-1}y}{k}\prod_{0&lt;i&lt;k}\left(1-\frac{y}{i}\right)
\end{align*}
we see that the coefficient of $y^n$ in the polynomial without constant term $\binom{y}{k}$ equals
\[
\frac{(-1)^{k+n}}{k}\sum_{0&lt;i_1&lt;\cdots&lt;i_{n-1}&lt;k}\frac{1}{i_1\cdots i_{n-1}}
=
\frac{(-1)^{k+n}}{k}H^{(n-1)}_{k-1},
\]
properly interpreted to equal $(-1)^{k-1}/k$ when $n=1$
(because the sum has a unique term, which is an empty product),
and to vanish when $n&gt;k$ (because the sum is empty).
The desired conclusion follows.
\end{proof}

\begin{lem}\label{lemma:Gg}
Let $n$ be a positive integer and let $p$ be a prime with $p&gt;n+1$.
Then we have the polynomial congruence
\begin{equation}\label{eq:Gg}
\sum_{k=1}^{p-1} H_{k-1}^{(n-1)}\frac{x^k}{k}
\equiv
(-1)^{n-1}\sum_{k=1}^{p-1}\frac{(1-x)^k}{k^n}
\pmod{p}.
\end{equation}
\end{lem}

The case $n=1$ of Lemma~\ref{lemma:Gg} is well known and due to the fact that
in this case the left-hand side is congruent modulo $p$ to the polynomial
$\bigl(1-x^p-(1-x)^p\bigr)/p$, which
is invariant under the substitution $x\mapsto 1-x$.
The general case can be proved by induction starting from this special case or,
more directly and perhaps more insightfully, as follows.

\begin{proof}
The left-hand side of the identity of Lemma~\ref{lemma:exp}
may be viewed as a polynomial in the indeterminate $y$ over the field of rational functions $\Q(x)$
(the field of quotients of $\Q[x]$).
Because of the binomial expansion, it takes the same values as the function $y\mapsto(1-x)^y$
when evaluated for $y=0,\ldots,m-1$.
Furthermore, having degree less than $m$ it is completely determined by those values,
for example through Lagrange's interpolation formula.

Over a field $E$ of characteristic $p$, and with $m=p$, Lagrange's interpolation formula takes a particularly nice shape:
for any polynomial $f(y)\in E[y]$ of degree less than $p$ we have
\[
f(y)=f(0)(1-y^{p-1})-\sum_{n=1}^{p-1}y^n\sum_{k\in\F_p^\ast}f(k)k^{-n}.
\]
In this special case the use of Lagrange's interpolation formula can be replaced by
direct verification: geometric summation shows that the polynomial
$\sum_{n=1}^{p-1}(y/k)^n$ takes the value $-1$ for $y=k$,
and vanishes on the remaining elements of $\F_p$.

By taking as $f$ the left-hand side of the identity of Lemma~\ref{lemma:exp}, with $m=p$,
viewed over the field $E=\F_p(x)$, we obtain
\[
\sum_{k=0}^{p-1}\binom{y}{k}(-x)^k
=
1-y^{p-1}-\sum_{n=1}^{p-1}y^n\sum_{k=1}^{p-1}(1-x)^k/k^n
\]
in the polynomial ring $E[y]$.
The conclusion now follows from Lemma~\ref{lemma:exp} by equating the coefficient of $y^n$ in both sides of this identity,
and rewriting the result as a congruence modulo $p$ in the polynomial ring
$\bigl(\Q(x)\bigr)[y]$.
\end{proof}

The polynomial at the right-hand side of congruence~\eqref{eq:Gg}
has some obvious roots in the prime field $\F_p$ for all primes $p&gt;n+1$, namely, $0$ and $1$, and also $2$ when $n$ is even.
This last fact occurs because the value modulo $p$ of that polynomial at $x=2$ is multiplied by $(-1)^{n-1}$ when replacing the summation variable $k$ with $p-k$.
By evaluating congruence~\eqref{eq:Gg} on $x=1$ we recover the basic fact that $H_{p-1}^{(n)}\equiv 0$ (mod $p$) for $0&lt;n&lt;p-1$.
Evaluation for $x=2$ yields
\begin{equation}\label{eq:sum:2*}
\sum_{0&lt;k_1&lt;\cdots&lt;k_n&lt;p}\frac{2^{k_n}}{k_1\cdots k_n}\equiv 0\pmod{p}
\end{equation}
for even $n$ with $0&lt;n&lt;p-1$.
Equation~(1.1) of Sun~\cite{Sunzw:09},
which reads $\sum_{0&lt;k&lt;p}H_k/(k2^k)\equiv 0\pmod{p}$,
follows from the special case $n=2$ of our Equation~\eqref{eq:sum:2*}
via the simple manipulation
\[
\sum_{0&lt;j\le k&lt;p}\frac{1}{jk2^k}
=\sum_{0&lt;j&lt;p}\frac{1}{j}\sum_{0&lt;k&lt;p}\frac{1}{k2^k}
-\sum_{0&lt;k&lt;j&lt;p}\frac{1}{jk2^k}
\equiv
\sum_{0&lt;j&lt;k&lt;p}\frac{1}{(p-j)(p-k)2^{p-k}}
\pmod{p}.
\]

We can use Lemma~\ref{lemma:Gg} to give a direct, rather than inductive proof, of the following crucial result of Zhao and Sun~\cite[Theorem~1.2]{ZhSuzw:09}.

\begin{cor}[Zhao and Sun~\cite{ZhSuzw:09}]\label{cor:ZhSu}
Let $n$ be a positive integer and let $p$ be a prime with $p&gt;n+1$.
Then we have the polynomial congruence
\[
\sum_{0&lt;k_1&lt;\cdots&lt;k_n&lt;p}\frac{(1-x)^{k_1}}{k_1\cdots k_n}
\equiv(-1)^{n-1}
\sum_{0&lt;k_1&lt;\cdots&lt;k_n&lt;p}\frac{x^{k_1}}{k_1\cdots k_n}
\pmod{p}.
\]
\end{cor}

\begin{proof}
After applying the simultaneous substitution
$k_i\mapsto p-k_{n+1-i}$ to the summation variables,
we invoke Lemma~\ref{lemma:Gg} with $x^{-1}$ in place of $x$ and obtain
\begin{align*}
\sum_{0&lt;k_1&lt;\cdots&lt;k_n&lt;p}\frac{x^{k_1}}{k_1\cdots k_n}
&amp;=
\sum_{0&lt;k_1&lt;\cdots&lt;k_n&lt;p}\frac{x^{p-k_n}}{(p-k_1)\cdots(p-k_n)}
\\&amp;
\equiv
(-1)^n
x^p
\sum_{0&lt;k_1&lt;\cdots&lt;k_n&lt;p}\frac{x^{-k_n}}{k_1\cdots k_n}
\\&amp;
\equiv
-x^p\sum_{k=1}^{p-1}\frac{(1-x^{-1})^k}{k^n}
\\&amp;
\equiv
-\sum_{k=1}^{p-1}\frac{(x-1)^kx^{p-k}}{k^n} \pmod{p}.
\end{align*}
If we apply the substitution $x\mapsto 1-x$ to this last polynomial we obtain
\[
\sum_{k=1}^{p-1}\frac{x^k(x-1)^{p-k}}{k^n}
=
\sum_{k=1}^{p-1}\frac{x^{p-k}(x-1)^k}{(p-k)^n}
\equiv
(-1)^n\sum_{k=1}^{p-1}\frac{(x-1)^kx^{p-k}}{k^n}
\pmod{p},
\]
which equals $(-1)^{n-1}$ times the original polynomial.
\end{proof}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Sums with periodic coefficient sequences}\label{sec:Bernoulli}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this final section we prove the pair of congruences stated in the abstract, and a naturally matching pair of congruences.
They concern multiple sums such as those in Theorem~\ref{thm:main} and Corollary~\ref{cor:main},
for special sequences $\{a_k\}$ of coefficients, which are periodic of period six.
The special significance of those sequences lies in the fact that, up to addition of multiples of the nearly constant sequences
$\{(1\pm 1),1,1,1,\ldots\}\in\calS_\pm$, they are the only (eventually) periodic sequences in $\calS_\pm$.
To prove this fact we start with some more general considerations on sequences in $\calS_\pm$
with a rational generating function.

Several sequences $\{a_k\}\in\calS_\pm$ of interest satisfy a linear recurrence.
It is well known that a sequence $\{a_k\}$ satisfies a linear recurrence exactly when its generating function
$A(x)=\sum_{k\ge 0}a_kx^k$ is a rational function.
If $\{a_k\}$ is any sequence with rational generating function $A(x)$,
then the generating function
$\frac{1}{1-x}A\left(\frac{x}{x-1}\right)$ of its binomial transform $T(\{a_k\})$
has a zero of multiplicity $s$ (or a pole of multiplicity $-s$ when $s$ is negative) at $\xi\in\C\setminus\{1\}$
if and only if $A(x)$ has a zero of the same multiplicity $s$ at $\xi/(\xi-1)=(1-\xi^{-1})^{-1}$.
The case $\xi=1$ is special, because the generating function of $T(\{a_k\})$ has a zero of multiplicity $s$ at $1$
if and only if $A(x)$ has a zero of multiplicity $s+1$ at $\infty$.
Recall that the multiplicity of $\infty$ as a zero of a rational function is the difference of the degrees of its denominator and numerator.
Because of Equation~\eqref{eq:S+-}, it follows that if $\{a_k\}\in\calS_\pm$ satisfies a linear recurrence, then
the multiplicity of $\xi\in\C\setminus\{1\}$
as a zero of its generating function $A(x)$ equals the multiplicity of $(1-\xi^{-1})^{-1}$,
and the multiplicity of $1$ is one less than the multiplicity of $\infty$.

Now consider a sequence $\{a_k\}\in {\cal S}_{\pm}$ which is eventually periodic, which means that
it satisfies, from some point on, a linear recurrence $a_{k+d}=a_k$ for some positive integer $d$.
Then its generating function $A(x)$ has the form $f(x)/(1-x^d)$, where $f(x)$ is a polynomial,
which has degree less than $d$ exactly when the sequence is periodic from the start.
Hence $A(x)$ has only simple poles, and at complex roots of unity.
However, the only roots of unity $\xi$ such that $\xi/(\xi-1)$ is also a root of unity
are the two primitive sixth roots of unity, which are the roots of the polynomial $1-x+x^2$.
The discussion in the previous paragraph shows that the poles of $A(x)$ can only occur at $1$ and at the primitive sixth roots of unity.
In particular, the sequence $\{a_k\}$ can only have period $1$ or $6$.
That discussion also shows that $f(x)$ has degree at most $d$, with equality if and only if
$1$ is a pole of $A(x)$.
In terms of the sequence $\{a_k\}$, this means that if it is eventually periodic then either it is periodic from the start,
or from its second term $a_1$.
In connection with our work, note that the first term $a_0$ of the sequence enters our Theorem~\ref{thm:main} only in one case,
and is immaterial in~Corollary~\ref{cor:main}.

We can now determine all sequences $\{a_k\}\in {\cal S}_{\pm}$ which are eventually periodic.
In fact, if such a sequence is not periodic from the start, it becomes so after adding to it
a suitable multiple of the sequence $\{(1\pm 1),1,1,1,\ldots\}\in\calS_\pm$,
with the effect of removing the pole at $1$ from its generating function $A(x)$.
Therefore, it suffices to consider a fully periodic sequence $\{a_k\}$.
Because the only poles of $A(x)$ are simple, and at the primitive sixth roots of unity,
we have $A(x)=\bigl((a_1-a_0)x+a_0\bigr)/(1-x+x^2)$.
Hence $\{a_k\}$ has period exactly six, and a simple calculation shows that
$A(x)$ is a scalar multiple of
\[
\frac{-x}{1-x+x^2}=\sum_{k=0}^{\infty}(-1)^k\leg{k}{3}x^k=-x-x^2+x^4+x^5+\cdots
\]
or
\[
\frac{2-x}{1-x+x^2}=\sum_{k=0}^{\infty}(-1)^k\left(\leg{k+1}{3}-\leg{k-1}{3}\right)x^k
=2+x-x^2-2x^3-x^4+x^5+\cdots,
\]
according as $\{a_k\}$ belongs to ${\cal S}_{-}$ or ${\cal S}_{+}$.

Now that we have shown the special significance of these sequences, we proceed to prove
the pair of congruences stated in the abstract, and a matching pair of congruences.

\begin{thm}\label{thm:Bernoulli}
Let $n$ be a positive integer and let $p$ be a prime with $p&gt;\max(n+1,3)$.
Consider the sequence in $\calS_-$ given by
$u_k=(-1)^k\leg{k}{3}$,
and the sequence in $\calS_+$ given by
$v_k=(-1)^k\left(\leg{k+1}{3}-\leg{k-1}{3}\right)$.
Let $B_m(x)$ denote the Bernoulli polynomials.
Then
\[
\sum_{0&lt;k_1&lt;\cdots&lt;k_{n}&lt;p}
\frac{u_{p-k_n}}{k_1\cdots k_{n}}\equiv
\begin{cases}\displaystyle
\frac{2^{n}+1}{3\cdot 6^{n}}\,p\,B_{p-n-1}\left({1/3}\right)
\pmod{p^2}, &amp;\text{if $n$ is odd,}
\\[.8em]
\displaystyle
\frac{2^{n+1}+4}{n6^n}\,B_{p-n}\left({1/3}\right)
\pmod{p}, &amp;\text{if $n$ is even,}
\end{cases}
\]
and
\[
\sum_{0&lt;k_1&lt;\cdots&lt;k_{n}&lt;p}
\frac{v_{p-k_n}}{k_1\cdots k_{n}}\equiv
\begin{cases}\displaystyle
\left(\frac{(2^n-1)(3^n-1)}{2\cdot 6^{n}}-{1\over n+1}\right)\,p\,B_{p-n-1}
\pmod{p^2}, &amp;\text{if $n$ is even,}
\\[1em]
\displaystyle
\frac{(2^{n-1}-1)(3^{n-1}-1)}{n 6^{n-1}}\,B_{p-n}
\pmod{p}, &amp;\text{if $n$ is odd.}
\end{cases}
\]
\end{thm}

\begin{proof}
We first prove the former pair of congruences, starting with the case where $n$ is even.
Let $\omega$ be a complex primitive cubic root of unity, and note that
$\leg{k}{3}=(\omega^k-\omega^{-k})/(\omega-\omega^{-1})$ for all $k$.
Interpreting congruences modulo $p$
in the ring $\Z[\omega]$ of Eisenstein integers,
Lemma~\ref{lemma:Gg} yields
\begin{align*}
\sum_{k=1}^{p-1} H_{k-1}^{(n-1)}\frac{u_{p-k}}{k}
&amp;=
\frac{1}{\omega-\omega^{-1}}\left(
(-\omega)^p\sum_{k=1}^{p-1} H_{k-1}^{(n-1)}\frac{(-\omega)^{-k}}{k}
-
(-\omega)^{-p}
\sum_{k=1}^{p-1} H_{k-1}^{(n-1)}\frac{(-\omega)^k}{k}
\right)
\\&amp;\equiv
\frac{(-1)^{n-1}}{\omega-\omega^{-1}}
\left(
(-\omega)^p\sum_{k=1}^{p-1}\frac{(-\omega)^k}{k^n}
-
(-\omega)^{-p}
\sum_{k=1}^{p-1}\frac{(-\omega)^{-k}}{k^n}
\right)\pmod{p}
\\&amp;=
-\sum_{k=1}^{p-1}\frac{u_{p+k}}{k^n},
\end{align*}
where we have used the fact that $1-(-\omega)^{-1}=-\omega$, in the second passage.
The coefficient $-u_{p+k}$ of $1/k^n$ in the last formula takes the values $0,1,1,0,-1,-1$
according as $p+k\equiv 0,1,2,3,4,5$ (mod $6$).
According to Sun~\cite[Lemma~2.1]{Sunzh:08} combined with Fermat's little theorem we have
\[
\sum_{\substack{0&lt;k&lt;p\\ k\equiv r\pmod{6}}}
\frac{1}{k^n}
\equiv \frac{1}{n6^n}\left(
B_{p-n}\left(\fraz{r}{6}\right)
-B_{p-n}\left(\fraz{r-p}{6}\right)\right)\pmod{p},
\]
for any integer $r$, under our hypothesis that $p&gt;\max(n+1,3)$.
Here $\{t\}=t-[t]$ denotes the fractional part of the real number $t$.
All the values of the Bernoulli polynomials involved in this formula can be obtained from just one of them,
using the fact that the Bernoulli polynomials satisfy the reflection property and
the multiplication formula
\[
B_m(1-x)=(-1)^m B_m(x),
\quad\text{and}\quad
B_m(ax)=a^{m-1} \sum_{k=0}^{a-1}B_m\left(x+k/a\right),
\]
for $m,a&gt;0$, see Ireland and Rosen~\cite[p.~248]{IrRo:90}.
Thus, taking into account that $p-n$ is odd we find
\begin{gather*}
B_{p-n}\left(0\right)=B_{p-n}\left({1/2}\right)=0,
\qquad
B_{p-n}\left({2/3}\right)=-B_{p-n}\left({1/3}\right),
\\
B_{p-n}\left({1/6}\right)=-B_{p-n}\left({5/6}\right)
=\left(2^{n-(p-1)}+1\right)B_{p-n}\left({1/3}\right).
\end{gather*}
Carrying out separate calculations according as $p\equiv\pm 1$ (mod $6$), in both cases we obtain
\[
-\sum_{k=1}^{p-1}\frac{u_{p-k}}{k^n}\equiv
\frac{2^{n+1}+4}{n6^n}\,B_{p-n}\left({1/3}\right) \pmod{p},
\]
which proves the case of our first pair of congruences where $n$ is even.
When $n$ is odd, the congruence which we have just proved holds with $n+1$ in place of $n$.
Combining this with Theorem~\ref{thm:main} we obtain
\begin{align*}
\sum_{k=1}^{p-1} H_{k-1}^{(n-1)}\frac{u_{p-k}}{k}
&amp;\equiv
\frac{p(n+1)}{2}
\sum_{k=1}^{p-1} H_{k-1}^{(n)}\frac{u_{p-k}}{k}
\pmod{p^3}
\\&amp;
\equiv \frac{2^{n+1}+2}{6^{n+1}}\,pB_{p-n-1}\left({1/3}\right)
\pmod{p^2},
\end{align*}
which proves the other case of the first pair of congruences.

We deal with the second pair of congruences in an entirely similar manner, using the fact that
$\leg{k+1}{3}-\leg{k-1}{3}=\omega^k+\omega^{-k}$ for all $k$.
Here $-v_{p+k}$ takes the values $-2,-1,1,2,1,-1$
according as $p+k\equiv 0,1,2,3,4,5$ (mod $6$).
When $n$ is odd, whence $p-n$ is even, the values of the Bernoulli polynomial $B_{p-n}(x)$ involved are
\begin{gather*}
B_{p-n}\left({1/2}\right)=\left(2^{n-(p-1)}-1\right)B_{p-n},
\qquad
B_{p-n}\left({1/3}\right)=B_{p-n}\left({2/3}\right)=
\frac{3^{n-(p-1)}-1}{2}B_{p-n},
\\
B_{p-n}\left({1/6}\right)=B_{p-n}\left({5/6}\right)=
\frac{6^{n-(p-1)}-3^{n-(p-1)}-2^{n-(p-1)}+1}{2}B_{p-n},
\end{gather*}
all expressed in terms of the Bernoulli numbers $B_n=B_n(0)$.
Thus, when $n$ is odd we find
\[
\sum_{k=1}^{p-1} H_{k-1}^{(n-1)}\frac{v_{p-k}}{k}
\equiv
-\sum_{k=1}^{p-1}\frac{v_{p+k}}{k^n}
\equiv
\frac{(2^{n-1}-1)(3^{n-1}-1)}{n 6^{n-1}}\,B_{p-n}
\pmod{p}.
\]
When $n$ is even, this congruence holds with $n+1$ in place of $n$.
According to Zhou and Cai~\cite[Remark at p.~1332]{ZC:07}, for $p&gt;j+2$ we have
\[
H_{p-1}^{(j)}\equiv
\begin{cases}
0\pmod{p^2},
&amp;\text{if $j$ is odd,}
\\[.4em]
-\dfrac{p}{j+1}\,B_{p-j-1}\pmod{p^2},
&amp;\text{if $j$ is even.}
\end{cases}
\]
In combination with Theorem~\ref{thm:main}, noting that $v_0=2$, this yields
\begin{align*}
\sum_{k=1}^{p-1} H_{k-1}^{(n-1)}\frac{v_{p-k}}{k}
&amp;\equiv
\frac{p(n+1)}{2}
\sum_{k=1}^{p-1} H_{k-1}^{(n)}\frac{v_{p-k}}{k}+H^{(n)}_{p-1}-\frac{p(n+1)}{2}H^{(n+1)}_{p-1}
\pmod{p^3}
\\&amp;
\equiv
\frac{p}{2}\,\frac{(2^{n}-1)(3^{n}-1)}{6^{n}}\,B_{p-n-1}-\frac{p}{n+1}\,B_{p-n-1}
\pmod{p^2},
\end{align*}
as desired.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibitem{IrRo:90} K. Ireland, M. Rosen,
{\it A Classical Introduction to Modern Number Theory}, Springer, 1990.

\bibitem{Pr:94} H. Prodinger,
Some information about the binomial transform,
{\it Fibonacci Quart.} {\bf 32} (1994), 412--415.

\bibitem{Sunzh:01} Z. H. Sun,
Invariant sequences under binomial transformation,
{\it Fibonacci Quart.} {\bf 39} (2001), 324--333.

\bibitem{Sunzh:08} Z. H. Sun,
Congruences involving Bernoulli polynomials,
{\it Discrete Math.} {\bf 308} (2008), 71--112.

\bibitem{Sunzw:09} Z. W. Sun,
Arithmetic of harmonic numbers,
preprint {\sf arXiv:math.NT/0911.4433v4}.

\bibitem{Wa:05} Y. Wang,
Self-inverse sequences related to a binomial inverse pair,
{\it Fibonacci Quart.} {\bf 43} (2005), 46--52.

\bibitem{ZhSuzw:09} L. L. Zhao, Z. W. Sun,
Some curious congruences modulo primes,
{\it J. Number Theory} {\bf 130} (2010), 930--935.

\bibitem{ZC:07} X. Zhou and T. Cai,
A generalization  of a curious congruence on harmonic sums,
{\it Proc. Amer. Math. Soc.} {\bf 135} (2007), 1329--1333.


\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: }
binomial transform, multiple sum, congruence, Bernoulli polynomial.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}

\noindent Received November 5 2009;
revised version received April 16 2010.
Published in {\it Journal of Integer Sequences}, April 16 2010.

\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>