\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://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 Generalized Akiyama-Tanigawa Algorithm for \\
\vskip .1in
Hypersums of Powers of Integers}
\vskip 1cm
\large
Jos\'{e} Luis Cereceda \\
Distrito Telef\'onica, Edificio Este 1 \\ 
28050 Madrid \\
Spain\\
\href{mailto:jl.cereceda@movistar.es}{\tt jl.cereceda@movistar.es}
\end{center}

\vskip .2 in

\begin{abstract}
In this paper we consider the hypersum polynomials, $P_k^{(m)}(n) =
\sum_{r=0}^{k+m+1} c_{k,m}^{r} n^r$, and give an explicit formula for
the coefficients $c_{k,m}^{r}$. We show that the $c_{k,m}^{r}$'s satisfy a
generalized Akiyama-Tanigawa recurrence relation, thus extending some
previous results due to Inaba. We also give a number of identities involving
the Stirling numbers of the first and second kinds, as well as Bernoulli and
harmonic numbers.
\end{abstract}


\section{Introduction}
\label{sec:1}

Akiyama and Tanigawa, in the course of their investigation of multiple zeta values at
non-positive integers \cite{AT}, found an algorithm to calculate the Bernoulli numbers in a
manner similar to Pascal's triangle for binomial coefficients. The Akiyama-Tanigawa
algorithm, as reformulated by Kaneko \cite{kaneko} and Chen \cite{chen}, is described
by the sequence $a_{k,m}$ defined recursively by
\begin{equation*}
a_{k,m} = (m+1) (a_{k-1,m} - a_{k-1,m+1}), \quad
k\geq 1, m\geq 0,
\end{equation*}
for a given initial sequence $a_{0,m}$, $m=0,1,2,\ldots\,$. If we start with
$a_{0,m} = 1/(m+1)$, then it can be shown \cite{kaneko} that the leading element
$a_{k,0}$ is the $k$-th Bernoulli number $B_k$ (with $B_1 = \tfrac{1}{2}$).

Later, Inaba \cite{inaba} considered hypersums of powers of integers and found that the
coefficient of the first-degree term in the hypersum polynomial coincides with the
element $a_{k,m}$ of the Akiyama-Tanigawa matrix. In this paper (Section \ref{sec:2}) we give an
explicit expression for the coefficients of the hypersum polynomials in terms of the Stirling
numbers of the first and second kinds. Moreover, in Section \ref{sec:3}, we derive a recursive
relationship for the hypersums. Based on this relationship, in Section \ref{sec:4} we show that
the coefficients of the hypersum polynomials satisfy a generalized Akiyama-Tanigawa recurrence
relation. Further, in Section \ref{sec:5}, as an illustration of the general theory, we give a
detailed treatment of the coefficient of the second-degree term in the hypersum polynomial,
and provide the general result for the third-degree term. We conclude in Section \ref{sec:6} with
a brief historical account of the work of Johann Faulhaber on power sums.


\section{Hypersums of powers of integers}
\label{sec:2}

Using Inaba's notation \cite{inaba}, the hypersums of powers of integers are defined
recursively as
\begin{equation*}
P_k^{(m)}(n) = \sum_{j=1}^n P_k^{(m-1)}(j), \qquad m\geq 1,
\end{equation*}
where $P_k^{(0)}(n)$ is the sum of the first $n$ positive integers
each raised to the integer power $k \geq 0$, $P_k^{(0)}(n) =
1^k +2^k +3^k +\cdots +n^k$. There exist several formulations for $P_k^{(0)}(n)$
(see, for instance, \cite{kotiah}). A convenient formula for our purposes is
given in terms of the Stirling numbers of the second kind
$S(k,i)$ (Sloane's \seqnum{A008277} \cite{sloane})
\begin{equation*}
P_k^{(0)}(n) = \sum_{i=1}^k i! {n+1 \choose i+1}
S(k,i), \qquad k \geq 1,
\end{equation*}
with ${n+1 \choose i+1} =0$ for $n <i$. A detailed derivation of this formula appears,
for example, in the article \cite{pfaff}. For hypersums of arbitrary order $m$ this formula
generalizes to
\cite{inaba}
\begin{equation}\label{orderm}
P_k^{(m)}(n) = \sum_{i=1}^k i! {n+m+1 \choose
i+m+1} S(k,i), \qquad k\geq 1.
\end{equation}
In addition, for $k=0$, $P_0^{(m)}(n)$ turns out  to be
\begin{equation}\label{k0}
P_0^{(m)}(n) = {n+m \choose m+1}.
\end{equation}
From (\ref{orderm}), it is readily seen that $P_k^{(m)}(n)$ is a polynomial in $n$ of degree
$k+m+1$ with constant term zero. This follows from the fact that each ${n+m+1 \choose
i+m+1}$ can be expanded as a polynomial in $n$ of degree $i+m+1$, and that the maximum value taken
by $i$ is $k$. Further, from (\ref{orderm}) we get $P_k^{(m)}(0) =0$ since ${m+1 \choose i+m+1}$
is zero for each $1 \leq i \leq k$. Thus $P_k^{(m)}(n)$ admits a polynomial representation of the form
\begin{equation}\label{poly}
P_k^{(m)}(n) = \sum_{r=0}^{k+m+1} c_{k,m}^{r}
n^r,\end{equation}
with $c_{k,m}^{0} =0$ for all $k$ and $m$.

The following proposition gives us an explicit formula for the coefficients $c_{k,m}^{r}$. From now on,
$|s(r,t)|$ will denote the (unsigned) Stirling numbers of the first kind, also known as Stirling
cycle numbers. (The Stirling numbers of the first kind (signed) are given by $s(r,t) =
(-1)^{r-t}|s(r,t)|$, see \seqnum{A008275} in \cite{sloane}.)

\begin{proposition}\label{prop:1}
For $k=0$ and $1 \leq r \leq m+1$, we have
\begin{equation}\label{p1a}
c_{0,m}^{r} = \frac{1}{(m+1)!} C(m,r),
\end{equation}
where
\begin{equation}\label{p1b}
C(m,r) = \sum_{t=r}^{m+1} (-1)^{m+1-t} |s(m+1,t)| {t \choose r} m^{t-r} .
\end{equation}
On the other hand, for $k \geq 1$ and $1 \leq r \leq m+k+1$, $c_{k,m}^{r}$ is given by
\begin{equation}\label{p1c}
c_{k,m}^{r} = \sum_{i=\text{max}\{1,r-m-1\}}^{k} \frac{i!}{(i+m+1)!} C(i,m,r) S(k,i),
\end{equation}
where
\begin{equation}\label{p1d}
C(i,m,r) = \sum_{t=r}^{i+m+1} (-1)^{i+m+1-t}
|s(i+m+1,t)| {t \choose r} (m+1)^{t-r}.
\end{equation}
\end{proposition}

\begin{proof}
Let us first prove relation (\ref{p1c}). For that, write the hypersum $P_k^{(m)}(n)$ in 
(\ref{orderm}) as
\begin{equation*}
P_k^{(m)}(n) = \sum_{i=1}^{k} \frac{i!}{(i+m+1)!}
[n+m+1]_{i+m+1} S(k,i),
\end{equation*}
where $[n]_k$ denotes the falling factorial $n(n-1)(n-2)\cdots (n-k+1)$. Considering $n$ as
a variable, $[n+m+1]_{i+m+1}$ can be regarded as a polynomial in $n$ of degree $i+m+1$.
Therefore, to prove (\ref{p1c}) it suffices to show that the coefficient of the $r$-degree term in
$[n+m+1]_{i+m+1}$ is equal to $C(i,m,r)$. But, by definition of the Stirling numbers of the first
kind in terms of the falling factorial, $[n+m+1]_{i+m+1}$ can be expressed as
\begin{equation*}
[n+m+1]_{i+m+1} = \sum_{t=1}^{i+m+1}
(-1)^{i+m+1-t} |s(i+m+1,t)| (n+m+1)^t.
\end{equation*}
Furthermore, by the binomial theorem we have
\begin{equation*}
(n+m+1)^t = \sum_{r=0}^t {t \choose r} n^r
(m+1)^{t-r},
\end{equation*}
and then the $r$-degree coefficient in $(n+m+1)^t$ is ${t \choose r} (m+1)^{t-r}$, from which
we in turn deduce that the $r$-degree coefficient in $[n+m+1]_{i+m+1}$ is just $C(i,m,r)$. Moreover,
since $C(i,m,r) =0$ for $i+m+1 < r$, we can restrict the summation in (\ref{p1c}) to the values
$i =1,\ldots,k$ if $r-m \leq 1$, or else to the values $i = r-m-1,\ldots,k$ if $r-m \geq 2$.

Similarly, to prove (\ref{p1a}), we first note that (\ref{k0}) can be written as
\begin{equation*}
{n+m \choose m+1} = \frac{[n+m]_{m+1}}{(m+1)!}.
\end{equation*}
As before, $[n+m]_{m+1}$ can be expanded as
\begin{equation*}
[n+m]_{m+1} = \sum_{t=1}^{m+1} (-1)^{m+1-t}
|s(m+1,t)| (n+m)^{t}.
\end{equation*}
Since the $r$-degree coefficient of
$(n+m)^t$ is ${t \choose r} m^{t-r}$ we conclude that the
$r$-degree coefficient in $[n+m]_{m+1}$ is equal to $C(m,r)$,
and hence the proof of (\ref{p1a}) is done.
\end{proof}

Next we give an alternative, closed formula for $c_{0,m}^{r}$ that will be used later when we
discuss the generalized Akiyama-Tanigawa algorithm in Section \ref{sec:4}.

\begin{proposition}\label{prop:2}
For $1 \leq r \leq m+1$
\begin{equation}\label{closed}
c_{0,m}^{r} = \frac{|s(m+1,r)|}{(m+1)!}.
\end{equation}
\end{proposition}

\begin{proof} This follows immediately when we write ${n+m \choose m+1}$ as
\begin{equation*}
{n+m \choose m+1} = \frac{[n]^{m+1}}{(m+1)!},
\end{equation*}
where $[n]^{k}$ denotes the rising factorial $n(n+1)(n+2)\cdots (n+k-1)$. To prove
the proposition we have to show that $|s(m+1,r)|$ constitutes the $r$-degree term of
$[n]^{m+1}$. But, from the algebraic definition of the (unsigned) Stirling numbers of the
first kind in terms of the rising factorial, we have that
\begin{equation*}
[n]^{m+1} = \sum_{r=1}^{m+1} |s(m+1,r)| n^r,
\end{equation*}
and thus relation (\ref{closed}) is proved.
\end{proof}

A direct consequence of (\ref{closed}) is that, for any given $r$, all the coefficients
$c_{0,m}^{r}$ ($m=0,1,2,\ldots $) are non-negative. On the other hand, from (\ref{p1c})
and (\ref{p1d}) we quickly deduce the leading coefficient of $P_k^{(m)}(n)$,
\begin{equation}\label{lc}
c_{k,m}^{k+m+1} = \frac{k!}{(k+m+1)!} ,
\end{equation}
which applies to all $k \geq 0$ and $m \geq 0$. Note that, as expected, for $m =0$ we retrieve the
well-known result $c^{k+1}_{k,0} = \frac{1}{k+1}$. In addition to $c_{k,m}^{k+m+1}$, from (\ref{p1c})
and (\ref{p1d}) we can also obtain closed-form expressions for the successive high-degree coefficients
of $P_k^{(m)}(n)$. Here we give the resultant formulas for the first five trailing coefficients next to
$c_{k,m}^{k+m+1}$:
\begin{align}\label{highd}
c^{k+m}_{k,m} & = \frac{k!}{(k+m)!} \,  \frac{m+1}{2} , \quad k\geq 1,  m\geq  0,  \notag \\
c^{k+m-1}_{k,m} & = \frac{k!}{(k+m-1)!} \, \frac{(m+1)(3m+2)}{24} , \quad k\geq 2,  m\geq  0,  \notag \\
c^{k+m-2}_{k,m} & =  \frac{k!}{(k+m-2)!} \, \frac{m (m+1)^2}{48} , \quad k\geq 3,  m\geq  0,  \\
c^{k+m-3}_{k,m} & = \frac{k!}{(k+m-3)!} (m+1) \frac{15m^3 +15m^2 -10m -8}{5760} , \quad k\geq 4,  m\geq  0, \notag \\
c^{k+m-4}_{k,m} & = \frac{k!}{(k+m-4)!} \, \frac{m (m+1)^2}{11520} (3m^2 -m -6 ) , \quad k\geq 5,  m\geq  0 . \notag
\end{align}
Likewise, for $m=0$, from these formulas we readily get $c^{k}_{k,0} = \frac{1}{2}$, $c^{k-1}_{k,0} = \frac{k}{12}$,
$c^{k-2}_{k,0} = 0$, $c^{k-3}_{k,0} = -\frac{k(k-1)(k-2)}{720}$, and $c^{k-4}_{k,0} = 0$.

In the following proposition we give an alternative formula for
$C(i,m,r)$, which is most suitable for determining the low-degree
coefficients of $P_k^{(m)}(n)$.

\begin{proposition}\label{prop:3}
For $1 \leq p \leq m+2$ and $1 \leq q \leq i$,
\begin{equation}\label{alt}
C(i,m,r) = \sum_{p+q = r+1} (-1)^{i-q} |s(m+2,p)||s(i,q)| .
\end{equation}
\end{proposition}

\begin{proof}
We start from the equality $[n+m+1]_{i+m+1} = \frac{1}{n}[n]^{m+2} [n]_{i}$.
Now, putting $[n]^{m+2} = \sum_{p=1}^{m+2}|s(m+2,p)| n^p$ and $[n]_{i} =
\sum_{q=1}^{i} (-1)^{i-q}|s(i,q)| n^q$,
we have
\begin{equation*}
\frac{1}{n}[n]^{m+2} [n]_{i} =\sum_{p=1}^{m+2} \sum_{q=1}^{i} (-1)^{i-q}
|s(m+2,p)| |s(i,q)| n^{p+q-1}.
\end{equation*}
From this expression it is clear that the $r$-degree coefficient in $\frac{1}{n}[n]^{m+2} [n]_{i}$
is attained whenever $p+q = r+1$. Thus, recalling that $C(i,m,r)$ denotes the coefficient of the $r$-degree
term in $[n+m+1]_{i+m+1}$, the proposition follows.
\end{proof} 

For example, for the case $r=1$ we must have $p=q=1$ and then
\begin{equation}\label{C1}
C(i,m,1) = (-1)^{i-1}|s(m+2,1)||s(i,1)| = (-1)^{i-1} (m+1)! (i-1)!,
\end{equation}
where we have used the fact that $|s(n,1)| = (n-1)!$.
Then, taking into account (\ref{closed})
and (\ref{p1c}), we find that
\begin{align*}
c_{0,m}^{1} &= \frac{1}{m+1},  \\
c_{k,m}^{1} & =
\sum_{i=1}^{k}\frac{(-1)^{i-1}(m+1)!(i-1)!i!}{(i+m+1)!}S(k,i),
\quad k\geq 1.
\end{align*}
These relations were previously derived in \cite[Prop.\ 2]{inaba}.
In Section \ref{sec:5} we shall obtain, using relations (\ref{closed}), (\ref{p1c}), and
(\ref{alt}), the second and third-degree coefficients $c_{k,m}^{2}$ and $c_{k,m}^{3}$
of $P_k^{(m)}(n)$.

Next we give a general expression for the leading elements
$c_{k,0}^{r}$ in terms of the Bernoulli numbers.

\begin{proposition}\label{prop:4}
For $1 \leq r \leq k+1$,
\begin{equation}\label{ber}
c_{k,0}^{r} = \frac{1}{k+1} {k+1 \choose r} B_{k+1-r} .
\end{equation}
with $B_1 = \tfrac{1}{2}$.
\end{proposition}

\begin{proof} 
This expression readily follows from the well-known Bernoulli formula for the ordinary power sums
(see, for example, the articles \cite{kotiah} and \cite{sherwood}):
\begin{equation*}
P_k^{(0)}(n) =  \frac{1}{k+1} \sum_{j=0}^{k} {k+1\choose j} B_{j} n^{k+1-j},
\end{equation*}
where $B_1$ is taken to be $\tfrac{1}{2}$. This can also be written as
\begin{equation*}
P_k^{(0)}(n) =  \frac{1}{k+1} \sum_{r=1}^{k+1} {k+1 \choose r} B_{k+1-r} n^{r}.
\end{equation*}
On the other hand, recalling that $c_{k,0}^{0} = 0$, the polynomial (\ref{poly}) for $m =0$
reads as
\begin{equation*}
P_k^{(0)}(n) = \sum_{r=1}^{k+1} c_{k,0}^{r} n^{r}.
\end{equation*}
Thus, comparing like terms in the previous two expressions, we get (\ref{ber}).
\end{proof}

From (\ref{ber}) we see at once that $c_{k,0}^{1} = B_k$ (cf.
\cite{kaneko}). Now Proposition~\ref{prop:4}, in conjunction with
equation (\ref{p1c}), yields the following identity.

\begin{corollary}\label{col:5}
For $1 \leq r \leq k+1$ and $k\geq 1$,
\begin{equation}\label{ber1}
\sum_{i=\text{max}\{1,r-1\}}^{k} \frac{1}{i+1} \left(\sum_{t=r}^{i+1} (-1)^{i+1-t} |s(i+1,t)|
{t \choose r} \right) \! S(k,i)  =  \frac{1}{k+1} {k+1 \choose r} B_{k+1-r}.
\end{equation}
\end{corollary}
\begin{proof}
Set $m =0$ in (\ref{p1c})
and identify the resulting expression with (\ref{ber}).
\end{proof}

Putting $r =1$ in (\ref{ber1}) yields the following explicit formula for the Bernoulli numbers
(with $B_1 =\tfrac{1}{2}$):
\begin{equation*}
B_k = \sum_{i=1}^{k} \frac{1}{i+1} \left(\sum_{t=1}^{i+1} (-1)^{i+1-t} |s(i+1,t)| t
\right) \! S(k,i) ,  \quad  k\geq 1 .
\end{equation*}
Furthermore, putting $m =0$ and $r =1$ in (\ref{p1d}) and equating the resulting expression to
that obtained in (\ref{C1}) for $m=0$ gives
\begin{equation*}
\sum_{t=1}^{i+1} (-1)^{i+1-t} |s(i+1,t)| t = (-1)^{i-1} (i-1)! ,
\end{equation*}
and then the previous expression for $B_k$ reduces to the classical
identity for the Bernoulli numbers in terms of the Stirling numbers of
the second kind.

\begin{corollary}\label{col:6}
\begin{equation*}
B_k = \sum_{i=1}^{k} \frac{(-1)^{i-1}(i-1)!}{i+1}  S(k,i) ,  \quad  k\geq 1 .
\end{equation*}
with $B_1 =\tfrac{1}{2}$.
\end{corollary}


\section{A recursive relationship for the hypersums}
\label{sec:3}

In this section we derive a recursive relationship for the hypersums
$P_k^{(m)}(n)$ that shall constitute the core of the generalized
Akiyama-Tanigawa algorithm developed in Section \ref{sec:4}.  This
recurrence relation is presented in Theorem \ref{th:8} below. To prove
this theorem, we shall need the following preliminary result.

\begin{lemma}\label{lem:7}
\begin{equation}\label{lemma}
\sum_{j=1}^{n} j P_{k}^{(m)}(j) = (n+1) P_{k}^{(m+1)}(n) - P_{k}^{(m+2)}(n) .
\end{equation}
\end{lemma}

\begin{proof}
Set $l =m+1$. Then, in view of (\ref{orderm}), it is clear that proving (\ref{lemma}) is
tantamount to proving the combinatorial identity
\begin{equation}\label{cid1}
\sum_{j=1}^n j {j+l \choose i+l} = (n+1){n+l+1
\choose i+l+1} - {n+l+2 \choose i+l+2} .
\end{equation}
To prove (\ref{cid1}), we shall repeatedly use the well-known identity
\begin{equation*}
\sum_{j=0}^{n} {j \choose i} = {n+1 \choose i+1},
\end{equation*}
with ${j \choose i} =0$ for $j <i$. Another crucial ingredient is the absorption property
\begin{equation*}
(i+1) {j+1 \choose i+1} =  (j+1) {j \choose i},  \quad 0 \leq i \leq j,
\end{equation*}
which we rewrite in the form
\begin{equation}\label{abs}
 j {j \choose i} =  (i+1) {j+1 \choose i+1} - {j \choose i}.
\end{equation}
With this in mind we have
\begin{align*}
\sum_{j=1}^n  j {j+l \choose i+l} & = \sum_{j=1}^{n} (j+l)
{j+l \choose i+l} - l \sum_{j=1}^{n}{j+l \choose i+l} \\
& = \sum_{s=i+l}^{n+l} s {s \choose i+l} - l
\sum_{s=i+l}^{n+l}{s \choose i+l} \\
& = \sum_{s=i+l}^{n+l} s {s \choose i+l} - l
{n+l+1 \choose i+l+1}.
\end{align*}
Now from relation (\ref{abs}) it follows that
\begin{align*}
\sum_{s=i+l}^{n+l} s {s \choose i+l} & = (i+l+1) \sum_{s=i+l+1}^{n+l+1} 
{s \choose i+l+1} - \sum_{s=i+l}^{n+l}  {s \choose i+l}  \\
& = (i+l+1)  {n+l+2 \choose i+l+2} -  {n+l+1 \choose i+l+1} ,
\end{align*}
and then
\begin{equation}\label{cid2}
\sum_{j=1}^n  j {j+l \choose i+l} = (i+l+1)  {n+l+2 \choose i+l+2}
- (l+1) {n+l+1 \choose i+l+1}.
\end{equation}
Applying the absorption property once more, we get
\begin{equation*}
(i+l+2) {n+l+2 \choose i+l+2} = (n+l+2) {n+l+1 \choose i+l+1}. 
\end{equation*}
From this we obtain
\begin{equation*}
(i+l+1) {n+l+2 \choose i+l+2} = (n+l+2) {n+l+1 \choose i+l+1}
-  {n+l+2 \choose i+l+2},
\end{equation*}
and then,
substituting this into (\ref{cid2}), we retrieve the identity (\ref{cid1}) and
thus the lemma is proved.
\end{proof}

The extended Akiyama-Tanigawa algorithm for hypersums of powers of
integers is based on the following recursive relationship for the
hypersums, which is stated in the next theorem.

\begin{theorem}\label{th:8}
The hypersums $P_{k+1}^{(m)}(n)$,
$P_{k}^{(m)}(n)$, and $P_{k}^{(m+1)}(n)$ are constrained to obey the relation
\begin{equation}\label{th}
P_{k+1}^{(m)}(n) = (m+1) \big( P_{k}^{(m)}(n) -
P_{k}^{(m+1)}(n) \big) + n P_{k}^{(m)}(n), \quad k, m \geq 0.
\end{equation}
\end{theorem}

\begin{proof}
Assume that $k$ and $n$ take fixed (but otherwise arbitrary)
integer values $k \geq 0$ and
$ n \geq 1$, and proceed by induction on $m$.
First we prove the base case where $m =0$. For this case we must show that
\begin{equation*}
(n+1) P_{k}^{(0)}(n) = P_{k+1}^{(0)}(n) + P_{k}^{(1)}(n) .
\end{equation*}
This is most easily seen by displaying $(n+1) P_{k}^{(0)}(n)$ as the sum of
the $n+1$ rows
\begin{equation*}
\left. \begin{array}{l}
1^k + 2^k + 3^k + \cdots + n^k  \\
1^k + 2^k + 3^k + \cdots + n^k  \\
\,  \vdots  \\
1^k + 2^k + 3^k + \cdots + n^k
\end{array} \!\! \right\}  n+1,
\end{equation*}
and noting that this sum
can be decomposed as the sum of the following two pieces
\begin{equation*}
\left. \begin{array}{l}
1^k   \\
1^k + 2^k \\
1^k + 2^k + 3^k  \\
\,  \vdots  \\
1^k + 2^k + 3^k + \cdots + n^k
\end{array} \!\! \right\}  n
\quad +
\left. \begin{array}{r}
1^k + 2^k + 3^k + \cdots + n^k  \\
2^k + 3^k + \cdots + n^k  \\
3^k + \cdots + n^k  \\
 \vdots \,\,\,  \\
n^k
\end{array} \!\! \right\}  n .
\end{equation*}
Clearly, summing the rows of the piece on the left gives $P_{k}^{(1)}(n)$. On the other hand,
the entries in the $i$-th column of the piece on the right sum to $i^{k+1}$, and so the sum of all
these columns amounts to $P_{k+1}^{(0)}(n)$.

Next we take as the inductive hypothesis the assumption that, for any given $m\geq 1$, it
happens that
\begin{equation}\label{hyp}
P_{k+1}^{(m-1)}(j) = m \big( P_{k}^{(m-1)}(j) -
P_{k}^{(m)}(j) \big) + j P_{k}^{(m-1)}(j),
\end{equation}
for arbitrary integers $k\geq 0$ and $j\geq 1$. The task is to derive (\ref{th}) starting from (\ref{hyp}).
This is rather immediate once we have established Lemma~\ref{lem:7}. Indeed,
recalling that, by definition,
\begin{equation*}
\sum_{j=1}^{n} P_{k+1}^{(m-1)}(j) =
P_{k+1}^{(m)}(n), \,\,\, \sum_{j=1}^{n}
P_{k}^{(m-1)}(j) = P_{k}^{(m)}(n),
\,\text{and}\,\,
\sum_{j=1}^{n} P_{k}^{(m)}(j) =
P_{k}^{(m+1)}(n),\end{equation*}
from (\ref{hyp}) we obtain that
\begin{equation*}
P_{k+1}^{(m)}(n) = m \big( P_{k}^{(m)}(n) -
P_{k}^{(m+1)}(n)\big) + \sum_{j=1}^{n} j
P_{k}^{(m-1)}(j) .
\end{equation*}
From Lemma \ref{lem:7} we have
\begin{equation*}
\sum_{j=1}^{n} j P_{k}^{(m-1)}(j) = (n+1)
P_{k}^{(m)}(n) - P_{k}^{(m+1)}(n) ,
\end{equation*}
and then substituting this expression into the previous equation we get the recursion formula
(\ref{th}). Having completed the base case and the inductive case, the overall proof of Theorem
\ref{th:8} is done.
\end{proof}


\section{Generalized Akiyama-Tanigawa algorithm
for hypersums of powers of integers}
\label{sec:4}

The Akiyama-Tanigawa algorithm for computing Bernoulli numbers starts with the
initial row (the 0-th row) given by the sequence $a_{0,m} = 1/(m+1)$ (for $m \geq 0$),
and then generates the row $k$ (for $k \geq 1$) by the rule
\cite{kaneko,chen,inaba}
\begin{equation}\label{rr}
a_{k,m} = (m+1) (a_{k-1,m} - a_{k-1,m+1}) .
\end{equation}
Then the leading element $a_{k,0}$ of each row is seen to be the $k$-th
Bernoulli number $B_k$ with $B_1 =\tfrac{1}{2}$ \cite{kaneko}.

As noted in the Introduction,
Inaba \cite{inaba} showed that the coefficient of the
first-degree term in $P_k^{(m)}(n)$, $c_{k,m}^{1}$,
satisfies a recurrence relation
given by (\ref{rr}), namely,
\begin{equation}\label{inaba}
c_{k,m}^{1} = (m+1) (c_{k-1,m}^{1} - c_{k-1,m+1}^{1}) ,
\end{equation}
with the same initial condition $c_{0,m}^{1} = 1/(m+1)$, and so we have in fact that $c_{k,m}^{1}
= a_{k,m}$. Based on Theorem \ref{th:8}, we are going to show that, actually, relation (\ref{inaba}) is
just a particular case of a more general relationship for the coefficients $c_{k,m}^{r}$ of
the hypersum polynomials (\ref{poly}). This is established in the following proposition, which
constitutes one of the main results of this paper.

\begin{proposition}[\it{Generalized Akiyama-Tanigawa algorithm}]\label{prop:9}

For $1 \leq r \leq k+m+1$, $k\geq 1$, and $m \geq 0$, we have the recurrence relation
\begin{equation}\label{grr}
c_{k,m}^{r} = (m+1) \big(c_{k-1,m}^{r} - c_{k-1,m+1}^{r} \big) + c_{k-1,m}^{r-1},
\end{equation}
with the starting sequence given by
\begin{equation}\label{closed2}
c_{0,m}^{r} = \frac{|s(m+1,r)|}{(m+1)!}.
\end{equation}
\end{proposition}

\begin{proof}
Write the recursive relationship (\ref{th}) for the hypersums as
\begin{equation*}
P_{k}^{(m)}(n) = (m+1) \big( P_{k-1}^{(m)}(n) -
P_{k-1}^{(m+1)}(n) \big) + n P_{k-1}^{(m)}(n) .
\end{equation*}
Replacing $P_k^{(m)}(n)$ for its polynomial expression (\ref{poly}) (with $c_{k,m}^{0} =0$)
we obtain
\begin{equation*}
\sum_{r=1}^{k+m+1} c_{k,m}^{r} n^r = (m+1) \left(
\sum_{r=1}^{k+m} c_{k-1,m}^{r} n^r
- \sum_{r=1}^{k+m+1} c_{k-1,m+1}^{r} n^r\right) +
\sum_{r=1}^{k+m} c_{k-1,m}^{r} n^{r+1},
\end{equation*}
or, equivalently,
\begin{equation*}
\sum_{r=1}^{k+m+1} c_{k,m}^{r} n^r =
\sum_{r=1}^{k+m+1} (m+1) (c_{k-1,m}^{r} -
c_{k-1,m+1}^{r}) n^r + \sum_{r=1}^{k+m+1}
c_{k-1,m}^{r-1} n^{r},
\end{equation*}
on the understanding that $c_{k-1,m}^{k+m+1} =0$. Thus, by equating like powers of $n$ on both
sides of this equation we are finally left with relation (\ref{grr}). On the other hand, the proof of
(\ref{closed2}) is given in Proposition~\ref{prop:2}.
\end{proof}

Clearly, for the case $r =1$ relation (\ref{grr}) reduces to (\ref{inaba}), as $c_{k-1,m}^{0} =0$
for all $k\geq 1$ and $m\geq 0$. Finally, one can check that the coefficients given in (\ref{highd})
in fact satisfy the recurrence (\ref{grr}). So, for example, for $k\geq 5$ and $m\geq 0$, we have that
\begin{align*}
c^{k+m-3}_{k,m} & = \frac{k!}{(k+m-3)!} (m+1) \frac{15m^3 +15m^2 -10m -8}{5760} ,  \\
c^{k+m-3}_{k-1,m} & = \frac{(k-1)!}{(k+m-3)!} \, \frac{m (m+1)^2}{48} ,  \\
c^{k+m-3}_{k-1,m+1} & =  \frac{(k-1)!}{(k+m-3)!} (m+2) \frac{15m^3 +60m^2 +65m +12}{5760},  \\
c^{k+m-4}_{k-1,m} & = \frac{(k-1)!}{(k+m-4)!} (m+1) \frac{15m^3 +15m^2 -10m -8}{5760} ,
\end{align*}
which satisfy the relation
\begin{equation*}
c^{k+m-3}_{k,m} = (m+1) \big(c^{k+m-3}_{k-1,m} - c^{k+m-3}_{k-1,m+1} \big) + c^{k+m-4}_{k-1,m}.
\end{equation*}


\section{Second-degree coefficient of the hypersum polynomial}
\label{sec:5}

In this section we examine explicitly the coefficient of the second-degree term in
$P_k^{(m)}(n)$, $c_{k,m}^{2}$, by means of the generalized Akiyama-Tanigawa algorithm.
For $r =2$, recurrence (\ref{grr}) becomes
\begin{equation}\label{at2}
c_{k,m}^{2} = (m+1) (c_{k-1,m}^{2} -
c_{k-1,m+1}^{2}) + c_{k-1,m}^{1},
\end{equation}
with initial sequence (the row 0)
\begin{equation}\label{c02}
c_{0,m}^{2} = \frac{|s(m+1,2)|}{(m+1)!} = \frac{H_m}{m+1},
\end{equation}
where we have used that $|s(n,2)| = (n-1)! H_{n-1}$, $H_n$ denoting the harmonic number
$H_n = \sum_{i=1}^{n} 1/i$, with $H_0 =0$. To obtain the sequence corresponding to
row 1, $c_{1,m}^{2}$, we feed (\ref{c02}) into
(\ref{at2}) and, recalling that $c_{0,m}^{1} = 1/(m+1)$, we get
\begin{equation*}
c_{1,m}^{2} = \frac{H_{m+1}}{m+2}.
\end{equation*}
Similarly,
inserting this expression into (\ref{at2}), and noting that $c_{1,m}^{1} =
1/(m+2)$, we find the elements of row 2
\begin{equation*}
c_{2,m}^{2} = \frac{2+(m+1)H_{m+1}}{(m+2)(m+3)}.
\end{equation*}
Likewise, proceeding this way, we obtain the sequences for rows 3 and 4 as
\begin{align*}
c_{3,m}^{2} & =
\frac{(m+1)(6+mH_{m+1})}{(m+2)(m+3)(m+4)}, \\
c_{4,m}^{2} & = \frac{(m+1)\big(
4+14m+(m-4)(m+1)H_{m+1}\big)}{(m+2)(m+3)(m+4)(m+5)},
\end{align*}
and so on.

\begin{table}
\begin{center}
\begin{tabular}{c|ccccccc} 
$k\backslash m$ & 0 & 1 & 2 & 3 & 4 & 5 & $\cdots$
\\
\hline $0$ & 0 & 1/2 &1/2 &11/24 &5/12 &137/360 &
$\cdots$ \\
$1$ & 1/2 & 1/2 &11/24 & 5/12 & 137/360 & 7/20 &
$\cdots$ \\
$2$ & 1/2 & 5/12 & 3/8 & 31/90 & 23/72 & 167/560 &
$\cdots$ \\
$3$ & 1/4 & 1/4 & 29/120& $ 7/30$ & 227/1008
&73/336 & $\cdots$ \\
$4$ & 0 & 1/20 & 3/40 & 113/1260 & 25/252 &
887/8400 & $\cdots$ \\
$5$ & $-1/12$ & $-1/12$ & $-11/168$ & $-1/21$ &
$-23/720$ & $-31/1680$ & $\cdots$ \\
$6$ & 0 & $-5/84$ & $-5/56$ & $-127/1260$ &
$-13/126$ & $-621/6160$ & $\cdots$ \\
$7$ & 1/12 & 1/12 & 1/24 & 0 & $-53/1584$ &
$-31/528$ & $\cdots$ \\
$8$ & 0 & 7/60 & 7/40 & 361/1980& 65/396 &
162641/1201200 & $\cdots$ \\
$\vdots$ & \vdots & \vdots & \vdots & \vdots &
\vdots & \vdots & $\cdots$ \\
\end{tabular}\end{center}
\caption{\small{The Akiyama-Tanigawa matrix $\{c_{k,m}^{2}\}$ for
$k=0/8$ and $m =0/5$.}}
\label{tb:1}
\end{table}

In Table \ref{tb:1} we display the matrix for $c_{k,m}^{2}$ that
results for the first few values of $k$ and $m$. From (\ref{ber}), it
follows that the sequence corresponding to the 0-th column,
$c_{k,0}^{2}$, $k = 1,2,3,\ldots\, $, is given by $c_{k,0}^{2} =
\frac{1}{2}k B_{k-1}$, with $c_{0,0}^{2} =0$.

We can deduce a general expression for $c_{k,m}^{2}$ by first using Proposition \ref{prop:3}
to get $C(i,m,2)$, and then using (\ref{p1c}). For $r=2$ the allowed values of the ordered pair
$(p,q)$ are $(1,2)$ and $(2,1)$, and then from (\ref{alt}) we get
\begin{equation*}
C(i,m,2) = (-1)^{i-2}|s(m+2,1)||s(i,2)| + (-1)^{i-1}|s(m+2,2)||s(i,1)|.
\end{equation*}
Recalling that $|s(n,1)|= (n-1)!$ and $|s(n,2)| = (n-1)! H_{n-1}$, this gives
\begin{align*}
C(i,m,2) & = (-1)^{i-2} (m+1)! (i-1)!H_{i-1} + (-1)^{i-1} (m+1)! H_{m+1} (i-1)! \\
& = (-1)^{i-1} (m+1)! (i-1)! \big(H_{m+1} - H_{i-1} \big). 
\end{align*}
Provided with $C(i,m,2)$, we can now use (\ref{c02}) and (\ref{p1c}) to obtain $c_{k,m}^{2}$:

\begin{proposition}\label{prop:10}
\begin{equation*}
c_{k,m}^{2} = \begin{cases}
\displaystyle{\frac{H_m}{m+1}}, & \text{ if }k=0,  \\
\displaystyle{\sum_{i=1}^{k} \frac{(-1)^{i-1}
(m+1)! (i-1)! i! \big(H_{m+1} - H_{i-1}
\big)}{(i+m+1)!} S(k,i)}, & \text{ if }   k\geq 1.
\end{cases}
\end{equation*}
\end{proposition}

The following corollary gives us an alternative explicit formula for
the Bernoulli numbers in terms of the Stirling numbers of the second
kind and the harmonic numbers.

\begin{corollary}\label{col:11}
\begin{equation*}
B_k = \frac{2}{k+1} \sum_{i=1}^{k+1} \frac{(-1)^{i-1}(i-1)!
\big( 1- H_{i-1} \big)}{i+1} S(k+1,i) , \quad k \geq 0.
\end{equation*}
with $B_1 = \tfrac{1}{2}$.
\end{corollary}
\begin{proof}
We already know that $c_{k,0}^{2} = \frac{1}{2}k B_{k-1}$ for $k\geq 1$ or,
equivalently, $c_{k+1,0}^{2} = \frac{1}{2}(k+1) B_{k}$ for $k\geq 0$. Then put $m =0$ in the
second relation of Proposition~\ref{prop:10} and shift $k$ to $k+1$. Equal the resulting expression to
$\frac{1}{2}(k+1) B_{k}$, and hence the corollary follows.
\end{proof}

In the same way, by applying relations (\ref{closed}), (\ref{p1c}), and (\ref{alt}), one can determine the
successive low-degree coefficients $c_{k,m}^{3},c_{k,m}^{4},\ldots\,$. In the following proposition we
give the expression for $c_{k,m}^{3}$ (note that, in this case, we have $c_{0,0}^{3} = c_{0,1}^{3} =
c_{1,0}^{3} =0$.)

\begin{proposition}\label{prop:12}
\begin{equation*}
c_{k,m}^{3} =\begin{cases}
\displaystyle{\frac{1}{2(m+1)} \Big( (H_m)^2 - H_m^{(2)} \Big)},& \text{ if }  k =0, \\
\displaystyle{\sum_{i=1}^{k} \frac{(-1)^{i-1}(m+1)! (i-1)! i!}{2(i+m+1)!} 
\Big( \big( H_{m+1} - H_{i-1} \big)^2 - H_{m+1}^{(2)} - H_{i-1}^{(2)} \Big)
S(k,i)}, & \text{ if } k \geq 1,
\end{cases}
\end{equation*}
where $H_m^{(2)} = \sum_{i=1}^m 1/i^2$.
\end{proposition}


\section{Concluding remarks}
\label{sec:6}

In his 1631 \textit{Academia Algebrae}, the German mathematician and
engineer Johann Faulhaber (1580--1635) presented novel formulas for (in
our notation) $P_k^{(0)}(n)$ for values of $k$ ranging from $k =13$ up
to $k =23$. (He had previously published formulas for $P_k^{(0)}(n)$ up
to $k =12$). These formulas were expressed for the first time in terms
of the variable $N =n(n+1)/2$.
Moreover, Faulhaber also produced remarkable formulas for sums of power
sums. Indeed, as Knuth explains in his comprehensive study of
Faulhaber's work on sums of powers \cite{knuth}, he exhibited a totally
correct 17-degree polynomial in $n$ for the hypersum $P_{6}^{(10)}(n)$
(which in Knuth's notation is $\Sigma^{11} n^6$) that, in Knuth's
words, would have been quite difficult to obtain by repeated
summation.
Here we argue that, in fact, $P_{6}^{(10)}(n)$ can be obtained by
repeated summation using the generalized Akiyama-Tanigawa algorithm described in equations
(\ref{grr}) and (\ref{closed2}). Of course this entails a lot of work since one has to construct 17
tables of coefficients $c_{k,m}^{r}$, $r =1,2,\ldots,17$, and, for each of these tables, one has to
determine, starting from (\ref{closed2}) and by repeated application of (\ref{grr}), the pair
of elements $c_{5,10}^{r}$ and $c_{5,11}^{r}$. Once the values of $c_{5,10}^{r}$ and
$c_{5,11}^{r}$ have been ascertained for each $r$, a last application of (\ref{grr})
would allow us to obtain the desired coefficients $c_{6,10}^{r}$.

Fortunately, 382 years after the time of publication of
\textit{Academia Algebrae}, we can routinely run a modern computer to
perform the calculations in a fraction of a second.
Furthermore, besides relations (\ref{grr}) and (\ref{closed2}), we can alternatively use the
formulas (\ref{p1c}) and (\ref{p1d}) to directly evaluate the coefficients we want to. So,
putting $k =6$ and $m =10$ in (\ref{p1c}) and (\ref{p1d}) yields
\begin{equation*}
c_{6,10}^{r} = \sum_{i=\text{max}\{1,r-11\}}^{6} \frac{i!}{(i+11)!}
\left(\sum_{t=1}^{i+11} (-1)^{i+11-t} |s(i+11,t)|
{t \choose r} 11^{t-r} \right) \!  S(6,i).
\end{equation*}
By means of, for example, a computer algebra system such as
\textit{Mathematica}, we can readily compute this
expression for $r=1,2,\ldots,17$. Next we quote the results as follows:
\begin{align*}
c_{6,10}^{1} &= -96598656000/C, & c_{6,10}^{2}
&=-203020963200/C, \\
c_{6,10}^{3} &= 90994289760/C, & c_{6,10}^{4} &=
709177112512/C, \\
c_{6,10}^{5} &= 1021675563656/C, & c_{6,10}^{6} &=
812536224500/C, \\
c_{6,10}^{7} &= 423402217056/C, & c_{6,10}^{8} &=
155027658357/C, \\
c_{6,10}^{9} &= 41338556974/C, & c_{6,10}^{10} &=
8177397800/C, \\
c_{6,10}^{11} &= 1208226448/C, & c_{6,10}^{12} &=
132902770/C, \\
c_{6,10}^{13} &= 10728564/C, & c_{6,10}^{14} &=
617100/C, \\
c_{6,10}^{15} &= 23936/C, & c_{6,10}^{16} &= 561/C
, \\
 c_{6,10}^{17} &= 6/C,
\end{align*}
where $C = 17! / 5! = 2964061900800$, in accordance with (\ref{lc}). We note that
$\sum_{r=1}^{17} c_{6,10}^{r} = 1$. This is an instance of the general relation
\begin{equation*}
\sum_{r=1}^{k+m+1} c_{k,m}^{r} =1,
\end{equation*}
which follows from the fact that $P_k^{(m)}(1) =1$ for all $k \geq 0$ and $m\geq 0$.


\section{Acknowledgement}

The author would like to thank the anonymous referee for essential comments and
suggesting Proposition \ref{prop:3}.


\begin{thebibliography}{9}

\bibitem{AT}
S. Akiyama and Y. Tanigawa, Multiple zeta values at non-positive integers,
\textit{Ramanujan J.} \textbf{5} (2001), 327--351.

\bibitem{kaneko}
M. Kaneko, The Akiyama-Tanigawa algorithm for Bernoulli numbers, \textit{J.
Integer Seq.} \textbf{3} (2000), \href{https://cs.uwaterloo.ca/journals/JIS/VOL3/KANEKO/AT-kaneko.html}
{Article 00.2.9}.

\bibitem{chen}
K.-W. Chen, Algorithms for Bernoulli and Euler numbers, \textit{J. Integer
Seq.} \textbf{4} (2001), \href{https://cs.uwaterloo.ca/journals/JIS/VOL4/CHEN/AlgBE2.html}
{Article 01.1.6}.

\bibitem{inaba}
Y. Inaba, Hyper-sums of powers of integers and the Akiyama-Tanigawa matrix,
\textit{J. Integer Seq.} \textbf{8} (2005), \href{https://cs.uwaterloo.ca/journals/JIS/VOL8/Inaba/inaba301.html}
{Article 05.2.7}.

\bibitem{kotiah}
T. C. T. Kotiah, Sums of powers of integers---A review, \textit{Int. J. Math.
Educ. Sci. Technol.} \textbf{24} (1993), 863--874.

\bibitem{sloane}
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published
electronically at \url{http://oeis.org}, 2012.

\bibitem{pfaff}
T. J. Pfaff, Deriving a formula for sums of powers of integers, \textit{Pi Mu Epsilon J.} \textbf{12} (2007), 425--430.

\bibitem{sherwood}
H. Sherwood, Sums of power of integers and Bernoulli numbers, \textit{Math.
Gaz.} \textbf{54} (1970), 272--274.

\bibitem{knuth}
D. E. Knuth, Johann Faulhaber and sums of powers, \textit{Math. Comp.}
\textbf{61} (1993), 277--294.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11Y55; Secondary 05A10.

\noindent \emph{Keywords: } 
hypersums of powers of integers, Akiyama-Tanigawa
algorithm, Stirling number, Bernoulli number, harmonic number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A008275} and
\seqnum{A008277}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 12 2012;
revised version received  February 11 2013.
Published in {\it Journal of Integer Sequences}, March 2 2013.

\bigskip
\hrule
\bigskip

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


\end{document}