19
$\begingroup$

I'm studying in the summer for calculus 2 in the fall and I'm reading about summation. I'm given these formulas: \begin{align*} \sum_{i=1}^n 1 &= n, \\ \sum_{i=1}^n i &= \frac{n(n+1)}{2},\\ \sum_{i=1}^n i^2 &= \frac{n(n+1)(2n+1)}{6},\\ \sum_{i=1}^n i^3 &=\left[ \frac{n(n+1)}{2}\right]^2. \end{align*}

But how do I come up with the right formula for exponents greater than 3?

$\endgroup$
  • 4
    $\begingroup$ Consider examining Faulhaber's Theorem: theoremoftheday.org/Binomial/Faulhaber/TotDFaulhaber.pdf $\endgroup$ – pMarkov Jul 8 '15 at 0:30
  • $\begingroup$ thanks for your input ill look into it $\endgroup$ – JRowan Jul 8 '15 at 0:37
  • 1
    $\begingroup$ I think is a bad idea to see Faulhaber formula by itself... you will not improve any knowledge or understanding, you only will see a recipe. The key point is understand Bernoulli polynomials that are the solution for the equation $\Delta f_n (k)=nk^{n-1}$ where $f_n(k)$ are polynomials of degree n (the Bernoulli polynomials) and after see the relation with this question. You can try the first pages of this text by example. $\endgroup$ – Masacroso Jul 8 '15 at 2:08
  • $\begingroup$ Perhaps one should also ask, does one even want to (in Calculus 2). In calculating a Riemann sum, we only need to know the coefficient on the leading term of the formula (since the other terms go to zero as $n$ becomes arbitrarily large). For example $$\sum^{n}_{i=1}i^2 = \frac{1}{3}n^3+an^2+bn+c$$ is sufficient for calculating the area under a parabola. $\endgroup$ – John Joy Jul 8 '15 at 14:48
23
$\begingroup$

You can obtain these formulae recursively. Look at this

$$n^5 = \sum_{k=1}^n \left( k^5 - (k-1)^5\right) $$

Expand the second term. Cancel the $k^5$ terms. Then apply the identities above. You can solve for $\sum_{k=1}^n k^4$. Continue in this fashion to get sums for higher powers.

$\endgroup$
  • $\begingroup$ for that i got 5k^4 -10k^3+10k^2 - 5k + 1, is that right for i^4 $\endgroup$ – JRowan Jul 8 '15 at 0:50
  • $\begingroup$ Now distribute the sum over these and substitute in the lower order sums. the sum of $k^4$ will be all by itself; solve for it. $\endgroup$ – ncmathsadist Jul 8 '15 at 1:03
  • $\begingroup$ This is amazing $\endgroup$ – user217285 Jul 8 '15 at 2:05
  • $\begingroup$ @Nitin: See my answer for an alternative method that is equally simple to use and more efficient in computing the answer, besides generalizing to other summations. Of course, its correctness relies on slightly more advanced concepts. $\endgroup$ – user21820 Jul 8 '15 at 11:38
  • $\begingroup$ This is clean and you can "see to the bottom." $\endgroup$ – ncmathsadist Jul 8 '15 at 21:59
5
$\begingroup$

General method for indefinite summation $\def\nn{\mathbb{N}}$ $\def\zz{\mathbb{Z}}$

Define the forward difference operator:

$D = ( \text{function $f$ on $\zz$} \mapsto ( \text{int $n$} \mapsto f(n+1) - f(n) ) )$

Namely for any function $f$ on $\zz$ and $n \in \zz$, $D(f)(n) = f(n+1) - f(n)$.

If you think of the functions as sequences (infinite in both directions), then taking the forward difference means replacing each term with the value of the next term minus itself. For example the following shows what happens when you repeatedly take the forward difference of the sequence of cubes:

...,-27,-8,-1, 0, 1, 8,27,...
..., 19, 7, 1, 1, 7,19,37,...
...,-12,-6, 0, 6,12,18,24,...
...,  6, 6, 6, 6, 6, 6, 6,...
...,  0, 0, 0, 0, 0, 0, 0,...
...,  0, 0, 0, 0, 0, 0, 0,...

Then we have:

$D\left( \text{int $n$} \mapsto \binom{n}{k+1} \right) = \left( \text{int $n$} \mapsto \binom{n}{k} \right)$ for any $k \in \zz$.

This is to be expected because it follows directly from Pascal's triangle, especially if we define $\binom{n}{k}$ using the triangle.

This means that if we have any function $f$ on $\zz$ such that $f(n) = \sum_{k=0}^\infty a_k \binom{n}{k}$ for any $n \in \zz$, then we get:

$D(f)(n) = \sum_{k=0}^\infty a_{k+1} \binom{n}{k}$ for any $n \in \zz$.

From a high-level perspective, this is the discrete version of the Taylor series, and indeed for such a function we easily see that $f(n) = \sum_{k=0}^\infty D^k(f)(0) \binom{n}{k}$ for any $n \in \zz$, because $\binom{0}{0} = 1$ while $\binom{0}{k} = 0$ for any $k \in \nn^+$.

This works for any polynomial function $f$ on $\zz$, since $D^k(f)$ is the zero function once $k$ is larger than the degree of $f$, so we can use it to immediately find the series for $(\text{int n} \mapsto n^3)$, and then just take the anti-difference by shifting the coefficients of the series the other way. The undetermined constant that appears will drop out once we perform a definite sum like if we want the sum of the first $m$ cubes.

Sum of $p$ powers

For example if we want $\sum_{k=1}^{n-1} k^2$ we first find the iterated forward differences of the sequence of squares $( n^2 )_{n \in \zz}$:

...,0,1,4,9,...
...,1,3,5,...
...,2,2,...
...,0,...

So we immediately get $n^2 = 0 \binom{n}{0} + 1 \binom{n}{1} + 2 \binom{n}{2}$ and hence $\sum_{k=0}^{n-1} = 0 \binom{n}{1} + 1 \binom{n}{2} + 2 \binom{n}{3}$. It is trivial to simplify it to $\sum_{k=0}^{n-1} = \frac{1}{6}(n-1)n(2n-1)$.

Computation efficiency

This is far more efficient than the method given by ncmathsadist because the series using binomial coefficients is easy to manipulate and easy to compute. For sum of $p$-powers we only need $O(p^2)$ arithmetic operations to find the forward-differences and then $O(p^2)$ more to simplify the series form into a standard polynomial form. In contrast, the other method requires $O(p^3)$ arithmetic operations.

Indefinite summation of non-polynomials

Also, for a wide class of non-polynomial functions, we can still compute the indefinite sum without using the series, by using the discrete analogue to integration by parts, here called summation by parts.

To derive it, simply check that $D(f \times g)(n) = f(n+1) g(n+1) - f(n) g(n) = f(n+1) D(g)(n) - D(f)(n) g(n)$ and so we get the product rule:

$D(f \times g) = R(f) \times D(g) + D(f) \times g$

where $R$ is the right-shift operator defined as:

$R = ( \text{function $f$ on $\zz$} \mapsto ( \text{int $n$} \mapsto f(n+1) ) )$

Namely for any function $f$ on $\zz$ and $n \in Z$, $R(f)(n) = f(n+1)$.

For convenience we also define the summation operator:

$S = ( \text{function $f$ on $\zz$} \mapsto ( \text{int $n$} \mapsto \sum_{k=0}^{n-1} f(k) ) )$

Then we have the important property that $DS(f) = f$ for any function $f$ on $\zz$, analogous to the fundamental theorem of calculus.

Now by substituting $f$ with $S(f)$ into the product rule and taking summation on both sides we get summation by parts:

$S( f \times g ) = S(f) \times g - S( R(S(f)) \times D(g) ) + c$ for some constant function $c$ on $\zz$.

Example indefinite sum

Using this we can easily compute things like $\sum_{k=1}^n k^3 3^k$ by applying it three times, each time reducing the degree of the polynomial part. There are other ways to achieve this using differentiation, but this method is purely discrete.

$\endgroup$
  • $\begingroup$ I'm aware of corresponding approaches, but didn't see this notation. Any helpful reference? (+1) $\endgroup$ – Markus Scheuer Jul 8 '15 at 14:32
  • 1
    $\begingroup$ @MarkusScheuer: Unfortunately I do not know of a comprehensive reference, because I developed all this on my own. I found that they are called Newton series and Summation by Parts on Wikipedia. The notation I used to define the operators comes from computer science where functions are first-class objects. If you learn Javascript it would be similar. $\endgroup$ – user21820 Jul 8 '15 at 15:45
  • 2
    $\begingroup$ @MarkusScheuer : The above material, and a bit more, is section 2.6 in [en.wikipedia.org/wiki/Concrete_Mathematics] Graham, Knuth, Patashnik, "Concrete Mathematics, 2nd ed.". A more "theoretical" treatment is section 2.1 (and its exercises) in [en.wikipedia.org/wiki/Special:BookSources/978-0-387-23059-7] Elaydi, "An Introduction to Difference Equations, 3rd. ed.". $\endgroup$ – Eric Towers Jul 8 '15 at 21:13
  • $\begingroup$ @EricTowers: Thanks a lot for the refs! I'm familiar with Knuth's book, but not with the second reference. It looks interesting! $\endgroup$ – Markus Scheuer Jul 8 '15 at 21:56
  • $\begingroup$ @EricTowers: Thanks for the references! $\endgroup$ – user21820 Jul 9 '15 at 13:55
4
$\begingroup$

You can find the formulas here (they get progressively messier), however for Calculus 2 you won't need anything past what you've already got.

$\endgroup$
  • $\begingroup$ thanks alot for your input ill look at your link thats all i need for calculus 2 got it, thanks :) $\endgroup$ – JRowan Jul 8 '15 at 0:37
4
$\begingroup$

The way I like to do this is to consider that we're looking for a polynomial $P(x)$ of degree $n+1$ satisfying: $$P(x)=x^n+P(x-1).$$ $$P(0)=0$$ Notice that when we expand, we get: $$P(x)=x^n+P(x-1)=x^n + (x-1)^n + P(x-2) = \ldots = x^n + (x-1)^n + \ldots + 2^n + 1^n + 0$$ which is what we desire. It's not too hard to show that such a polynomial always exists*, but once we know it does, this gives a way to find it. So, for $n=1$ we want a polynomial of degree $2$ - so $P(x)=ax^2+bx$ (noting that the constant term is obviously $0$) - satisfying $$[ax^2 + bx] = x + [a(x-1)^2 + b(x-1)]$$ which expands as: $$ax^2 + bx = ax^2 + (1+b-2a)x + (a-b)$$ and noting that the coefficient of $x$ and the constant term must be equal on both sides, we get: $$b=1+b-2a$$ $$0=a-b$$ yielding $a=b=\frac{1}2$ so $$P(x)=\frac{1}2\left(x^2+x\right)$$ is the polynomial giving the sum of $1+2+3+\ldots + x$. We can repeat this procedure for all degrees of polynomials - and may indeed replace the $x^n$ term by any polynomial of degree $n$ (which is often helpful). It takes some work to do things this way, but it always works without too much cleverness.

(*My way to do this would be to consider the linear map on polynomials of degree at most $n+1$ taking $P$ to a pair $(Q,c)$ where $Q(x)=P(x)-P(x-1)$ and $c=P(0)$. It turns out that this is map is invertible. Notice that for $Q$ to be zero, $P$ must be constant - and for $c$ to be zero too, $P$ must be the zero polynomial, meaning that the kernel of the map is trivial. Additionally, the degree of $Q$ is at most $n$, so the space of pairs $(Q,c)$ is $n+1$ dimensional too, so we may conclude that any system of equations of similar form to the one presented has a unique solution - which by the same methods as used in the post, can be shown to mean that summing over a polynomial yields another polynomial, of degree one higher)

$\endgroup$
1
$\begingroup$

An other way, not mention there I do the example for power two but you can do the same for all. You just need to know the summation of all powers before.


$$\int_{k}^{k+1} x^2 \mathrm{d}x=k^2+k+\frac{1}{3}$$

Then using summation we have

$$\frac{(n+1)^3}{3}=\int_0^{n+1} x^2 \mathrm{d}x=\sum_{k=0}^n\left(k^2+k+\frac{1}{3}\right) $$

Then use factorisation to find $$\sum_{k=0}^nk^2=\frac{n(n+1)(2n+1)}{6}$$

$\endgroup$
1
$\begingroup$

For any polynomial of $p$th powers $S_p(n) = \sum_{k=1}^n k^p$ $(p \in \Bbb N)$ there is a formula of higher degree $S_p(n)=\sum_{k=1}^{p+1} a_kn^k$

The question is how to find the unknown $a_k$ coefficients which are real numbers. So use the following formulas to find them:

$a_k= \frac{1}{k!} \cdot \sum_{j=1}^{p+1-k} (-1)^{j+1} \frac {a_{k+j} \cdot (k+j)!}{(j+1)!}$ for $(0 \lt k \lt p+1)$

$a_k=\frac {1}{p+1}$ for $(k=p+1)$

Example:

$S_3(n) = \sum_{k=1}^n k^3$

Solution:

$p=3$

$S_3(n)=\sum_{k=1}^{4} a_kn^3 = a_1n+a_2n^2+a_3n^3+a_4n^4$

Now using the above two formulas to find the unknown coefficients $a_1,a_2,a_3,a_4$

$a_4 = \frac{1}{3+1}=\frac{1}{4}$

$a_3=\frac {1}{3!} \cdot \sum_{j=1}^{1} (-1)^{j+1} \frac {a_{3+j} \cdot (3+j)!}{(j+1)!} =\frac {1}{3!} \cdot \frac {a_4 \cdot 4!}{2!} = \frac {\frac{1}{4} \cdot 4!}{3! \cdot 2!}=\frac {1}{2}$

$a_2=\frac {1}{2!} \cdot \sum_{j=1}^{2} (-1)^{j+1} \frac {a_{2+j} \cdot (2+j)!}{(j+1)!} = \frac {1}{2!} \cdot (\frac {a_3 \cdot 3!}{2!} - \frac {a_4 \cdot 4!}{3!}) = \frac {1}{2} \cdot (3a_3-4a_4)= \frac {1}{2} \cdot (3 \cdot \frac {1}{2}-4 \cdot \frac {1}{4})= \frac {1}{4}$

$a_1=\frac {1}{1!} \cdot \sum_{j=1}^{3} (-1)^{j+1} \frac {a_{1+j} \cdot (1+j)!}{(j+1)!} = \sum_{j=1}^{3} (-1)^{j+1} a_{1+j}=a_2-a_3+a_4 =\frac {1}{4}-\frac {1}{2}+\frac {1}{4}=0$

Finally

$S_3(n)=0*n+\frac {1}{4}*n^2+\frac {1}{2}*n^3+\frac {1}{4}*n^4 =\frac {n^2+2n^3+n^4}{4}=\left[ \frac{n(n+1)}{2}\right]^2.$

$\endgroup$
1
$\begingroup$

The sum of the $k$-th powers of numbers $1$ to $n$ can also be derived by means of formal power series. \begin{align*} S_k(n):=\sum_{j=1}^n j^k\qquad\qquad n,k\geq 1 \end{align*} In order to do so we encode for fixed $k$ the sequence $\left(S_k(n)\right)_{n\geq 0}$ by generating functions $$A(z)=\sum_{n=0}^\infty S_k(n)z^n$$

It's convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. We also use $D_z:=\frac{d}{dz}$ to denote the differential operator. The following is valid:

The sum of the $k$-th powers of numbers $1$ to $n$ is given by \begin{align*} S_k(n)=\sum_{j=1}^nj^k=[z^n]\frac{1}{1-z}(zD_z)^k\frac{1}{1-z}\tag{1} \end{align*}

A detailed derivation of (1) together with some examples can be found in this answer.

Here is an example with $k=4$

Example $S_4(n)$

\begin{align*} S_4(n)=\sum_{j=0}^n j^4&=[z^n]\frac{1}{1-z}(zD_z)^4\frac{1}{1-z}\tag{2}\\ &=[z^n]\frac{z(1+11z+11z^2+z^3)}{(1-z)^6}\\ &=[z^n](z+11z^2+11z^3+z^4)\sum_{j=0}^{\infty}\binom{-6}{j}(-z)^{j}\tag{3}\\ &=\left([z^{n-1}]+11[z^{n-2}]+11[z^{n-3}]+[z^{n-4}]\right)\sum_{j=0}^{\infty}\binom{j+5}{5}z^j\tag{4}\\ &=\binom{n+4}{5}+11\binom{n+3}{5}+11\binom{n+2}{5}+\binom{n+1}{5}\\ &=\frac{1}{30}n(6n^4+15n^3+10n^2-1) \end{align*}

Comment:

  • In (2) we apply the operator $\frac{1}{1-z}(zD_z)^4$ to $\frac{1}{1-z}$

  • In (3) we use the binomial series expansion

  • In (4) we use the linearity of the coefficient of operator, apply the formula \begin{align*} [z^{p-q}]A(z)=[z^p]z^qA(z) \end{align*} and use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

  • In (5) we select the coefficients of $z^{n-1}$ to $z^{n-4}$.
$\endgroup$
0
$\begingroup$

If you accept that the summation of $p$th powers $\sum_{j=1}^n j^p$ ($p \in {\mathbb N}$) is a polynomial in $n$ of degree $p+1$, then similar to another answer, there is a very easy way to remember how to get the coefficients for the polynomial, especially if you use a computer program like MATLAB, if you are familiar with a little linear algebra (basically, just matrix and vector operations). If your answer polynomial is $\sum_{k=0}^{p+1} c_k n^k$, then you can just plug in $n=0,1,2,\ldots,p+1$ into the original summation formula, and for each value you plug in you will get an equation for a linear combination of the $c_k$. It turns out these linear equations are linearly independent, and in matrix notation what you get is a linear system $Ac = b$ where $c$ is the vector of $p+2$ coefficients $c_k$ you are solving for, and $A$ is the matrix of coefficients you get for your linear equations when plugging in $n$ in between $0$ and $p+1$, and $b$ is the vector of $p+2$ summation values you get when you plug in $n$ between $0$ and $p+1$. Here $Ac$ is standard matrix-vector multiplication. Then provided you know matrix operations, the solution is $c = A^{-1}b$ where $A^{-1}$ is the inverse matrix of $A$ (easy to compute especially with a matrix-friendly computing tool like MATLAB).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.