Sum of Consecutive Powers

[Keen94]

Homework Statement

Use the method of Problem 6 to show that ∑^1≤k≤n k^p can always be written in the form
(n^p+1) / (p+1) +An^p+Bn^p-1+Cn^p-2+...
Source: Calculus by Michael Spivak. Chapter 2 problem 7.

Homework Equations

The method from problem 6 is described as follows:
The formula for the sum of consecutive squares may be derived as follows. We begin with the formula
(k+1)³ - k³=3k²+3k+1
Writing this formula for k=1,..,n and summing all n equations we arrive at
(n+1)³ -1=3(sum of consecutive squares)+3(sum of consecutive positive integers)+n
or
(n+1)³ -1=3(1²+2²+...+n²)+3(1+2+...+n)+n

The Attempt at a Solution

I have included (uploaded) all of my work. It's too much to write here and every step is not super relevant.
In short I thought that the only way to go about this was to do an inductive proof. After a lot of algebra I have arrived at the following equation found at the end of Page4.
∑^r_k=1 k^p+1= (r^p+2) / (P+2) +r^p+1 -1/(P+2)[∑_0≤j≤p∑^1≤k≤r-1(p+2 C j)(k^j) +1]
Which almost what I need. That last term is the collection of all r with exponents ≤p but I can't figure out how to expand it so I have coefficients that I can relabel as A, B, C, etc. Thanks for the help.

 

[wabbit]

You're making this more complicated than it needs to be. Define $S_p(n)=\sum_{k=1}^n k^p$. Expand $(m+1)^{p+1}-m^{p+1}$ using the binomial formula, then sum these from $m=0$ to $m=n$ , and express the resulting RHS in terms of the $S_q(n),q<p$ .

 

[Keen94]

You're making this more complicated than it needs to be. Define $S_p(n)=\sum_{k=1}^n k^p$. Expand $(m+1)^{p+1}-m^{p+1}$ using the binomial formula, then sum these from $m=0$ to $m=n$ , and express the resulting RHS in terms of the $S_q(n),q<p$ .

I believe I've done as you suggested on Page3. The RHS can be rearranged so that it is a series of sums of K's of increasing or decreasing powers (however you'd like to rearrange them). When you say to express the RHS in terms of the $S_q(n),q<p$. Are you hinting at I should just relabel theses sums as $S_q(n),q<p$ and $S_(q-1)(n),q<p$ and so on?

 

[wabbit]

Yes, it doesn't change anything of course except it makes the inductive argument more apparent. Note that you you know by assumption that $S_q$ is a polynomial, and you know its degree too.

I only had a quick look at the attachments, the calculations you do are probably correct but far more complicated that needed, my suggestion is that you restart from scratch and also write it down here in latex as this is far easier to read - it should be a matter of just a few lines.

 

[Keen94]

Yes, it doesn't change anything of course except it makes the inductive argument more apparent. Note that you you know by assumption that $S_q$ is a polynomial, and you know its degree too.

I only had a quick look at the attachments, the calculations you do are probably correct but far more complicated that needed, my suggestion is that you restart from scratch and also write it down here in latex as this is far easier to read - it should be a matter of just a few lines.

I think I see it now. Just as (1+K)^p+1-k^p+1=∑k^p then all the other sigmas can be replaced by a polynomial of the form (1+K)ⁿ-kⁿ. Is that were you were going with this?

 

[wabbit]

I'm not sure I get what you mean, but it is not true that $(1+k)^{p+1}-k^{p+1}=\sum k^p$ - you dropped some coefficients here.

What I meant is you can obtain an expression of $S_p$ involving lower-power $S_q$.
What you are trying to prove by induction on $p$ is " $S_p(n)= \frac{n^{p+1}}{p+1}$ plus a polynomial of degree at most $p$ ."

 

[Keen94]

I'm not sure I get what you mean, but it is not true that $(1+k)^{p+1}-k^{p+1}=\sum k^p$ - you dropped some coefficients here.

What I meant is you can obtain an expression of $S_p$ involving lower-power $S_q$.
What you are trying to prove by induction on $p$ is " $S_p(n)= \frac{n^{p+1}}{p+1}$ plus a polynomial of degree at most $p$ ."

You're right. Big mistake on my part. What I meant was, am I trying to rewrite my sums so that it fits the definition of the binomial theorem? Therefore I could replace my binomial theorem sums with a polynomial.

 

[wabbit]

Again I'm not quite sure what you mean - but the idea is just to do the same thing as in the $p=3$ case you described, where you show that $S_3$ can be expressed as leading term plus some combination of $S_2,S_1,S_0$.

I don't know how to explain it better without writing down the solution.

 

[vela]

(n+1)³ -1=3(sum of consecutive squares)+3(sum of consecutive positive integers)+n
or
(n+1)³ -1=3(1²+2²+...+n²)+3(1+2+...+n)+n

In this particular case, what you have here is
$$(n+1)^3-1 = 3 S_2(n) + 3 S_1(n) + S_0(n).$$ If you solve for $S_2(n)$, you get
\begin{align*}
S_2(n) &= \frac{(n+1)^3-1}{3} - S_1(n) - \frac 13 S_0(n) \\
&= \frac{n^3+3n^2+3n+1-1}{3} - S_1(n) - \frac 13 S_0(n) \\
&= \frac{n^3}{3} + n^2 + n - S_1(n) - \frac 13 S_0(n)
\end{align*} If you were to substitute in expressions for $S_1(n)$ and $S_0(n)$ and simplify, everything after $\frac{n^3}{3}$ will combine to form a quadratic polynomial. You should, however, be able to reason out this is the case without having to explicitly substitute in for $S_1(n)$ and $S_0(n)$.

What you're being asked to do is do the same analysis for the general case.

 

[Keen94]

In this particular case, what you have here is
$$(n+1)^3-1 = 3 S_2(n) + 3 S_1(n) + S_0(n).$$ If you solve for $S_2(n)$, you get
\begin{align*}
S_2(n) &= \frac{(n+1)^3-1}{3} - S_1(n) - \frac 13 S_0(n) \\
&= \frac{n^3+3n^2+3n+1-1}{3} - S_1(n) - \frac 13 S_0(n) \\
&= \frac{n^3}{3} + n^2 + n - S_1(n) - \frac 13 S_0(n)
\end{align*} If you were to substitute in expressions for $S_1(n)$ and $S_0(n)$ and simplify, everything after $\frac{n^3}{3}$ will combine to form a quadratic polynomial. You should, however, be able to reason out this is the case without having to explicitly substitute in for $S_1(n)$ and $S_0(n)$.

What you're being asked to do is do the same analysis for the general case.

In other words I just have to get that crucial first term (n^p+1) / (p+1) and simply reason out that the remaining terms are n's with decreasing power.

 

[Keen94]

Let P(p) be the statement $\sum_{k=1}^n k^p = \frac{n^{p+1}}{p+1}$ + polynomial of degree at most p

Suppose P(1) is true, we have
$\sum_{k=1}^n k^1=\frac{n^2}{2}+\frac{n}{2}$
Suppose ∀_n∈ℤ⁺, if P(1),...,P(p-1),P(p) are all true, then P(p+1) is true.
So we have,
$\sum_{k=1}^n k^1=\frac{n^2}{2}+\frac{n}{2}$
.
.
.
$\sum_{k=1}^n k^{p-1} = \frac{n^{p}}{p}$ + polynomial of degree at most p-1
$\sum_{k=1}^n k^p = \frac{n^{p+1}}{p+1}$ + polynomial of degree at most p
Then P(p+1) Since $k^{p+1}$ is a polynomial we can use the method from problem 6 to derive the sum formula of $\sum_{k=1}^n k^{p+1}$
By the Binomial Theorem we have
$(1+k)^{p+2}-k^{p+2}=\sum_{n=0}^{p+2} \binom{p+2} {n}\ k^n -k^{p+2}$
$(1+k)^{p+2}-k^{p+2}=\sum_{n=0}^{p+1} \binom{p+2} {n}\ k^n$
Let k=1,...,r then sum of the list of r equations we have,
$(1+r)^{p+2}-1=\sum_{n=0}^{p+1} \binom{p+2} {n}\ 1^n+\sum_{n=0}^{p+1} \binom{p+2} {n}\ 2^n+...+\sum_{n=0}^{p+1} \binom{p+2} {n}\ r^n$
After algebraic manipulations,
$(1+r)^{p+2}-1=\binom{p+2} {0}\ \sum_{k=0}^r k^0+...+\binom{p+2} {p}\ \sum_{k=0}^{r} k^{p}+\binom{p+2} {p+1}\ \sum_{k=0}^rk^{p+1}$
Does it suffice to simply subtract the required sums to one side and simply reason that the expansion of these sums is a polynomial of degree at most p?

 

[Keen94]

Bump

 

[vela]

After algebraic manipulations,
$$(1+r)^{p+2}-1=\binom{p+2} {0}\ \sum_{k=0}^r k^0+...+\binom{p+2} {p}\ \sum_{k=0}^{r} k^{p}+\binom{p+2} {p+1}\ \sum_{k=0}^rk^{p+1}$$
Does it suffice to simply subtract the required sums to one side and simply reason that the expansion of these sums is a polynomial of degree at most p?

Yes, but you should explain your logic. So you have
\begin{align*}
\binom{p+2} {p+1} \sum_{k=0}^r k^{p+1} &= (1+r)^{p+2}-1 - \left[\binom{p+2} {0} \sum_{k=0}^r k^0+ \cdots +\binom{p+2} {p} \sum_{k=0}^{r} k^{p}\right] \\
&= (1+r)^{p+2}-1 - \left[\binom{p+2} {0} S_0(r) + \cdots + \binom{p+2} {p} S_p(r) \right]
\end{align*} Now what?

 

[Keen94]

Yes, but you should explain your logic. So you have
\begin{align*}
\binom{p+2} {p+1} \sum_{k=0}^r k^{p+1} &= (1+r)^{p+2}-1 - \left[\binom{p+2} {0} \sum_{k=0}^r k^0+ \cdots +\binom{p+2} {p} \sum_{k=0}^{r} k^{p}\right] \\
&= (1+r)^{p+2}-1 - \left[\binom{p+2} {0} S_0(r) + \cdots + \binom{p+2} {p} S_p(r) \right]
\end{align*} Now what?

I suppose it follows that
$(p+2)\sum_{k=0}^r k^{p+1} = (1+r)^{p+2}-1-\left[\sum_{k=0}^r k^0 +(p+2)\sum_{k=0}^{r} k^{1}+...+\frac{(p+2)(p+1)}{2}\ \sum_{k=0}^{r} k^{p}\right]$

Then
$\sum_{k=0}^r k^{p+1} = \frac{(1+r)^{p+2}}{p+2}-\frac{1}{p+2}-\frac{1}{p+2}\ \left[\sum_{k=0}^r k^0 + (p+2)\sum_{k=0}^{r} k^{1}+...+\frac{(p+2)(p+1)}{2}\ \sum_{k=0}^{r} k^{p}\right]$

$\sum_{k=0}^r k^{p+1} = \frac{(1+r)^{p+2}}{p+2}-\frac{1}{p+2}\ \left[\sum_{k=0}^r k^0 + (p+2)\sum_{k=0}^{r} k^{1}+...+\frac{(p+2)(p+1)}{2}\ \sum_{k=0}^{r} k^{p}\right]-\frac{r^0}{p+2}$

If we substitute the sums with the corresponding polynomials since we assumed that P(1),...,P(n) are true then we have
$\sum_{k=0}^r k^{p+1} = \frac{(1+r)^{p+2}}{p+2}+$ a Polynomial of Degree at most (p+1) which can be expressed as
$\sum_{k=0}^r k^{p+1} = \frac{(1+r)^{p+2}}{p+2}+Ar^{p+1}+Br^{p}+...+Zr^{0}$

 

[vela]

Go back and reread what you were asked to prove. You didn't quite show that yet.

 

[Keen94]

Go back and reread what you were asked to prove. You didn't quite show that yet.

Since P(k+1) is true whenever P(1),...,P(k) are true then P(k) is true therefore
$\sum_{k=0}^r k^{p} = \frac{(1+r)^{p+1}}{p+1}+Ar^{p}+Br^{p-1}+Cr^{p-2}+...$

 

[vela]

That isn't quite what you were asked to show.

 

[Keen94]

How hot or cold am I? I'm guessing that the last step is to adjust the index of the the sum on the LHS by subtracting the first term of the sum from both sides.

 

[Keen94]

After adjusting the index of the sum and sending the first term of the sum to the LHS we are left with
$\sum_{k=1}^r k^{p} = \frac{(1+r)^{p+1}}{p+1}+Ar^{p}+Br^{p-1}+Cr^{p-2}+...$

 

[Keen94]

Would I do the adjusting to the the P(p+1) sum, so that then the P(p) sum is proved?

 

[vela]

Homework Statement

Use the method of Problem 6 to show that ∑^1≤k≤n k^p can always be written in the form
(n^p+1) / (p+1) +An^p+Bn^p-1+Cn^p-2+...
Source: Calculus by Michael Spivak. Chapter 2 problem 7.

After adjusting the index of the sum and sending the first term of the sum to the LHS we are left with
$\sum_{k=1}^r k^{p} = \frac{(1+r)^{p+1}}{p+1}+Ar^{p}+Br^{p-1}+Cr^{p-2}+...$

There's an obvious difference between what you were asked to show and what you've ended up with (besides using $r$ vs. $n$).

 

[Keen94]

If you hadn't pointed it out, I would have never noticed. I'll get to it.

 

[Keen94]

Let P(p) be the statement $\sum_{k=1}^{n} k^p= \frac{n^{p+1}}{p+1}\ +An^{p}+Bn^{p-1}+Cn^{p-2}+...$
Observe that if p=1, the statement $\sum_{k=1}^{n} k^1= \frac{n^2}{2}\ +\frac{n}{2}$ , is true.
Suppose ∀_n∈ℤ⁺, if P(1),...,P(p-1),P(p) are true, then P(p+1).
Observe that if p=1,...,p the statements are ture.
$\sum_{k=1}^{n} k=\frac{n^2}{2}\ + \frac{n}{2}$
.
.
.
$\sum_{k=1}^{n} k^{p-1}=\frac{n^p}{p}\ + An^{p-1} + Bn^{p-2} +Cn^{p-3}+...$
$\sum_{k=1}^{n} k^p= \frac{n^{p+1}}{p+1}\ +An^{p}+Bn^{p-1}+Cn^{p-2}+...$
We must show that $\sum_{k=1}^{n} k^{p+1}=\frac{n^p+2}{p+2}\ + An^{p+1} + Bn^{p} +Cn^{p-1}+...$
By the Binomial Theorem and the method from problem 6 we have.
$(1+k)^{p+2}-k^{p+2}=\sum_{j=0}^{p+2} \binom {p+2}{j}\ k^j -k^{p+2}=\sum_{j=0}^{p+1} \binom {p+2}{j}\ k^j$
Let k=1,...,n then sum the list of n equations we have,
k=1→$2^{p+2}-1=\sum_{j=0}^{p+1} \binom {p+2}{j}\$
k=2→$3^{p+2}-2^{p+2}=\sum_{j=0}^{p+1} \binom {p+2}{j}\ 2^j$
.
.
.
k=n→$(1+n)^{p+2}-n^{p+2}=\sum_{j=0}^{p+1} \binom {p+2}{j}\ n^j$

The sum is
$(1+n)^{p+2}-1=\sum_{j=0}^{p+1} \binom {p+2}{j}\ +\sum_{j=0}^{p+1} \binom {p+2}{j}\ 2^j +...+\sum_{j=0}^{p+1} \binom {p+2}{j}\ n^j$

Which is equivalent to
$(1+n)^{p+2}-1=\binom {p+2}{0}\ \sum_{k=1}^{n} k^0+...+\binom {p+2}{p}\ \sum_{k=1}^{n} k^p + \binom {p+2}{p+1}\ \sum_{k=1}^{n} k^{p+1}$

The LHS can be rearranged so that
$\sum_{j=1}^{p+2} \binom {p+2}{j}\ n^j=\binom {p+2}{0}\ \sum_{k=1}^{n} k^0+...+\binom {p+2}{p}\ \sum_{k=1}^{n} k^p + \binom {p+2}{p+1}\ \sum_{k=1}^{n} k^{p+1}$

$\binom {p+2}{1}\ n +...+\binom {p+2}{p+1}\ n^{p+1}+\binom {p+2}{p+2}\ n^{p+2}=\binom {p+2}{0}\ \sum_{k=1}^{n} k^0+...+\binom {p+2}{p}\ \sum_{k=1}^{n} k^p + \binom {p+2}{p+1}\ \sum_{k=1}^{n} k^{p+1}$

$\binom {p+2}{p+1}\ \sum_{k=1}^{n} k^{p+1}=\binom {p+2}{p+2}\ n^{p+2} +\binom {p+2}{p+1}\ n^{p+1}+\binom {p+1}{p} [n^p-\sum_{k=1}^n k^{p+1}]+...+\binom {p+2}{1}\ [n-\sum_{k=1}^n k]-\binom {p+2}{0}\ \sum_{k=1}^n k^0$

By Assumption, that P(1),...,P(p) are true we have
$(p+2) \sum_{k=1}^{n} k^{p+1}= n^{p+2} +(p+2)n^{p+1}$+ Polynomial of degree at most p.

$\sum_{k=1}^{n} k^{p+1}= \frac{n^{p+2}}{p+2}\ +n^{p+1}$+ Polynomial of degree at most p.

Hence $\sum_{k=1}^{n} k^{p+1}= \frac{n^{p+2}}{p+2}\ +An^{p+1}+Bn^{p}+Cn^{p-1}+...$
Since P(p+1) is true whenever P(1),...,P(p) are true it follows that
$\sum_{k=1}^{n} k^p= \frac{n^{p+1}}{p+1}\ +An^{p}+Bn^{p-1}+Cn^{p-2}+...$

 

[Keen94]

The LHS can be rearranged so that
$\sum_{j=1}^{p+2} \binom {p+2}{j}\ n^j=\binom {p+2}{0}\ \sum_{k=1}^{n} k^0+...+\binom {p+2}{p}\ \sum_{k=1}^{n} k^p + \binom {p+2}{p+1}\ \sum_{k=1}^{n} k^{p+1}$
Expanding the LHS we have
$\binom {p+2}{1}\ n +...+\binom {p+2}{p+1}\ n^{p+1}+\binom {p+2}{p+2}\ n^{p+2}=\binom {p+2}{0}\ \sum_{k=1}^{n} k^0+...+\binom {p+2}{p}\ \sum_{k=1}^{n} k^p + \binom {p+2}{p+1}\ \sum_{k=1}^{n} k^{p+1}$
Isolating the desired term we have
$\binom {p+2}{p+1}\ \sum_{k=1}^{n} k^{p+1}=\binom {p+2}{p+2}\ n^{p+2} +\binom {p+2}{p+1}\ n^{p+1}+\binom {p+1}{p} [n^p-\sum_{k=1}^n k^{p+1}]+...+\binom {p+2}{1}\ [n-\sum_{k=1}^n k]-\binom {p+2}{0}\ \sum_{k=1}^n k^0$

By Assumption, that P(1),...,P(p) are true we have
$(p+2) \sum_{k=1}^{n} k^{p+1}= n^{p+2} +(p+2)n^{p+1}$+ Polynomial of degree at most p.

$\sum_{k=1}^{n} k^{p+1}= \frac{n^{p+2}}{p+2}\ +n^{p+1}$+ Polynomial of degree at most p.

Hence $\sum_{k=1}^{n} k^{p+1}= \frac{n^{p+2}}{p+2}\ +An^{p+1}+Bn^{p}+Cn^{p-1}+...$
Since P(p+1) is true whenever P(1),...,P(p) are true it follows that
$\sum_{k=1}^{n} k^p= \frac{n^{p+1}}{p+1}\ +An^{p}+Bn^{p-1}+Cn^{p-2}+...$

I edited the post to clear up a few steps.