# Homework Help: Sum of Consecutive Powers

1. Jun 14, 2015

### Keen94

1. The problem statement, all variables and given/known data
Use the method of Problem 6 to show that ∑1≤k≤n kp can always be written in the form
(np+1) / (p+1) +Anp+Bnp-1+Cnp-2+...
Source: Calculus by Michael Spivak. Chapter 2 problem 7.

2. Relevant 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)3 - k3=3k2+3k+1
Writing this formula for k=1,..,n and summing all n equations we arrive at
(n+1)3 -1=3(sum of consecutive squares)+3(sum of consecutive positive integers)+n
or
(n+1)3 -1=3(12+22+...+n2)+3(1+2+...+n)+n

3. 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.
rk=1 kp+1= (rp+2) / (P+2) +rp+1 -1/(P+2)[∑0≤j≤p1≤k≤r-1(p+2 C j)(kj) +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.

#### Attached Files:

File size:
160.4 KB
Views:
47
File size:
179.5 KB
Views:
43
File size:
245.9 KB
Views:
40
• ###### Page4.pdf
File size:
192.6 KB
Views:
35
2. Jun 14, 2015

### 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$ .

3. Jun 14, 2015

### Keen94

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?

4. Jun 14, 2015

### 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.

5. Jun 14, 2015

### Keen94

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

6. Jun 14, 2015

### 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$ ."

Last edited: Jun 14, 2015
7. Jun 14, 2015

### Keen94

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.

8. Jun 14, 2015

### 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.

Last edited: Jun 14, 2015
9. Jun 14, 2015

### vela

Staff Emeritus
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.

10. Jun 20, 2015

### Keen94

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

11. Jun 21, 2015

### 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?

Last edited: Jun 21, 2015
12. Jun 21, 2015

### Keen94

Bump

13. Jun 22, 2015

### vela

Staff Emeritus
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?

14. Jun 22, 2015

### Keen94

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}$

15. Jun 23, 2015

### vela

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

16. Jun 23, 2015

### Keen94

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}+...$

17. Jun 23, 2015

### vela

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

18. Jun 23, 2015

### 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.

19. Jun 24, 2015

### 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}+...$

20. Jun 25, 2015

### Keen94

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

21. Jun 26, 2015

### vela

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

22. Jun 26, 2015

### Keen94

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

23. Jun 29, 2015

### 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}+...$

Last edited: Jun 29, 2015
24. Jul 2, 2015

### Keen94

I edited the post to clear up a few steps.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted