\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

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

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
Hyper-Sums of Powers of Integers and the \\
\vskip .08in 
Akiyama-Tanigawa Matrix}

\vskip 1cm
\large
Yoshinari Inaba\\
Toba Senior High School\\
Nishikujo, Minami-ku \\
Kyoto 601-8449 \\
Japan\\
\href{mailto:inava@kyoto-be.ne.jp}{\tt inava@kyoto-be.ne.jp} \\
\end{center}

\vskip .1in

\begin{abstract}
In this short essay, we consider hyper-sums of powers of integers,
namely sums of power sums. We can obtain easily their formulae as
polynomials by using formulae for ordinary sums of powers of integers.
The coefficient of the first-degree term in each polynomial coincides
with the matrix element of the Akiyama-Tanigawa matrix.
\end{abstract}


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



%\usepackage{amsmath,amssymb,amsthm}
%\usepackage{txfonts}
%\setlength{\topmargin}{-10mm}
%\setlength{\oddsidemargin}{-1mm}
%\setlength{\textwidth}{47zw}
%\pagestyle{empty}
%
\newcommand{\minisp}{\vspace{3mm}}
\newcommand{\bigsp}{\vspace{30mm}}
\newcommand{\midsp}{\vspace{14mm}}
\newcommand{\bango}[1]{{\Large{#1}.}}
\newcommand{\stf}[2]{\begin{bmatrix}#1 \cr #2 \end{bmatrix}}
\newcommand{\sts}[2]{\begin{Bmatrix}#1 \cr #2 \end{Bmatrix}}
%
\newtheorem{lem}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
%




\section{The Akiyama-Tanigawa matrix}

The Akiyama-Tanigawa algorithm which is reformulated by K. W. Chen \cite{chen} and 
M. Kaneko \cite{kan} is described by the sequence $\{a_{n,\, m}\}$;
\begin{align}
a_{n,\, m}=(m+1)(a_{n-1,\, m}-a_{n-1,\, m+1}),\quad n\ge1,\, m\ge 0
\label{eqn:rec1}
\end{align}
with an initial sequence $a_{0,\, m}\ (m=0,1,2,\ldots)$. \par
\noindent Let $B_n(x)$ be the $n$-th Bernoulli polynomial
$$\frac{te^{xt}}{e^t-1}=\sum_{n=0}^\infty B_n(x)\frac{t^n}{n!},\qquad | t|<2\pi$$
When the initial sequence is $a_{0,\, m}=1/(m+1)$ then this algorithm
yields $B_n(1)$ as the leading element $a_{n,\, 0}$. Here $B_n(1)$ are,
in fact, the Bernoulli numbers $B_n$, with the sole exception of $n=1$,
for which $B_1(1)=-B_1$ holds. We assume this situation here and the
Akiyama-Tanigawa matrix $\{a_{n,\, m}\}$ is then

\begin{table}[H]
\begin{center}
\renewcommand{\arraystretch}{1.1}
{\setlength{\tabcolsep}{4pt}
\begin{tabular}{rrrrrrrrrrrrr}
$a_{n,\, 0}$&$a_{n,\, 1}$&$a_{n,\, 2}$&$a_{n,\, 3}$&$a_{n,\, 4}$&$a_{n,\, 5}$&$a_{n,\, 6}$&$a_{n,\, 7}$&$a_{n,\, 8}$&$a_{n,\, 9}$&$a_{n,\, 10}$&\\
\hline
$1$&$\frac{1}{2}$&$\frac{1}{3}$&$\frac{1}{4}$&$\frac{1}{5}$&$\frac{1}{6}$&$\frac{1}{7}$&$\frac{1}{8}$&$\frac{1}{9}$&$\frac{1}{10}$&$\frac{1}{11}$&$\cdots$\\
$\frac{1}{2}$&$\frac{1}{3}$&$\frac{1}{4}$&$\frac{1}{5}$&$\frac{1}{6}$&$\frac{1}{7}$&$\frac{1}{8}$&$\frac{1}{9}$&$\frac{1}{10}$&$\frac{1}{11}$&$\cdots$&\\
$\frac{1}{6}$&$\frac{1}{6}$&$\frac{3}{20}$&$\frac{2}{15}$&$\frac{5}{42}$&$\frac{3}{28}$&$\frac{7}{72}$&$\frac{4}{45}$&$\frac{9}{110}$&$\cdots$&&\\
$0$&$\frac{1}{30}$&$\frac{1}{20}$&$\frac{2}{35}$&$\frac{5}{84}$&$\frac{5}{84}$&$\frac{7}{120}$&$\frac{28}{495}$&$\cdots$&&&\\
$-\frac{1}{30}$&$-\frac{1}{30}$&$-\frac{3}{140}$&$-\frac{1}{105}$&$0$&$\frac{1}{140}$&$\frac{49}{3960}$&$\cdots$&&&&\\
$0$&$-\frac{1}{42}$&$-\frac{1}{28}$&$-\frac{4}{105}$&$-\frac{1}{28}$&$-\frac{29}{924}$&$\cdots$&&&&&\\
$\frac{1}{42}$&$\frac{1}{42}$&$\frac{1}{140}$&$-\frac{1}{105}$&$-\frac{5}{231}$&$\cdots$&&&&&&\\
$0$&$\frac{1}{30}$&$\frac{1}{20}$&$\frac{8}{165}$&$\cdots$&&&&&&&\\
$-\frac{1}{30}$&$-\frac{1}{30}$&$\frac{1}{220}$&$\cdots$&&&&&&&&\\
$0$&$-\frac{5}{66}$&$\cdots$&&&&&&&&&\\
$\frac{5}{66}$&$\cdots$&&&&&&&&&&\\
$\cdots$&&&&&&&&&&&&
\end{tabular}}
\end{center}
\end{table}
\noindent
Each matrix element $a_{n,\, m}$ is determined uniquely by the recursive rule (\ref{eqn:rec1}) and
the initial values. 

\section{Explicit formulation}

In this section, we determine an explicit expression of $a_{n,\, m}$. 
\begin{prop}
\begin{align}
a_{n,\, m}=\frac{1}{m!}\sum_{i=0}^m(-1)^i\stf{m+1}{i+1}B_{n+i}(1),\qquad n\in \mbox{$\mathbb{N}$}.
\label{eqn:anm}
\end{align}
where $\genfrac{[}{]}{0pt}{}{n}{k}$ are the 
Stirling numbers of the first kind (Sloane's A008275,  cf. \cite{gkp}, Ch. 6.1).
\end{prop}
\begin{proof} First, we shall see that this
$a_{n,\, m}$ satisfies the recursive rule (\ref{eqn:rec1}).
To do this, we use the well known recurrence relation  
$\genfrac{[}{]}{0pt}{}{n+1}{k}=n\genfrac{[}{]}{0pt}{}{n}{k}+\genfrac{[}{]}{0pt}{}{n}{k-1}$. 

\begin{align*}
&(m+1)(a_{n-1,\, m}-a_{n-1,\, m+1})\\
&=(m+1)\Bigl(\frac{1}{m!}\sum_{i=0}^m(-1)^i\stf{m+1}{i+1}B_{n+i-1}(1)-\frac{1}{(m+1)!}\sum_{i=0}^{m+1}(-1)^i\stf{m+2}{i+1}B_{n+i-1}(1) \Bigr)\\
&=\frac{1}{m!}\sum_{i=0}^{m+1}(-1)^i\Bigl( (m+1)\stf{m+1}{i+1}-\stf{m+2}{i+1}\Bigr)B_{n+i-1}(1)\\
&=\frac{1}{m!}\sum_{i=0}^{m+1}(-1)^{i+1}\stf{m+1}{i}B_{n+i-1}(1)\\
&=a_{n,\, m},
\end{align*}
where we have used the fact that $\genfrac{[}{]}{0pt}{}{m+1}{0}=0$.\\

Next, to show that the initial sequence $a_{0,\, m}=1/(m+1)$, we use an
expression that can be found in Kaneko \cite{kan}.  Let 
$\genfrac{\{}{\}}{0pt}{}{n}{k}$ be the Stirling numbers of the second kind
(Sloane's A008277, cf. \cite{gkp}, Ch. 6.1).  Then
\begin{align*}
B_n(1)=\sum_{i=0}^n\frac{(-1)^ii!}{i+1} \sts{n+1}{i+1},\qquad n\ge 0,
\end{align*}
By the well known inversion formula (cf. \cite{gkp}, Ch. 6.1),
\begin{align*}
\sum_{k=m}^n\stf{n}{k}\sts{k}{m}(-1)^{n-k}=\begin{cases}
                   1, & m=n\\
                   0, & m\ne n
                  \end{cases}
,
\end{align*}
we can compute what we want easily.

\begin{align*}
(m+1)a_{0,\, m}&=\frac{m+1}{m!}\sum_{i=0}^m(-1)^i\stf{m+1}{i+1}B_{i}(1)\\
&=\frac{m+1}{m!}\sum_{k=0}^m \frac{k!(-1)^k}{k+1}\sum_{i=k}^m(-1)^i\stf{m+1}{i+1}\sts{i+1}{k+1}\\
&=\frac{(m+1)(-1)^m}{m!}\sum_{k=0}^m\frac{k!(-1)^k}{k+1}\sum_{i=k}^m(-1)^{m-i}\stf{m+1}{i+1}\sts{i+1}{k+1}\\
&=1
\end{align*}
\noindent From the recursive rule (\ref{eqn:rec1}) and initial values $a_{0,\, m}$, the proof of this proposition is done and we have an explicit expression of $a_{n,\, m}$.
\end{proof}

\minisp
\section{Hyper-sum polynomials}

Now we shall consider ``hyper-sums'' of powers of integers, namely sums
of power sums. Let
$P_k^{(0)}(n)=\sum_{i=1}^ni^k,\ P_k^{(1)}(n)=
\sum_{i=1}^nP_k^{(0)}(i),\ P_k^{(2)}(n)=\sum_{i=1}^nP_k^{(1)}(i),\ldots,$
and $P_k^{(m)}(n)=\sum_{i=1}^nP_k^{(m-1)}(i)$, with $k$ and $n$
positive integers. $P_k^{(m)}(n)$ is a $(k+m+1)$-th degree polynomial
in $n$ and $P_k^{(0)}(n)$ is the ordinary power sum
$1^k+2^k+3^k+\cdots+n^k$. Let $c_{k,\, m}$ be the coefficient of the
first-degree term in $P_k^{(m)}(n)$. \\ Since the formulae for
$P_k^{(0)}(n)$ have been investigated for a long time and abundant
methods of determining them have been developed, we can use some of
them.  Here we choose the formula including the Stirling numbers of the
second kind, which is for instance seen in the paper of Srivastava,
Joshi and Bisht \cite{sjb}.
\begin{align*}
P^{(0)}_k(n)=\sum_{i=1}^ki!\binom{n+1}{i+1}\sts{k}{i},\qquad k\in \mbox{$\mathbb{N}$}
\end{align*}
where the binomial coefficient $\binom{n+1}{i+1}$ is taken to be zero for $n<i$.
Here we use the well known identity (cf. \cite{gkp}, Ch. 5.1),
\begin{align*}
\sum_{k=0}^n\binom{k}{m}=\binom{n+1}{m+1},
\end{align*}
where the binomial coefficient $\binom{k}{m}$ is zero for $k<m$. 
This yields
\begin{align*}
\sum_{n=0}^N\binom{n+1}{i+1}=
\sum_{n=i}^N\binom{n+1}{i+1}=\sum_{n=i+1}^{N+1}\binom{n}{i+1}=\binom{N+2}{i+2}.
\end{align*}
So we can get easily 
\begin{align*}
P_k^{(1)}(n)=\sum_{i=1}^ki!\binom{n+2}{i+2}\sts{k}{i},\qquad k\in \mbox{$\mathbb{N}$}.
\end{align*}
Thus, by means of the successive computations, we arrive at
\begin{align*}
P_k^{(m)}(n)=\sum_{i=1}^ki!\binom{n+m+1}{i+m+1}\sts{k}{i},\qquad k\in \mbox{$\mathbb{N}$}.
\end{align*}
From the fact that $\binom{n+m+1}{i+m+1}$ has the factor $n$ for $i\ge 1$,
$P_k^{(m)}(n)$ is divisible by $n$.
Therefore, to find $c_{k,\, m}$, we shall use the following relation. 
\begin{align*}
c_{k,\, m}=\frac{P_k^{(m)}(n)}{n}\Big|_{n=0} 
\end{align*}
Since
\begin{align*}
\frac{1}{n}\binom{n+m}{k+m}\Big|_{n=0} =\frac{m!(k-1)!(-1)^{k-1}}{(k+m)!}.
\end{align*}
We obtain
\begin{align}
c_{k,\, m}=\sum_{i=1}^k\frac{(m+1)!(i-1)!i!(-1)^{i-1}}{(i+m+1)!}\sts{k}{i},\qquad k\in \mbox{$\mathbb{N}$}.
\label{eqn:cnm}
\end{align}
Now only $c_{0,\, m}$ has been left for us. But it is not difficult to
see it, because the identity $P_0^{(1)}(n)=P_1^{(0)}(n)=\sum_{i=1}^ni$
yields $P_0^{(m)}(n)=P_1^{(m-1)}(n)$ immediately. Thus we have $c_{0,\,
m}=c_{1,\, m-1}=1/(m+1)$. By combining these consequences, we can state
the following proposition.

\begin{prop}
\renewcommand{\arraystretch}{2.5}
\[ c_{k,\, m}=\left\{ \begin{array}{ll}
\dfrac{1}{m+1}, & k=0\\
\displaystyle{\sum_{i=1}^k\frac{(m+1)!(i-1)!i!(-1)^{i-1}}{(i+m+1)!}}{\genfrac{\{}{\}}{0pt}{}{k}{i}},& k\ge 1
        \end{array}\right. \]
\label{prop:ftc}
\end{prop}

\section{Equality between $a_{n,\, m}$ and $c_{n,\, m}$}
As one of the important consequences in this essay, let us see the
equality between $a_{n,\, m}$ and $c_{n,\, m}$. To do this, we shall
see the recurrence relation whom $c_{n,\, m}$ satisfies.
\begin{lem}
\begin{align*}
c_{n,\, m}&=(m+1)(c_{n-1,\, m}-c_{n-1,\, m+1}),\qquad n\ge 1
\end{align*}
\end{lem}
\begin{proof}
For the initial case $n=1$, by proposition \ref{prop:ftc} we have
$c_{0,\, m}=1/(m+1)$ and $c_{1,\, m}=1/(m+2)$ without difficulty. So we
can confirm that $c_{1,\, m}=(m+1)(c_{0,\, m}-c_{0,\, m+1})$ easily.\\

For the case $n\ge 2$, we use the well known recurrence relation
$\genfrac{\{}{\}}{0pt}{}{n}{k}=
k\genfrac{\{}{\}}{0pt}{}{n-1}{k}+\genfrac{\{}{\}}{0pt}{}{n-1}{k-1}$.
\begin{align*}
c_{n,\, m}&=\sum_{i=1}^{n}\frac{(m+1)!(i-1)!i!(-1)^{i-1}}{(i+m+1)!}\sts{n}{i}\\
&=\sum_{i=1}^{n}\frac{(m+1)!(i-1)!i!(-1)^{i-1}}{(i+m+1)!}\bigl( i\sts{n-1}{i}+\sts{n-1}{i-1}\bigr) \\
&=\sum_{i=1}^{n-1}\frac{(m+1)!i!i!(-1)^{i-1}}{(i+m+1)!}\sts{n-1}{i}-\sum_{i=1}^{n-1}\frac{(m+1)!i!(i+1)!(-1)^{i-1}}{(i+m+2)!}\sts{n-1}{i}\\
&=\sum_{i=1}^{n-1}\frac{(m+1)!i!i!(-1)^{i-1}}{(i+m+1)!}\cdot \frac{m+1}{i+m+2}\sts{n-1}{i}
\end{align*}
On the other hand,
\begin{align*}
&(m+1)(c_{n-1,\, m}-c_{n-1,\, m+1})\\
&=(m+1)\Bigl(\sum_{i=1}^{n-1}\frac{(m+1)!(i-1)!i!(-1)^{i-1}}{(i+m+1)!}\sts{n-1}{i}-\sum_{i=1}^{n-1}\frac{(m+2)!(i-1)!i!(-1)^{i-1}}{(i+m+2)!}\sts{n-1}{i}\Bigr)\\
&=(m+1)\Bigl(\sum_{i=1}^{n-1}\frac{(m+1)!(i-1)!i!(-1)^{i-1}}{(i+m+1)!}\cdot \frac{i}{i+m+2}\sts{n-1}{i}\Bigr)\\
&=\sum_{i=1}^{n-1}\frac{(m+1)!i!i!(-1)^{i-1}}{(i+m+1)!}\cdot \frac{m+1}{i+m+2}\sts{n-1}{i}.
\end{align*}
\end{proof}
\noindent Thus this lemma and the fact $c_{0,\, m}=1/(m+1)$ yield the next consequence immediately.
\begin{prop}
$$c_{n,\, m}=a_{n,\, m}.$$
\end{prop}
\begin{cor}
\begin{align*}
\frac{1}{m!}\sum_{i=0}^m(-1)^i\stf{m+1}{i+1}B_{n+i}(1)=\sum_{i=1}^n\frac{(m+1)!(i-1)!i!(-1)^{i-1}}{(i+m+1)!}\sts{n}{i},\qquad n\in \mbox{$\mathbb{N}$}.
\end{align*}
\end{cor}
\begin{proof}
It is clear from (\ref{eqn:anm}) and (\ref{eqn:cnm}).
\end{proof}

\section{Acknowledgements}
I should like to thank the referees for several comments and suggestions.

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

\bibitem{gkp} R. Graham, D. Knuth, and O. Patashnik,
{\textit{Concrete Mathematics}}, Addison-Wesley, 1989.

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

\bibitem{sjb} H. M. Srivastava, J. M. C. Joshi and C. S. Bisht, Fractional calculus
and the sum of powers of natural numbers, {\textit{Stud. Appl. Math.}} {\textbf{85}} (1991),
 183--193.

\end{thebibliography}

%\begin{flushright}
%{\small{\today, Typeset by \LaTeXe}}
%\end{flushright}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11Y55; Secondary 11B68 .\\

\noindent \emph{Keywords:} Bernoulli numbers, Stirling numbers, power sums.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 5 2005; 
revised version received  March 9 2005; April 1 2005; April 29 2005.
Published in {\it Journal of Integer Sequences}, May 15 2005.

\bigskip
\hrule
\bigskip

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


\end{document}