<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}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

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

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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
An Explicit Formula for Sums of Powers of \\ 
\vskip .1in
Integers in Terms of Stirling Numbers
}
\vskip 1cm
\large
Diffalah Laissaoui\\
Dr Yahia Far\`{e}s University of M\'{e}d\'{e}a\\
26000 M\'{e}d\'{e}a \\
Algeria\\
\href{mailto:laissaoui.diffalah74@gmail.com}{\tt laissaoui.diffalah74@gmail.com}\\
\ \\
Mourad Rahmani\\
Faculty of Mathematics\\
University of Sciences and Technology Houari Boumediene\\
P. O. Box 32 \\
El Alia \\
Bab Ezzouar \\
16111 Algiers\\
Algeria\\
\href{mailto:mrahmani@usthb.dz}{\tt mrahmani@usthb.dz}\\
\end{center}

\vskip .2 in

\newcommand{\olP}{\overline{P}}
\newcommand{\mW}{{\mathcal W}}
\newcommand{\mw}{{\mathcal L}}
\newcommand{\mS}{{\mathcal S}}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}

\vskip .2 in
\begin{abstract}
In this note we present an explicit formula for the sum of powers of
the first $n$ terms of a general arithmetic sequence in terms of
Stirling numbers. We then provide an algorithm for calculating the sum
of consecutive powers of integers.
\end{abstract}


\section{Introduction}

This paper is concerned with sums of $p$th powers of the first $n$ terms
of a general arithmetic sequence
\[
S_{p,\left(  a,d\right)  }\left(  n\right)  =a^{p}+\left(  a+d\right)
^{p}+\cdots+\left(  a+\left(  n-1\right)  d\right)  ^{p},\text{ }n\geq1
\]
where $p$ is a nonnegative integer,
and $a,d$ are complex numbers with $d\neq0$.
In particular, we have
\[
S_{p,\left(  1,1\right)  }\left(  n\right)  =1^{p}+2^{p}+3^{p}+\cdots+n^{p},
\]
which has been studied extensively by many authors.

The properties of $S_{p,\left(  a,d\right)  }\left(  n\right)  $
were obtained by Howard \cite{Howard1996} via the following generating
function
\begin{equation}
\mathcal{B}_{0}\left(  z\right)  :=
{\displaystyle\sum\limits_{p\geq0}}
S_{p,\left(  a,d\right)  }\left(  n\right)  \frac{z^{p}}{p!}=
{\displaystyle\sum\limits_{k=0}^{n-1}}
e^{\left(  a+kd\right)  z}.\label{L1}
\end{equation}
For recent articles on this subject, see \cite{BAsos,Merca,Schumacher}.

In this note we establish a generalization of the well-known formula \cite{KnuthB,Gould,Roman}
\[
S_{p,\left(  1,1\right)  }\left(  n\right)  ={\sum\limits_{k=0}^{p}}k!
\genfrac{\{}{\}}{0pt}{}{p}{k}
\dbinom{n+1}{k+1},\text{ }p\geq1.
\]
for the sums $S_{p,\left(  a,d\right)  }\left(  n\right)$. Also, we provide an algorithm for
calculating the sum of the $p$th powers of the first $n$ terms of a general
arithmetic sequence.

First we present some definitions and notations and some results that
will be useful in the rest of the paper. For $x\in\mathbb{C},$ the falling
factorial $\left(  x\right)  _{n}$ is defined by $\left(  x\right)
_{0}=1,\left(  x\right)  _{n}=x\left(  x-1\right)  \cdots\left(  x-n+1\right)
$ for $n&gt;0$. The generalized binomial coefficient is defined as follows:
\begin{displaymath}
\binom{x}{n} = \begin{cases}
\frac{\left(  x\right)_{n}}{n!}, &amp; \text{ if $n\geq0$};\\
0, &amp; \text{otherwise.}
\end{cases}
\end{displaymath}

The (signed) Stirling numbers of the first kind $s\left(  n,k\right)
$ are the coefficients in the expansion
\[
\left(  x\right)  _{n}=
{\displaystyle\sum\limits_{k=0}^{n}}
s\left(  n,k\right)  x^{k}
\]
and satisfy the recurrence relation
\begin{equation}
s\left(  n+1,k\right)  =s\left(  n,k-1\right)  -ns\left(  n,k\right)  \text{
for }1\leq k\leq n.\label{recst}
\end{equation}

The Stirling numbers of the second kind, denoted by $
\genfrac{\{}{\}}{0pt}{}{n}{k}
$, are the coefficients in the expansion
\[
x^{n}=
{\displaystyle\sum\limits_{k=0}^{n}}
\genfrac{\{}{\}}{0pt}{}{n}{k}
\left(  x\right)  _{k}.
\]
These numbers count the number of ways to partition a set of $n$
elements into exactly $k$ nonempty subsets.

For any positive integer $r$, the $r$-Stirling numbers of the second kind $
\genfrac{\{}{\}}{0pt}{}{n}{k}_{r}$ are obviously generalizations
of Stirling numbers of the second kind.
These numbers count the number of partitions of a set of $n$ objects into
exactly $k$ nonempty, disjoint subsets, such that the first $r$ elements are
in distinct subsets. The exponential generating function is given by
\[
{\sum\limits_{n\geq k}}
\genfrac{\{}{\}}{0pt}{}{n+r}{k+r}_{r}\frac{z^{n}}{n!}=\frac{1}{k!}e^{rz}\left(  e^{z}-1\right)  ^{k}.
\]
For more details about these numbers see \cite{Broder,KnuthB}.

\section{Main results}

First, we obtain the following result via the generalized Stirling
transform method.

\begin{theorem}
For all $n\geq1$, non-negative integer $p$ and complex numbers $a$ and $d$ $(d\neq0)$, we have
\begin{equation}
S_{p,\left(  a,d\right)  }\left(  n\right)  =d^{p}{\sum\limits_{k=0}^{p}}k!
\genfrac{\{}{\}}{0pt}{}{p}{k}
\left(  \dbinom{n+\frac{a}{d}}{k+1}-\dbinom{\frac{a}{d}}{k+1}\right)
.\label{FFF}
\end{equation}

\end{theorem}

\begin{proof}
Since
\[
S_{p,\left(  a,d\right)  }\left(  n\right)  =d^{p}S_{p,\left(  \frac{a}
{d},1\right)  }\left(  n\right)  ,
\]
we can investigate the sums $S_{p,\left(  \frac{a}{d},1\right)
}\left(  n\right)  $. It follows from (\ref{L1}) and \cite[Theorem 4]{Rahmani2014} that
\begin{align*}
\mathcal{A}_{0}\left(  z\right)   &amp;  ={\sum\limits_{m\geq0}}a_{0,m}
\dfrac{z^{m}}{m!}\\
&amp;  =\mathcal{B}_{0}\left(  \ln\left(  1+z\right)  \right)  \\
&amp;  =
{\displaystyle\sum\limits_{k=0}^{n-1}}
\left(  1+z\right)  ^{\frac{a}{d}+k}\\
&amp;  =
{\displaystyle\sum\limits_{m\geq0}}
\frac{z^{m}}{m!}
{\displaystyle\sum\limits_{k=0}^{n-1}}
\left(  \frac{a}{d}+k\right)  _{m}.
\end{align*}
Since
\[
{\displaystyle\sum\limits_{k=0}^{n}}
\left(  x+k\right)  _{m}:=\frac{\left(  x+n+1\right)  _{m+1}-\left(  x\right)
_{m+1}}{m+1},
\]
we can easily verify that
\begin{align}
a_{0,m} &amp;  =\left[  z^{m}\right]  \mathcal{A}_{0}\left(  z\right)  \\
&amp;  =m!\left(  \dbinom{n+\frac{a}{d}}{m+1}-\dbinom{\frac{a}{d}}{m+1}\right)
\label{AANN}
\end{align}
where $[z^{n}]f(z)=f_{n}$ denotes the operation of extracting the coefficient
of $z^{n}$ in the formal power series $f(z)=
{\displaystyle\sum\limits_{n}}
f_{n}\frac{z^{n}}{n!}$.

Now, from \cite[Corollary 1]{Rahmani2014} we get 
\begin{multline}
{\sum\limits_{k=0}^{m}}\frac{1}{d^{p+k}}s\left(  m,k\right)  S_{p+k,\left(
a,d\right)  }\left(  n\right)  =\label{Lai}\\
{\sum\limits_{k=0}^{p}}
\genfrac{\{}{\}}{0pt}{}{p+m}{k+m}_{m}\left(  m+k\right)  !\left(  \dbinom{n+\frac{a}{d}}{m+k+1}-\dbinom
{\frac{a}{d}}{m+k+1}\right)  .
\end{multline}
and the proof is completed by letting $m=0$ in the above identity.
\end{proof}

Setting $p=0$ in (\ref{Lai}), one obtains
the following recursive formula for the
sum of the $p$th powers of the first $n$ terms of a general arithmetic
sequence involving the Stirling numbers of the first kind:

\begin{corollary}
We have
\[
{\sum\limits_{k=0}^{m}}\frac{1}{d^{k}}s\left(  m,k\right)  S_{k,\left(
a,d\right)  }\left(  n\right)  =m!\left(  \dbinom{n+\frac{a}{d}}{m+1}
-\dbinom{\frac{a}{d}}{m+1}\right)  .
\]
\end{corollary}

Thus, for example, when $m=0,1,2,3$, we obtain
\begin{align*}
S_{0,\left(  a,d\right)  }\left(  n\right)   &amp;  =n,\\
S_{1,\left(  a,d\right)  }\left(  n\right)   &amp;  =d\left(  \dbinom{n+\frac
{a}{d}}{2}-\dbinom{\frac{a}{d}}{2}\right)  ,\\
-\frac{1}{d}S_{1,\left(  a,d\right)  }\left(  n\right)  +\frac{1}{d^{2}
}S_{2,\left(  a,d\right)  }\left(  n\right)   &amp;  =2\left(  \dbinom{n+\frac
{a}{d}}{3}-\dbinom{\frac{a}{d}}{3}\right)  ,\\
\frac{2}{d}S_{1,\left(  a,d\right)  }\left(  n\right)  -\frac{3}{d^{2}
}S_{2,\left(  a,d\right)  }\left(  n\right)  +\frac{1}{d^{3}}S_{3,\left(
a,d\right)  }\left(  n\right)   &amp;  =6\left(  \dbinom{n+\frac{a}{d}}{4}
-\dbinom{\frac{a}{d}}{4}\right)  .
\end{align*}

In the next paragraph, we propose an algorithm based on a three-term
recurrence relation for calculating the $p$th powers of the first $n$ terms
of a general arithmetic sequence $S_{p,\left(  a,d\right)  }\left(  n\right)
$. It is convenient to introduce the following sequence $A_{p,m}^{\left(
a,d\right)  }\left(  n\right)  $ with two indices by
\begin{equation}
A_{p,m}:=A_{p,m}^{\left(  a,d\right)  }\left(  n\right)  =\frac{S_{0,\left(
a,d\right)  }\left(  n\right)  }{a_{0,m}}{\sum\limits_{k=0}^{m}}\frac{1}
{d^{k}}s\left(  m,k\right)  S_{p+k,\left(  a,d\right)  }\left(  n\right)  ,
\label{ALgoo}
\end{equation}
with $A_{0,m}=n$ and $A_{p,0}=S_{p,\left(  a,d\right)  }\left(  n\right)  $.

\begin{theorem}
The sequence $A_{p,m}^{\left(  a,d\right)  }\left(  n\right)  $ satisfies the
following three-term recurrence relation
\begin{equation}
{A}_{p+1,m}=d\frac{a_{0,m+1}}{a_{0,m}}A_{p,m+1}+dm{A}_{p,m}, \label{star1}
\end{equation}
with the initial sequence $A_{0,m}=n,$ and $a_{0,m}$ is defined by $\left(
\ref{AANN}\right)  $.
\end{theorem}

\begin{proof}
From (\ref{ALgoo}) and $\left(  \ref{recst}\right)  ,$ we have
\begin{align*}
A_{p,m+1} &amp;  =\frac{n+1}{a_{0,m+1}}{\sum\limits_{k=0}^{m+1}}\frac{1}{d^{k}
}s\left(  m+1,k\right)  S_{p+k,\left(  a,d\right)  }\left(  n\right)  \\
&amp;  =\frac{n+1}{a_{0,m+1}}{\sum\limits_{k=1}^{m+1}}\frac{1}{d^{k}}\left(
s\left(  m,k-1\right)  -ms\left(  m,k\right)  \right)  S_{p+k,\left(
a,d\right)  }\left(  n\right)  .
\end{align*}
After some rearrangement, we get
\[
A_{p,m+1}=\frac{a_{0,m}}{da_{0,m+1}}{A}_{p+1,m}-\frac{a_{0,m}m}{a_{0,m+1}}
{A}_{p,m}.
\]
This completes the proof.
\end{proof}

As an immediate application of (\ref{star1}) we have the
following algorithm for evaluating
Faulhaber's formula $S_{p,\left(  1,1\right)
}\left(  n\right)  $. Starting with the sequence $R_{0,
m}:=n$, as the first row of the matrix $\left(
R_{p,m}\right)  _{p,m\geq0}$,
each entry is determined recursively by
\[
{R}_{p+1,m}=m{R}_{p,m}+\frac{\left(  m+1\right)  \binom{n+1}{m+2}}
{\binom{n+1}{m+1}-\delta_{0,m}}R_{p,m+1},
\]
where $\delta_{i,j}$ denotes the Kronecker symbol.

Then $R_{p,0}:=S_{p,\left(  1,1\right)  }\left(  n\right) $ is
Faulhaber's formula.

\section{Acknowledgments}
We thank the referee and the editor for helpful comments and suggestions.


\begin{thebibliography}{9}

\bibitem {BAsos}A. Bazs\'{o} and I. Mez\H{o}, On the coefficients of
power sums of arithmetic progressions. \emph{J. Number Theory} {\bf
153} (2015), 117--123.

\bibitem {Broder}A. Z. Broder, The $r$-Stirling numbers. \emph{Discrete
Math.} {\bf 49} (1984), 241--259.

\bibitem {KnuthB}R. L. Graham and D. E. Knuth and O. Patashnik, \emph{Concrete
Mathematics: A Foundation for Computer Science}, Addison-Wesley, 1994.

\bibitem {Howard1996}F. T. Howard, Sums of powers of integers via generating
functions. \emph{Fibonacci Quart.} {\bf 34} (1996), 244--256.

\bibitem {Gould} J. Quaintance and H. W. Gould. \emph{Combinatorial
Identities for Stirling Numbers: The Unpublished Notes of H. W. Gould},
World Scientific Publishing, 2016.

\bibitem {Merca}M. Merca, An alternative to Faulhaber's formula. \emph{Amer.
Math. Monthly} {\bf 122} (2015), 599--601.

\bibitem {Rahmani2014}M. Rahmani, Generalized Stirling transform.
\emph{Miskolc Math. Notes} {\bf 15} (2014), 677--690.

\bibitem{Schumacher} R. Schumacher, An extended version of Faulhaber's formula,
\emph{J. Integer Sequences} {\bf 19} (2016), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Schumacher/schu3.html}{Article 16.4.2}.

\bibitem{Roman} R. Witu{\l}a, K. Kaczmarek, P. Lorenc, E. Hetmaniok and
M. Pleszczynski, Jordan numbers, Stirling numbers and sums of
powers. \emph{Discuss. Math. Gen. Algebra Appl.} {\bf 34} (2014),
155--166.



\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 11B73; Secondary 11B37.

\noindent {\it Keywords}:  algorithm, explicit formula, Stirling
number, sums of powers of integers.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 26 2016;
revised version received February 24 2017. 
Published in {\it Journal of Integer Sequences}, February 24 2017.

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