Summation Theorem how to get formula for exponent greater than 3 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?
 A: 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.
A: 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.
A: 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)
A: 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.
A: 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}$$
A: 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.$
A: 
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}$.

A: 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).
A: Although this is not quite within the traditional scope of pre-calculus material, it might be worthwhile to think about it from a different perspective. Below is the Faulhaber formula: $$\displaystyle \sum_{j=1}^{n}j^{k} = \sum_{i=1}^{k}S(k, i)\binom{n+1}{i+1}i!$$ where $S(k, i)$ is the Stirling number of the second kind, which counts the number of ways to partition a set of $k$ elements into $i$ disjoint, non-empty subsets.
Here's a combinatorial proof of the formula when $k < n:$
We will establish this identity by double-counting the number of $(k+1)$-tuples $(x_1, \ldots , x_{k+1})$ where $x_{1}, \ldots , x_{k+1} \in [n]= \{1,2, \ldots , n\}$ and $x_{k+1}> \max\{x_{i}: 1\leq i \leq k\}.$ The proof uses only elementary combinatorics.
LHS: divide into cases on the basis of the value of last variable 
A natural way to count these $(k+1)-$tuples would be to set $x_{k+1}= j+1$ for $1\leq j \leq n$, which leaves $j$ choices for each of $x_{1}, \ldots x_{k}$ and hence $j^{k}$ such tuples with $x_{k+1}$ specified. Summing over the range of $j$ covers all possibles values of $x_{k+1}$ and hence we end up with the LHS of the above equation.
RHS: divide into cases on the basis of the range of the function x
On the other hand, think of the $x_{m}$ as the output of the function $x: [k+1] \to [n+1].$ Suppose there are $i+1$ distinct values in $[n+1]$ taken by the function $x$, where $1\leq i \leq k.$ This can be fixed in $\binom{n+1}{i+1}$ ways. In this scheme, the actual value of $x_{k+1}$ is irrelevant, all that we want to fix is the fact that it is the largest value. This forces us to surjectively allocate the remaining $i$ values to $x_{1}, \ldots , x_{k}$ or in other words count the number of surjective functions from a set of $k$ distinguishable objects to a set of $i$ distinguishable objects, which is simply $S(k, i)i!.$ (This is because each function is uniquely defined by the pre-image of each of the $i$ values and the set of pre-images partitions the set $[k]$ into $i$ disjoint, non-empty subsets of which there are $S(k, i)$ many, by definition. Since there are $i!$ ways to order these partitions (because the $i$-set is distinguishable), we get $S(k, i)i!.$
Thus for a fixed value of $1\leq i \leq k$, there are $\displaystyle \binom{n+1}{i+1}S(k, i)i!$ $(k+1)-$tuples $(x_{1}, \ldots , x_{k+1})$ such that $x_{k+1}$ is the largest of $i+1$ values. Summing over the range of $i$, we cover all possible sizes of the range, thereby obtaining the RHS.
If you want to see special cases of this formula worked out for small values of $k$, take a look at the Enumerative Combinatorics chapter of Arthur Engel's Problem-Solving Strategies.
