Sums of Consecutive Powers as a Linear Combination of Products of

Two Figurate Numbers

František Marko Department of Mathematics The Pennsylvania State University 76 University Drive Hazleton, PA 18202 USA

                     fxm13@psu.edu

Abstract

We derive two formulae expressing the pth 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 pth powers of the first n consecutive natural numbers as a linear combination of products of two figurate numbers of dimensions not exceeding p.

1 Introduction

For natural numbers n and r, we denote the figurate number of dimension r corresponding to n by

F_{n}^{r} = \binom{n + r − 1}{r}.

We also view F_{n}^{r} 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 pth powers of natural numbers by

s_{p}(n) = ∑_{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 [3, Chap. 1].

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}, …, F_{n}^{p}. A geometric representation of this expression was provided in Marko and Litvinov [6, Conj. 16]. This conjecture was proved in Marko and Cereceda [5]. 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 pth 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 1 and 2, we identify s_{p}(n) as a linear combination of products of two figurate numbers in Propositions 3 and 4.

2 Expressing powers as a linear combination of products of two figurate numbers

We start by recalling some well-known facts from DeTemple and Webb [2, Chap. 6]—see also Marko and Cereceda [5] and Marko, Litvinov, and Cereceda [6, 1]. We denote the Stirling number of the second kind by S(m, n). They are described as sequence \underline{A008277} in the On-Line Encyclopedia of Integer Sequences (OEIS)).

By DeTemple and Webb [2, (6.8)], 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 \underline{A019538}. According to DeTemple and Webb [2, Thm. 6.10], we have

n^{p} = ∑_{ℓ=1}^{p}(−1)^{p−ℓ}T (p, ℓ)F_{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.

Proposition 1. For a pair of natural numbers n and p, we express n^{p} as

n^{p} = (−1)^{p} ∑_{r=1}^{p}(−1)^{r}r^{p}F_{n}^{r}F_{n+r+1}^{p−r}.

Proof. Using DeTemple and Webb [2, (4.11)], we get

T (p, ℓ) = (−1)^{ℓ} ∑_{r=0}^{ℓ}(−1)^{r}\binom{ℓ}{r}r^{p},

which implies

\begin{aligned}n^{p} & = ∑_{ℓ=1}^{p}(−1)^{p} ∑_{r=0}^{ℓ}(−1)^{r}\binom{ℓ}{r}r^{p}\binom{n + ℓ − 1}{ℓ} \\ & = (−1)^{p} ∑_{ℓ=0}^{p} ∑_{r=0}^{ℓ}(−1)^{r}\binom{ℓ}{r}r^{p}\binom{n + ℓ − 1}{ℓ}. \end{aligned}

The last expression equals

\begin{matrix}(−1)^{p} ∑_{r=0}^{p}(−1)^{r}r^{p} ∑_{ℓ=r}^{p} \binom{ℓ}{r}\binom{n + ℓ − 1}{ℓ} \\ = (−1)^{p} ∑_{r=0}^{p}(−1)^{r}r^{p}\binom{n + r − 1}{r} ∑_{ℓ=r}^{p} \binom{n + ℓ − 1}{ℓ − r}, \end{matrix}

because

\binom{ℓ}{r}\binom{n + ℓ − 1}{ℓ} = \binom{n + r − 1}{r}\binom{n + ℓ − 1}{ℓ − r}.  (1)

Hence,

n^{p} = (−1)^{p} ∑_{r=0}^{p}(−1)^{r}r^{p}\binom{n + r − 1}{r} ∑_{j=0}^{p−r} \binom{n + r + j − 1}{j}.

Using the well-known identity ∑_{k=0}^{p} \binom{n+k−2}{k} = \binom{n+p−1}{p} we rewrite the last expression as

n^{p} = (−1)^{p} ∑_{r=1}^{p}(−1)^{r}r^{p}\binom{n + r − 1}{r}\binom{n + p}{p − r} = (−1)^{p} ∑_{r=1}^{p}(−1)^{r}r^{p}F_{n}^{r}F_{n+r+1}^{p−r}.

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.

Proposition 2. For a pair of natural numbers n and p, we express n^{p} as

n^{p} = (−1)^{p} ∑_{r=0}^{p} F_{n}^{r} ∑_{j=1}^{p−r}(−1)^{j}j^{p}F_{n+r}^{j}.

Proof. First, we use the formula in DeTemple and Webb [2, (4.11)]

(−1)^{j}T (p, j) = ∑_{k=0}^{j}(−1)^{k}\binom{j}{k}k^{p},

set r = j − k and derive

T (p, j) = ∑_{k=0}^{j}(−1)^{k−j}\binom{j}{k}k^{p} = ∑_{r=0}^{j}(−1)^{r}\binom{j}{r}(j − r)^{p}.

Using this, we write

\begin{aligned}n^{p} & = ∑_{ℓ=1}^{p}(−1)^{p−ℓ} ∑_{r=0}^{ℓ}(−1)^{r}\binom{ℓ}{r}(ℓ − r)^{p}\binom{n + ℓ − 1}{ℓ} \\ & = (−1)^{p} ∑_{ℓ=0}^{p} ∑_{r=0}^{ℓ}(−1)^{ℓ−r}\binom{ℓ}{r}(ℓ − r)^{p}\binom{n + ℓ − 1}{ℓ}. \end{aligned}  (2)

It follows from (1) that the last expression equals

\begin{matrix}(−1)^{p} ∑_{r=0}^{p} ∑_{ℓ=r}^{p}(−1)^{ℓ−r}(ℓ − r)^{p}\binom{ℓ}{r}\binom{n + ℓ − 1}{ℓ} \\ = (−1)^{p} ∑_{r=0}^{p} \binom{n + r − 1}{r} ∑_{ℓ=r}^{p}(−1)^{ℓ−r}(ℓ − r)^{p}\binom{n + ℓ − 1}{ℓ − r}. \end{matrix}

Hence, setting j = ℓ − r, we obtain

\begin{aligned}n^{p} & = (−1)^{p} ∑_{r=0}^{p} \binom{n + r − 1}{r} ∑_{j=1}^{p−r}(−1)^{j}j^{p}\binom{n + r + j − 1}{j} \\ & = (−1)^{p} ∑_{r=0}^{p} F_{n}^{r} ∑_{j=1}^{p−r}(−1)^{j}j^{p}F_{n+r}^{j} \end{aligned}.

Note that in the last formula, the product F_{n}^{r}F_{n+r}^{j} is a polynomial in n of degree not exceeding p.

Observe that the coefficient corresponding to r = 0 in the formula in Proposition 1 vanishes, while the coefficient in the formula in Proposition 2 is ∑_{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)^{p}p^{p}}{p!} ≠ 0. Therefore, the formulae in Propositions 1 and 2 are genuinely different.

3 Expressing sums of consecutive powers as a linear combination of products of two figurate numbers

Since the sum ∑_{i=1}^{n} F_{i}^{ℓ} of figurate numbers of dimension ℓ is the figurate number F_{n}^{ℓ+1} of dimension ℓ + 1, one can expect that formulae analogous to those exhibited in Propositions 1 and 2 can be derived for s_{p}(n) instead of n^{p}.

It is well-known that

s_{p}(n) = ∑_{j=1}^{p+1} d_{j,p}F_{n}^{j}  (3)

is a linear combination of figurate numbers F_{n}^{1}, …, 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, …, n^{p}} to {F_{n}^{1}, …, F_{n}^{p}} by A_{p}. Then it was proved in Marko and Litvinov [6] that the transition matrix from the basis {s_{0}(n), …, s_{p}(n)} to {F_{n}^{1}, …, F_{n}^{p+1}} is given as

( \begin{matrix}1 & 0 \\ 0 & A_{p}^{−1} \end{matrix} ) .

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ó [4, 7] 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 [4, Thm. 3] or Szabó [7], stating

2s_{2m+1}(n) = ∑_{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{1}{2} ∑_{k=1}^{2m−1}(−1)^{k−1}\binom{2m}{k} ∑_{a=1}^{k+1} d_{a,k} ∑_{b=1}^{2m−k+1} d_{b,2m−k}F_{n}^{a}F_{n}^{b}.

Using MacDougall [4, Thm. 4], stating

2ms_{2m+1}(n) = ∑_{k=1}^{2m−1}(−1)^{k−1}k\binom{2m}{k}s_{k}(n)s_{2m−k}(n)

and applying formula (3) twice, we can express

s_{2m+1}(n) = \frac{1}{2m} ∑_{k=1}^{2m−1}(−1)^{k−1}k\binom{2m}{k} ∑_{a=1}^{k+1} d_{a,k} ∑_{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 1.

Proposition 3. For a pair of natural numbers n and p, we express s_{p}(n) as

s_{p}(n) = (−1)^{p} ∑_{r=1}^{p}(−1)^{r}(n + r)r^{p}F_{n}^{r} ∑_{j=0}^{p−r} \frac{F_{n+r+1}^{j}}{j + r + 1}.

Proof. Using (2), we rewrite the sum

s_{p}(n) = (−1)^{p} ∑_{ℓ=0}^{p} ∑_{r=0}^{ℓ}(−1)^{r}\binom{ℓ}{r}r^{p} ∑_{i=1}^{n} \binom{i + ℓ − 1}{ℓ}

= (−1)^{p} ∑_{ℓ=0}^{p} ∑_{r=0}^{ℓ}(−1)^{r}\binom{ℓ}{r}r^{p}\binom{n + ℓ}{ℓ + 1}

= (−1)^{p} ∑_{ℓ=0}^{p} ∑_{r=0}^{ℓ}(−1)^{r}(n + r)r^{p}\binom{n + r − 1}{r}\frac{\binom{n+ℓ}{ℓ−r}}{ℓ + 1}

= (−1)^{p} ∑_{r=0}^{p}(−1)^{r}(n + r)r^{p}\binom{n + r − 1}{r} ∑_{ℓ=r}^{p} \frac{\binom{n+ℓ}{ℓ−r}}{ℓ + 1},

utilizing

∑_{i=1}^{n} \binom{i + ℓ − 1}{ℓ} = \binom{n + ℓ}{ℓ + 1}  (4)

and

\binom{ℓ}{r}\binom{n + ℓ}{ℓ + 1} = (n + r)\binom{n + r − 1}{r}\frac{\binom{n+ℓ}{ℓ−r}}{ℓ + 1}.  (5)

Hence, setting j = ℓ − r, we obtain

\begin{aligned}s_{p}(n) & = (−1)^{p} ∑_{r=1}^{p}(−1)^{r}(n + r)r^{p}\binom{n + r − 1}{r} ∑_{j=0}^{p−r} \frac{\binom{n+r+j}{j}}{j + r + 1} \\ & = (−1)^{p} ∑_{r=1}^{p}(−1)^{r}(n + r)r^{p}F_{n}^{r} ∑_{j=0}^{p−r} \frac{F_{n+r+1}^{j}}{j + r + 1}. \end{aligned}

When we modify the arguments in Proposition 2 instead of Proposition 1, we obtain the following result.

Proposition 4. For a pair of natural numbers n and p, we express s_{p}(n) as

s_{p}(n) = (−1)^{p} ∑_{r=0}^{p}(n + r)F_{n}^{r} ∑_{j=1}^{p−r}(−1)^{j}j^{p} \frac{F_{n+r+1}^{j}}{j + r + 1}.

Proof. Since

\begin{aligned}i^{p} & = ∑_{ℓ=1}^{p}(−1)^{p−ℓ} ∑_{r=0}^{ℓ}(−1)^{r}\binom{ℓ}{r}(ℓ − r)^{p}\binom{i + ℓ − 1}{ℓ} \\ & = (−1)^{p} ∑_{ℓ=0}^{p} ∑_{r=0}^{ℓ}(−1)^{ℓ−r}\binom{ℓ}{r}(ℓ − r)^{p}\binom{i + ℓ − 1}{ℓ}, \end{aligned}

the sum

s_{p}(n) = (−1)^{p} ∑_{r=0}^{p} ∑_{ℓ=r}^{p}(−1)^{ℓ−r}(ℓ − r)^{p}\binom{ℓ}{r} ∑_{i=1}^{n} \binom{i + ℓ − 1}{ℓ}

= (−1)^{p} ∑_{r=0}^{p} ∑_{ℓ=r}^{p}(−1)^{ℓ−r}(ℓ − r)^{p}\binom{ℓ}{r}\binom{n + ℓ}{ℓ + 1}

= (−1)^{p} ∑_{r=0}^{p} ∑_{ℓ=r}^{p}(n + r)\binom{n + r − 1}{r}(−1)^{ℓ−r}(ℓ − r)^{p} \frac{\binom{n+ℓ}{ℓ−r}}{ℓ + 1}

= (−1)^{p} ∑_{r=0}^{p}(n + r)\binom{n + r − 1}{r} ∑_{ℓ=r}^{p}(−1)^{ℓ−r}(ℓ − r)^{p} \frac{\binom{n+ℓ}{ℓ−r}}{ℓ + 1}

by application of formulae (4) and (5).

Therefore, making a substitution j = ℓ − r, we obtain

\begin{aligned}s_{p}(n) & = (−1)^{p} ∑_{r=0}^{p}(n + r)\binom{n + r − 1}{r} ∑_{j=1}^{p−r}(−1)^{j}j^{p} \frac{\binom{n+r+j}{j}}{j + r + 1} \\ & = (−1)^{p} ∑_{r=0}^{p}(n + r)F_{n}^{r} ∑_{j=1}^{p−r}(−1)^{j}j^{p} \frac{F_{n+r+1}^{j}}{j + r + 1}. \end{aligned}

Note that in the last formula, the product F_{n}^{r}F_{n+r+1}^{j} is a polynomial in n of degree not exceeding p.

Since the coefficient corresponding to r = 0 in the formula in Proposition 3 vanishes, while in the formula in Proposition 4 it is ∑_{j=1}^{p}(−1)^{j}j^{p} \frac{F_{n+1}^{j}}{j+1} . If we consider the last sum as a polynomial in n, the leading coefficient is \frac{(−1)^{p}p^{p}}{(p+1)!} ≠ 0. Thus, formulae in Propositions 3 and 4 are indeed different.

References

[1] J. L. Cereceda, Figurate numbers and sums of powers of integers, preprint, 2020. Avail-

   able at http://arxiv.org/abs/2001.03208.

[2] D. DeTemple and W. Webb, Combinatorial Reasoning. An Introduction to the Art of Counting, John Wiley & Sons, 2014.

[3] A. W. F. Edwards, Pascal’s Arithmetical Triangle. The Story of a Mathematical Idea. Revised reprint of the 1987 original, Johns Hopkins Press, 2002.

[4] J. A. MacDougall, Identities relating sums of powers of integers—an exercise in generalization, Australian Senior Math. J. 2 (1988), 53–62.

[5] F. Marko and J. L. Cereceda, A note on the geometry of figurate numbers, Amer. Math. Monthly 128 (2021), 461–463.

[6] F. Marko and S. Litvinov, Geometry of figurate numbers and sums of powers of consecutive natural numbers. Amer. Math. Monthly 127 (2020), 4–22.

[7] L. I. Szabó, Some equations concerning the sums of powers of integers, Acta Sci. Math. (Szeged) 67 (2001), 501–503.

2010 Mathematics Subject Classification: Primary 11B57; Secondary 11B73. Keywords: figurate number, sum of powers of integers.

(Concerned with sequences \underline{A008277} and \underline{A019538}.)

Received July 25 2021; revised version received, March 6 2022. Published in Journal of Integer Sequences, March 6 2022.

Return to Journal of Integer Sequences home page.