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:
38
File size:
179.5 KB
Views:
33
File size:
245.9 KB
Views:
32
• Page4.pdf
File size:
192.6 KB
Views:
30
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?