\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \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
Sums of Consecutive Powers as a \\
Linear Combination of Products of\\
\vskip .15in
Two Figurate Numbers
}
\vskip 1cm
\large
Franti\v sek Marko\\
Department of Mathematics\\
The Pennsylvania State University\\
76 University Drive\\ Hazleton, PA 18202 \\
USA\\
\href{mailto:fxm13@psu.edu}{\tt fxm13@psu.edu}
\end{center}
\vskip .2in
\begin{abstract}
We derive two formulae expressing the $p$th power of an integer $n$ as a linear combination of products of two figurate numbers of dimensions not exceeding $p$. Then we derive two formulae for the sum of the $p$th powers of the first $n$ consecutive natural numbers as a linear combination of products of two figurate numbers of dimensions not exceeding $p$.
\end{abstract}
\vskip .2in
\section{Introduction}
For natural numbers $n$ and $r$, we denote the figurate number of dimension $r$ corresponding to $n$
by \[F^r_n=\binom{n+r-1}{r}.\]
We also view $F^r_n$ as a polynomial in $n$ of degree $r$.
For a non-negative integer $p$ and a natural number $n$, we denote the sum of the first $n$ consecutive $p$th powers of natural numbers by \[s_p(n)=\sum_{i=1}^n i^p.\]
Finding a closed form for the expression $s_p(n)$ is a classical problem. An excellent source for the history of figurate numbers and their connections to sum $s_p(n)$ is Edwards \cite[Chap.\ 1]{ed}.
Fix a non-negative integer $p$ and consider the natural number $n$ as indeterminate. It is well-known that $n^p$ can be expressed as a unique linear combination of the figurate numbers $F_n^0, \ldots, F_n^p$. A geometric representation of this expression was provided in Marko and Litvinov \cite[Conj.\ 16]{ml}. This conjecture was proved in Marko and Cereceda \cite{mc}. The coefficients in the above linear combinations are related to Stirling numbers, and their description is not straightforward.
In this paper, we express these coefficients as another linear combination of figurate numbers. Consequently, we obtain a presentation of $n^p$ as a linear combination of products of two figurate numbers. The upshot is that the coefficients in the resulting linear combination are, up to a sign, just $p$th powers of natural numbers.
In the second half of the paper, using the formula expressing $n^p$ as a linear combination of products of two figurate numbers in Propositions \ref{l1} and \ref{l2}, we identify $s_p(n)$ as a linear combination of products of two figurate numbers in Propositions \ref{l3} and \ref{l4}.
\section{Expressing powers as a linear combination of \\
products of two figurate numbers}
We start by recalling some well-known facts from DeTemple and Webb \cite[Chap.\ 6]{dw}---see also Marko and Cereceda \cite{mc} and Marko, Litvinov, and Cereceda \cite{ml,cer}.
We denote the Stirling number of the second kind by $S(m,n)$.
They are described as sequence \seqnum{A008277} in the On-Line Encyclopedia of Integer Sequences (OEIS)).
By DeTemple and Webb \cite[(6.8)]{dw}, $T(m,n)=n! S(m,n)$ describes
the number of ways that $m$ distinct objects can be distributed to $n$ different recipients
so that each recipient is given at least one of the objects. The numbers $T(m,n)$ are described by sequence \seqnum{A019538}.
According to DeTemple and Webb \cite[Thm.\ 6.10]{dw}, we have
\[n^p=\sum_{\ell=1}^p (-1)^{p-\ell} T(p,\ell) F^\ell_n.\]
Using the last expression, we can write the power $n^p$ as a linear combination of products of two figurate numbers of dimensions not exceeding $p$.
\begin{proposition}
\label{l1}For a pair of natural numbers $n$ and $p$, we express $n^p$ as
\[n^p=(-1)^p\sum_{r=1}^p (-1)^r r^p F^r_n F^{p-r}_{n+r+1}.\]
\end{proposition}
\begin{proof}
Using DeTemple and Webb \cite[(4.11)]{dw}, we get
\[T(p,\ell)=(-1)^\ell \sum_{r=0}^{\ell} (-1)^r \binom{\ell}{r}r^p,\]
which implies
\[\begin{aligned}n^p&=\sum_{\ell=1}^p (-1)^{p} \sum_{r=0}^{\ell} (-1)^r \binom{\ell}{r} r^p \binom{n+\ell-1}{\ell}\\
&=(-1)^p\sum_{\ell=0}^p \sum_{r=0}^{\ell} (-1)^r \binom{\ell}{r} r^p \binom{n+\ell-1}{\ell}.
\end{aligned}\]
The last expression equals
\[\begin{aligned}&(-1)^p\sum_{r=0}^p (-1)^r r^p\sum_{\ell=r}^p \binom{\ell}{r}\binom{n+\ell-1}{\ell}\\
&=(-1)^p \sum_{r=0}^p (-1)^r r^p \binom{n+r-1}{r} \sum_{\ell=r}^p \binom{n+\ell-1}{\ell-r},
\end{aligned}\]
because
\begin{equation}\label{e1}
\binom{\ell}{r}\binom{n+\ell-1}{\ell}= \binom{n+r-1}{r} \binom{n+\ell-1}{\ell-r}.
\end{equation}
Hence,
\[n^p=(-1)^p \sum_{r=0}^p (-1)^r r^p \binom{n+r-1}{r} \sum_{j=0}^{p-r} \binom{n+r+j-1}{j}.\]
Using the well-known identity $\sum_{k=0}^p \binom{n+k-2}{k}=\binom{n+p-1}{p}$ we rewrite the last expression as
\[n^p=(-1)^p\sum_{r=1}^p (-1)^r r^p \binom{n+r-1}{r} \binom{n+p}{p-r}=(-1)^p\sum_{r=1}^p (-1)^r r^p F^r_n F^{p-r}_{n+r+1}.\]
\end{proof}
After reviewing the formula from the above proposition, it is natural to ask whether we can express $n^p$ as a linear combination of products of two figurate numbers of dimensions $r,s$ such that the sum $r+s$ does not exceed $p$.
We exhibit such a formula in the following proposition by slightly modifying our previous arguments.
\begin{proposition}\label{l2}
For a pair of natural numbers $n$ and $p$, we express $n^p$ as
\[n^p=(-1)^p\sum_{r=0}^p F^r_n \sum_{j=1}^{p-r} (-1)^j j^p F^j_{n+r}.\]
\end{proposition}
\begin{proof}
First, we use the formula in DeTemple and Webb \cite[(4.11)]{dw}
\[(-1)^j T(p,j)= \sum_{k=0}^j (-1)^k \binom{j}{k}k^p,\]
set $r=j-k$ and derive
\[
T(p,j)=\sum_{k=0}^j (-1)^{k-j} \binom{j}{k}k^p=\sum_{r=0}^j (-1)^{r} \binom{j}{r} (j-r)^p.
\]
Using this, we write
\begin{equation}
\begin{aligned}n^p&=\sum_{\ell=1}^p (-1)^{p-\ell} \sum_{r=0}^{\ell} (-1)^{r} \binom{\ell}{r} (\ell-r)^p \binom{n+\ell-1}{\ell}\\
&\label{e2}=(-1)^p\sum_{\ell=0}^p \sum_{r=0}^{\ell} (-1)^{\ell-r} \binom{\ell}{r} (\ell-r)^p \binom{n+\ell-1}{\ell}.
\end{aligned}
\end{equation}
It follows from \eqref{e1} that the last expression equals
\[\begin{aligned}&(-1)^p\sum_{r=0}^p \sum_{\ell=r}^p (-1)^{\ell-r} (\ell-r)^p \binom{\ell}{r}\binom{n+\ell-1}{\ell}\\
&=(-1)^p \sum_{r=0}^p \binom{n+r-1}{r}\sum_{\ell=r}^p (-1)^{\ell-r} (\ell-r)^p \binom{n+\ell-1}{\ell-r}.\end{aligned}
\]
Hence, setting $j=\ell-r$, we obtain
\[\begin{aligned}n^p&=(-1)^p \sum_{r=0}^p \binom{n+r-1}{r} \sum_{j=1}^{p-r}(-1)^{j} j^p \binom{n+r+j-1}{j}\\&=(-1)^p \sum_{r=0}^p F^r_n \sum_{j=1}^{p-r}(-1)^{j} j^p F^{j}_{n+r}\end{aligned}
.\]
Note that in the last formula, the product $F^r_nF^{j}_{n+r}$ is a polynomial in $n$ of degree not exceeding $p$.
\end{proof}
Observe that the coefficient corresponding to $r=0$ in the formula in Proposition \ref{l1} vanishes, while the coefficient in the formula in Proposition \ref{l2} is $\sum_{j=1}^{p} (-1)^j j^p F_{n}^j$. If we consider this sum as a polynomial in $n$, its leading coefficient is $\frac{(-1)^pp^p}{p!}\neq 0$. Therefore, the formulae in Propositions \ref{l1} and \ref{l2} are genuinely different.
\section{Expressing sums of consecutive powers as a linear combination of products of two figurate numbers}
Since the sum $\sum_{i=1}^n F_i^{\ell}$ of figurate numbers of dimension $\ell$ is the figurate number $F_n^{\ell+1}$ of dimension $\ell +1$, one can expect that formulae analogous to those exhibited in Propositions \ref{l1} and \ref{l2} can be derived for $s_p(n)$ instead of $n^p$.
It is well-known that
\begin{equation} \label{e3}
s_p(n)=\sum_{j=1}^{p+1} d_{j,p} F_n^j
\end{equation} is a linear combination of figurate numbers $F_n^1, \ldots, F_n^{p+1}$. The coefficients $d_{j,p}$ are related to Bernoulli numbers and are not easy to understand. One way to express the coefficients $d_{j,p}$ is as follows.
We denote the transition matrix from the basis $\{n, \ldots , n^p\}$ to $\{F^1_n , \ldots , F^p_n\}$ by $A_p$.
Then it was proved in Marko and Litvinov \cite{ml} that the transition matrix from the basis $\{s_0(n), \ldots, s_p(n)\}$ to $\{F_n^1, \ldots, F_n^{p+1}\}$
is given as
\[\left(
\begin{array}{c|c}
1 & 0 \\ \hline
0 & A_p^{-1}
\end{array}
\right).
\]
The coefficients $d_{j,p}$ appear in the last column of the above matrix.
The author thanks J. L. Cereceda for bringing the papers MacDougall and Szab\'o \cite{mac,szabo} to his attention. He pointed out that it is possible to express the sums $s_p(n)$, for odd $p$, as a linear combination of products of two figurate numbers by using their results. The explicit expressions are given as follows.
Using MacDougall \cite[Thm.\ 3]{mac} or Szab\'o \cite{szabo}, stating
\[2s_{2m+1}(n)=\sum_{k=1}^{2m-1}(-1)^{k-1}\binom{2m}{k} s_k(n)s_{2m-k}(n),
\]
we can express the sums $s_{2m+1}(n)$ as a linear combination of products of two figurate numbers as
\[s_{2m+1}(n)= \frac 12\sum_{k=1}^{2m-1}(-1)^{k-1}\binom{2m}{k} \sum_{a=1}^{k+1} d_{a,k} \sum_{b=1}^{2m-k+1}
d_{b,2m-k} F_n^a F_n^b.\]
Using MacDougall \cite[Thm.\ 4]{mac}, stating
\[2m s_{2m+1}(n)=\sum_{k=1}^{2m-1} (-1)^{k-1} k\binom{2m}{k} s_k(n)s_{2m-k}(n)
\]
and applying formula \eqref{e3} twice, we can express
\[s_{2m+1}(n)=\frac{1}{2m} \sum_{k=1}^{2m-1}(-1)^{k-1} k \binom{2m}{k} \sum_{a=1}^{k+1} d_{a,k} \sum_{b=1}^{2m-k+1}
d_{b,2m-k} F_n^a F_n^b.\]
We obtain a more straightforward and general presentation of $s_p(n)$ for all $p$ as a linear combination of products of two figure numbers analogously to Proposition \ref{l1}.
\begin{proposition}\label{l3}
For a pair of natural numbers $n$ and $p$, we express $s_p(n)$ as
\[s_p(n)=(-1)^p \sum_{r=1}^p (-1)^r (n+r)r^p F^r_n \sum_{j=0}^{p-r} \frac{F^{j}_{n+r+1}}{j+r+1}.\]
\end{proposition}
\begin{proof}
Using \eqref{e2}, we rewrite
the sum
\[\begin{aligned}s_p(n)&=(-1)^p\sum_{\ell=0}^p \sum_{r=0}^{\ell} (-1)^r \binom{\ell}{r} r^p \sum_{i=1}^n
\binom{i+\ell-1}{\ell}\\
&=(-1)^p\sum_{\ell=0}^p \sum_{r=0}^{\ell} (-1)^r \binom{\ell}{r} r^p \binom{n+\ell}{\ell+1}\\
&=(-1)^p \sum_{\ell=0}^p \sum_{r=0}^{\ell} (-1)^r (n+r)r^p\binom{n+r-1}{r} \frac{\binom{n+\ell}{\ell-r}}{\ell+1}\\
&=(-1)^p \sum_{r=0}^p (-1)^r (n+r) r^p \binom{n+r-1}{r}\sum_{\ell=r}^p \frac{\binom{n+\ell}{\ell-r}}{\ell+1},
\end{aligned}\]
utilizing
\begin{equation}\label{e4}\sum_{i=1}^n \binom{i+\ell-1}{\ell} =\binom{n+\ell}{\ell+1}
\end{equation} and
\begin{equation}\label{e5}\binom{\ell}{r}\binom{n+\ell}{\ell+1} = (n+r)\binom{n+r-1}{r} \frac{\binom{n+\ell}{\ell-r}}{\ell+1}.\end{equation}
Hence, setting $j=\ell-r$, we obtain
\[\begin{aligned}s_p(n)&=(-1)^p \sum_{r=1}^p (-1)^r (n+r)r^p \binom{n+r-1}{r} \sum_{j=0}^{p-r} \frac{\binom{n+r+j}{j}}{j+r+1}\\
&=(-1)^p \sum_{r=1}^p (-1)^r (n+r)r^p F^r_n \sum_{j=0}^{p-r} \frac{F^{j}_{n+r+1}}{j+r+1}.\end{aligned}\]
\end{proof}
When we modify the arguments in Proposition \ref{l2} instead of Proposition \ref{l1}, we obtain the following result.
\begin{proposition}\label{l4}
For a pair of natural numbers $n$ and $p$, we express $s_p(n)$ as
\[s_p(n)=(-1)^p \sum_{r=0}^p (n+r)F^r_n \sum_{j=1}^{p-r}(-1)^{j} j^p \frac{F^{j}_{n+r+1}}{j+r+1}.\]
\end{proposition}
\begin{proof}
Since
\[\begin{aligned}i^p&=\sum_{\ell=1}^p (-1)^{p-\ell} \sum_{r=0}^{\ell} (-1)^{r} \binom{\ell}{r} (\ell-r)^p \binom{i+\ell-1}{\ell}\\
&=(-1)^p\sum_{\ell=0}^p \sum_{r=0}^{\ell} (-1)^{\ell-r} \binom{\ell}{r} (\ell-r)^p \binom{i+\ell-1}{\ell},
\end{aligned}
\]
the sum
\[\begin{aligned}s_p(n)&=(-1)^p\sum_{r=0}^p \sum_{\ell=r}^p (-1)^{\ell-r} (\ell-r)^p \binom{\ell}{r}\sum_{i=1}^n \binom{i+\ell-1}{\ell}\\
&=(-1)^p\sum_{r=0}^p \sum_{\ell=r}^p (-1)^{\ell-r} (\ell-r)^p \binom{\ell}{r} \binom{n+\ell}{\ell+1}\\
&=(-1)^p\sum_{r=0}^p \sum_{\ell=r}^p (n+r)\binom{n+r-1}{r} (-1)^{\ell-r} (\ell-r)^p \frac{\binom{n+\ell}{\ell-r}}{\ell+1}\\
&=(-1)^p \sum_{r=0}^p (n+r) \binom{n+r-1}{r} \sum_{\ell=r}^p (-1)^{\ell-r} (\ell-r)^p \frac{\binom{n+\ell}{\ell-r}}{\ell+1}
\end{aligned}\]
by application of formulae \eqref{e4} and \eqref{e5}.
Therefore, making a substitution $j=\ell-r$, we obtain
\[\begin{aligned}s_p(n)&=(-1)^p \sum_{r=0}^p (n+r)\binom{n+r-1}{r}\sum_{j=1}^{p-r}(-1)^{j} j^p \frac{\binom{n+r+j}{j}}{j+r+1}\\
&=(-1)^p \sum_{r=0}^p (n+r)F^r_n \sum_{j=1}^{p-r}(-1)^{j} j^p \frac{F^{j}_{n+r+1}}{j+r+1}.\end{aligned}\]
Note that in the last formula, the product $F^r_nF^{j}_{n+r+1}$ is a polynomial in $n$ of degree not exceeding $p$.
\end{proof}
Since the coefficient corresponding to $r=0$ in the formula in Proposition \ref{l3} vanishes, while in the formula in Proposition \ref{l4} it is
$\sum_{j=1}^{p}(-1)^{j} j^p \frac{F^{j}_{n+1}}{j+1}$.
If we consider the last sum as a polynomial in $n$, the leading coefficient is $\frac{(-1)^pp^p}{(p+1)!} \neq 0$. Thus, formulae in Propositions \ref{l3} and \ref{l4} are indeed different.
\begin{thebibliography}{9}
\bibitem{cer} J. L. Cereceda, Figurate numbers and sums of powers of integers, preprint, 2020. Available at \url{http://arxiv.org/abs/2001.03208}.
\bibitem{dw}D. DeTemple and W. Webb, \textit{Combinatorial Reasoning. An Introduction to the Art of Counting,} John Wiley \& Sons, 2014.
\bibitem{ed} A. W. F. Edwards, \textit{Pascal's Arithmetical
Triangle. The Story of a Mathematical Idea.} Revised reprint of the 1987
original, Johns Hopkins Press, 2002.
\bibitem{mac} J. A. MacDougall, Identities relating sums of powers of integers---an exercise in generalization, \textit{Australian Senior Math. J.} {\bf 2} (1988), 53--62.
\bibitem{mc} F. Marko and J. L. Cereceda, A note on the geometry of figurate numbers, \textit{Amer. Math. Monthly}
{\bf 128} (2021), 461--463.
\bibitem{ml} F. Marko and S. Litvinov, Geometry of figurate numbers and sums of powers of consecutive natural numbers. \textit{Amer. Math. Monthly} {\bf 127} (2020), 4--22.
\bibitem{szabo} L. I. Szab\'o, Some equations concerning the sums of powers of integers, \textit{Acta Sci. Math. (Szeged)} {\bf 67} (2001), 501--503.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: {Primary 11B57; Secondary 11B73.}
\noindent \emph{Keywords: } figurate number, sum of powers of integers.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A008277} and
\seqnum{A019538}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received July 25 2021;
revised version received, March 6 2022.
Published in {\it Journal of Integer Sequences}, March 6 2022.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}