PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (23)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very high
sum of powers (Definition)

Introduction

A sum of powers is a number expressible in the form

$\displaystyle 1^p+2^p+\cdots + n^p$
where $ p$ and $ n$ are positive integers. Let us denote this sum by $ S_p(n)$. It is a well-known fact that when $ p=1$, then we have the following equality
$\displaystyle S_1(n):=1+2+\cdots +n = \frac{n(n+1)}{2}.$
In fact, a famous story goes that, when the teacher asked the students to sum up all the integers from 1 to 100, Gauss, at the age of 10, solved the problem immediately. Gauss realized that the sum can be written in two ways
$\displaystyle \underbrace{ \xymatrix@R=0pt@C=0pt{ &1& +&2& +&\cdots& + &n &&\\ ... ... \ &(n+1)& +&(n+1)& +&\cdots& + &(n+1) && }}_{\displaystyle{n}\mbox{ terms}} $
Therefore, $ 2S_1(n)=n(n+1)$ and hence the result: $ 1+2+\cdots+100=\frac{100(101)}{2}=50\cdot 100=5050$.

What Gauss did is actually a special case of a method that can be generalized to the case when $ p>1$. Thinking of a number $ i$ as $ 1$ added to itself $ i$ times, then using the following diagram:

$\displaystyle \xymatrix@R=0pt@C=0pt{ &1& && && & &&1&&\ &1& + &1& &&& &&2&&\\... ...[rrrrrrrr]&&&&&&& &\ar@{-}[rr]&& \ &n& +&(n-1)& +&\cdots& + &1 && S_1(n)&& } $
Using the summation notation, it then follows that
$\displaystyle \sum_{i=1}^n (n-i+1)=n+(n-1)+\cdots +1=S_1(n)=1+2+\cdots +n=\sum_{i=1}^n i.$
Then,
$\displaystyle S_1(n)=\sum_{i=1}^n (n-i+1) = \sum_{i=1}^n (n+1) - \sum_{i=1}^n i = (n+1)\sum_{i=1}^n 1 - S_1(n) = (n+1)n -S_1(n),$
and we have the same result.

Let us now apply this method to the case when $ p=2$. This time, we use the following diagram

$\displaystyle \xymatrix@R=0pt@C=0pt{ &1& && && & &&S_1(1)&&\ &1& + &2& &&& &&... ...& &\ar@{-}[rr]&& \ &n\cdot 1& +&(n-1)\cdot 2& +&\cdots& + &1\cdot n && T&& } $
Again, using the summation notation, we have
$\displaystyle \sum_{i=1}^n (n-i+1)i = T = \sum_{i=1}^n S_1(i) = \sum_{i=1}^n \frac{i(i+1)}{2}.$
Further algebraic manipulations give us the result:
$\displaystyle S_2(n):=1^2+2^2+\cdots n^2=\frac{n(n+1)(2n+1)}{6}.$

The general case

Using the method above, one can iteratively solve for $ S_3(n),S_4(n),\ldots$. This means that if we know the formulas for $ S_k(n)$ for all $ k<p$, then we can derive the formula for $ S_p(n)$. The formulas for $ p=3,4,5$ and $ 6$ are

$ p$ $ S_p(n)$
$ 3$ $ \displaystyle{\frac{n^2(n+1)^2}{4}}$
$ 4$ $ \displaystyle{\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}}$
$ 5$ $ \displaystyle{\frac{n^2(n+1)^2(2n^2+2n-1)}{12}}$
$ 6$ $ \displaystyle{\frac{n(n+1)(2n+1)(3n^4+6n^3-3n +1)}{42}}$

Remarks.

  1. Notice that the formula for each of the powers $ p=1,2,\ldots, 6$ is always a polynomial of degree $ p+1$. This is in fact true in the general case, and can be proved by the method of telescoping sum, together with induction: for each positive integer $ n$, define
    $\displaystyle x_n:=n^{p+1}-(n-1)^{p+1}.$
    Then $ x_n$ is expressible as a polynomial $ y(n)$ of degree $ p$ in $ n$. So
    $\displaystyle n^{p+1}=x_n+x_{n-1}+\cdots +x_1 = \sum_{i=1}^n y(i)=a_p \sum_{i=1}^n i^p + a_{p-1}\sum_{i=1}^n i^{p-1} + \cdots + a_0 \sum_{i=1}^n 1.$
    The right hand side is $ a_pS_p(n)+a_{p-1}S_{p-1}(n)+\cdots + a_0n$. By induction, each $ S_k(n)$ is a polynomial of degree $ k+1$ for all $ k<p$. But then right hand side is equal to the left hand side, which is a polynomial of degree $ p+1$. Therefore, $ S_p(n)$ is a polynomial of degree $ p+1$. So we can safely write
    $\displaystyle S_p(n)=b_0+b_1n+\cdots + b_{p+1}n^{p+1}.$
  2. Another property of $ S_p(n)$ is that $ b_0+b_1+\cdots + b_{p+1}=1$ for any $ p$. This is clear, since, one the one hand, $ S_p(1)=1$ as a sum of just one term $ 1^p$. On the other hand, its polynomial representation evaluated at $ n=1$ is just the sum of the coefficients.
  3. In addition, there are also two curious properties: These can be proved using the method above. For example, to show that $ n\vert S_p(n)$, use the expression
    $\displaystyle n^{p+1}= \sum_{i=1}^n y(i)=a_p \sum_{i=1}^n i^p + a_{p-1}\sum_{i=1}^n i^{p-1} + \cdots + a_0 \sum_{i=1}^n 1,$
    and notice that the left hand side is divisible by $ n$, and therefore so is the right hand side. Since all sums with powers $ k<p$ are divisible by $ n$ (induction), so is the sum with power $ p$, and hence $ n\vert S_p(n)$. From this, one also sees that
    $\displaystyle S_p(n)=\sum_{i=1}^n i^p=-(n+1)^p+\sum_{i=1}^{n+1} i^p $
    is divisible by $ n+1$ as well.
  4. For general $ p$, Jacques Bernoulli gave the formula for the coefficients: $ b_0=0$ and
    $\displaystyle b_i=\frac{B_{p+1-i}}{p+1}\binom{p+1}{i},$ (1)

    where $ B_k$ is the $ k$th Bernoulli number. The formula for $ S_p(n)$ using the polynomial representation with the coefficients $ b_i$ is called the Faulhaber's formula, since Faulhaber first wrote down the polynomial in this form in 1631 (without knowing the Bernoulli numbers).
  5. By (3) above, we see that $ S_p(n)$ can in fact be expressed as a polynomial in terms of $ (n+1)$ with no constant coefficient:
    $\displaystyle S_p(n)=T_p(n+1):=c_1(n+1)+c_2(n+1)^2+\cdots + c_{p+1}(n+1)^{p+1}.$
    The coefficient $ c_i$ takes on a form similar to but simpler than $ b_i$:
    $\displaystyle c_i=\frac{B_{p+1-i}}{p+1}\binom{p+1}{i}.$
  6. The Faulhaber's formula can actually be extended to all real numbers. In other words, $ S_p(x)$ (and correspondingly $ T_p(x)$) can be viewed as a polynomial of degree $ p+1$ in the real variable $ x$ with coefficients $ b_i$ described by $ (1)$. When $ x$ is some positive integer $ n$, we are back to the formula for the sum of $ p$th powers of integers $ 1$ through $ n$. In general, $ T_p(x)$ is the indefinite sum of $ x^p$:
    $\displaystyle T_p(x)=\Delta^{-1} x^p.$
  7. When $ p<0$, we have what is known as the $ p$-series of order $ n$ with the special case $ p=-1$ the harmonic series (of order $ n$). There are no polynomial representations for $ S_p(n)$ when $ p<0$.

For further properties of the sum of powers, see the refreshing article Sum of Powers of Integers.



"sum of powers" is owned by CWoo.
(view preamble | get metadata)

View style:

See Also: harmonic series, sum of $r$th powers of the first $n$ positive integers

Also defines:  Faulhaber's formula
Log in to rate this entry.
(view current ratings)

Cross-references: harmonic series, order, indefinite sum, variable, real numbers, similar, Bernoulli number, divisible, expression, even, iff, divide, addition, coefficients, representation, term, clear, property, left hand side, right hand side, induction, telescoping sum, degree, polynomial, powers, algebraic, diagram, Gauss, equality, sum, integers, positive, expressible, number
There are 5 references to this entry.

This is version 11 of sum of powers, born on 2007-10-23, modified 2008-06-30.
Object id is 10011, canonical name is SumOfPowers.
Accessed 2070 times total.

Classification:
AMS MSC: 40A05 (Sequences, series, summability :: Convergence and divergence of infinite limiting processes :: Convergence and divergence of series and sequences)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)