\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\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>n+1$.
Suppose that either $n$ is odd and $\{a_k\}\in \calS_-$, or $n$ is even and $\{a_k\}\in \calS_{+}$.
Then
\[
\sum_{0n+1$.
\begin{cor}\label{cor:main}
Let $n$ be a positive integer, and let $p$ be a prime such that $p>n+1$.
Suppose that $\{a_k\}\in \calS_{-}$ if $n$ is odd,
and that $\{a_k\}\in \calS_{+}$ if $n$ is even.
Then
\[
\sum_{00$ 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>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 k0}(-y)^n\sum_{00$, by expanding
\begin{align*}
\binom{y}{k}
&=
\frac{y}{k}\binom{y-1}{k-1}
=
\frac{(-1)^{k-1}y}{k}\prod_{0*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>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>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 $0n+1$.
Then we have the polynomial congruence
\[
\sum_{0\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\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>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}
&\equiv
\frac{p(n+1)}{2}
\sum_{k=1}^{p-1} H_{k-1}^{(n)}\frac{u_{p-k}}{k}
\pmod{p^3}
\\&
\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>j+2$ we have
\[
H_{p-1}^{(j)}\equiv
\begin{cases}
0\pmod{p^2},
&\text{if $j$ is odd,}
\\[.4em]
-\dfrac{p}{j+1}\,B_{p-j-1}\pmod{p^2},
&\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}
&\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}
\\&
\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}
*