Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am having trouble completing exercise 17 of chapter 2 of Spivak's Calculus. In this exercise, the reader is asked to prove that for all natural numbers $n$ and $p$, there exist real numbers $\alpha_1,\ldots,\alpha_p$ such that: $$ \sum_{k = 1}^n k^p ~=~ \frac{n^{p + 1}}{p + 1} + \sum_{i = 1}^p \alpha_in^i$$ The attempted proof of the identity that I devised uses the binomial theorem with $p$ and $n$ fixed, but does not use complete induction. The proof of the identity provided by Spivak uses the binomial theorem with $n$ fixed, but uses complete induction on $p$ to complete the proof. What follows is my attempted proof.

In this proof, I apply $(x + 1)^{y + 1}$ and $(n + 1)^{p + 1}$ to the binomial theorem in order to derive the first and second terms of the sum on the left-hand side of the identity to be proved. First, note that applying $(x + 1)^{y + 1}$ to the binomial theorem, where $x$ is a real number and $y$ a natural number, demonstrates that the predicate $\phi(x,y)$ is true for all real numbers $x$ and natural numbers $y$: $$ \phi(x,y) ~\equiv~ (x + 1)^{y + 1} - x^{y + 1} ~=~ (y + 1)x^y + \sum_{i = 0}^{y - 1} {y + 1 \choose i} x^i$$ Now, suppose that $n$ and $p$ are natural numbers. Then the sum of the left-hand sides of the identities $\phi(k,p)$ and the sum of the right-hand sides of the identities $\phi(k,p)$, for $k = 1,\ldots,n$, are equal: $$(n + 1)^{p + 1} - 1 ~=~ \sum_{k = 1}^n (p + 1)k^p + \sum_{k = 1}^n \left ( \sum_{i = 0}^{p - 1} {p + 1 \choose i} k^i \right )$$ Rewriting $(n + 1)^{p + 1}$ using the identity $\phi(n,p)$ and dividing both sides of the identity by $p + 1$ gives $$ \sum_{i = 1}^n k^p ~=~ \frac{n^{p + 1}}{p + 1} + \sum_{i = 0}^p {p + 1 \choose i} \left ( \frac{1}{p + 1}\right ) n^i - \left [\frac{1}{p + 1} + \sum_{k = 1}^n \left ( \sum_{i = 0}^{p - 1} {p + 1 \choose i} \frac{k^i}{p + 1} \right ) \right ] $$ Assuming that I didn't make any algebraic errors, I have shown that there are $\alpha_1,\ldots,\alpha_p$ such that the sum of the $p$th powers of the first $n$ natural numbers can be written in the required way. On the other hand, Spivak derives an identity containing the sums of the $r$th powers of the first $n$ natural numbers, for $r \leq p$, then applies an induction hypothesis to obtain the case for $p + 1$. I'm not sure if my proof is wrong, and whether I am missing something that would require a proof by induction. Is there an error?

For reference: I wrote functions that compute the sum of the $p$h power of the first $n$ numbers, and a version of the last identity derived before expanding $(n + 1)^{p + 1}$ using $\phi(n,p)$ in Haskell. Both computed the same numbers for all values of $n \leq 100$ and $p \leq 10$, so for a few numbers there seems to be no problem. Of course, there are more numbers greater than the number of cases that I tested.

share|improve this question
    
You really should be using induction. He tells you to use it. –  Pedro Tamaroff Aug 18 '12 at 3:22
    
I tried using complete induction on $p$. However, I found that expanding $(n + 1)^{p + 1}$ using the binomial theorem generated the sum of the $\alpha_i n^i$ that I needed. It's not clear where I should use induction. –  danportin Aug 18 '12 at 3:24
    
I'll try to write something out for you. –  Pedro Tamaroff Aug 18 '12 at 3:25

1 Answer 1

up vote 6 down vote accepted

He tells you to use induction. In my copy, he just says:

Use the methods of problem $6$ to prove that $$\sum_{k=0}^n k^p$$ may be written in the form

$$\frac{n^{p+1}}{p+1}+An^{p}+Bn^{p-1}+Cn^p+\dots$$

The really important thing here is

$$\frac{n^{p+1}}{p+1}$$

and later on you'll find out why.

Basically, he hints on using the "recursive" trick to obtaining

$$S_{p+1}$$ from $S_p,\dots,S_1$

where $$S_p=\sum_{k=0}^n k^p$$

Say we want $$S_2=\sum_{k=0}^n k^2$$

Then we note that $$(k+1)^3=3k^2+3k+1$$

So that

$$(k+1)^3-k^3=3k^2+3k+1$$

Now we sum $k=1,\dots,n$.

$$\sum_{k=1}^n(k+1)^3-k^3=3\sum_{k=1}^nk^2+3\sum_{k=1}^nk+\sum_{k=1}^n1$$

$$(n+1)^3-1^3=3\sum_{k=1}^nk^2+3\frac{n(n+1)}{2}+n$$

$$\frac{{{{(n + 1)}^3}}}{3} - \frac{{n + 1}}{2} - \frac{{n(n + 1)}}{2} = \sum\limits_{k = 1}^n {{k^2}} $$

(Expansion aside).

So the idea is that you assume the result true for $p=1,\dots,l$ and prove it for $l+1$. Note you shouldn't be too explicit about the coefficients, and the induction is to be done on $p$, not on $n$.

share|improve this answer
    
Thank you for responding. I used this method in order to solve the problems in Exercise 6. I attempted to generalize the method to problem 17 by applying the binomial theorem to $(k + 1)^{n + 1}$ in order to obtain an expansion that the method of Exercise 6 requires. What is bothering me is the following: assuming that I didn't make any errors, why did I use the method of Exercise 6 in order to obtain a term of the required form without induction, but Spivak used the method of Exercise 6 to obtain a term of the required for with induction? This leads me to believe that I made an error. –  danportin Aug 19 '12 at 6:23
    
@danportin I'm guessing you didn't make an error, but just over complicated things. =) –  Pedro Tamaroff Aug 19 '12 at 17:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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