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.

Possible Duplicate:
why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

What is the proof without induction for :

$(1)$ $\sum_{i=1}^n\ i^2= \frac{n(n+1)(2n+1)}{6}$

$(2)$ $\sum_{i=1}^n\ i^3=\frac{n^2(n+1)^2}{4}$

share|improve this question

marked as duplicate by J. M., Ross Millikan, Pedro Tamaroff, Jennifer Dylan, Asaf Karagila Aug 30 '12 at 23:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers 3

up vote 3 down vote accepted

One can give a proof that has a combinatorial flavour. We want to choose $3$ numbers from the numbers $0, 1,2,3,\dots, n$. This can be done in $\binom{n+1}{3}$ ways. We do the counting in another way.

Perhaps the smallest chosen number is $0$. Then the other two can be chosen in $\binom{n}{2}$ ways. Perhaps the smallest chosen number is $1$. Then the other two can be chosen in $\binom{n-1}{2}$ ways. Continue. Finally, the smallest of the chosen numbers could be $n-2$. Then the other two can be chosen in $\binom{2}{2}$ ways.

Reversing the order of summation we get $$\binom{2}{2}+\binom{3}{2}+\cdots+\binom{n}{2}=\binom{n+1}{3}.$$ Now use the fact that $\binom{k}{2}=\frac{k(k-1)}{2}$. We find that $$\frac{1}{2}\sum_{k=1}^n k^2-\frac{1}{2}\sum_{k=1}^n k =\frac{(n+1)(n)(n-1)}{3!}.$$ We know a closed form formula for $\sum_{k=1}^n k$, so from the above we can get a closed form for $\sum_{k=1}^n k^2$.

A similar idea works for $\sum k^3$. We use the combinatorial fact that $$\sum_{k=3}^n \binom{k}{3}=\binom{n+1}{4},$$ which is proved by a counting argument similar to the one we used for the closed form of $\sum_{k=2}^n \binom{k}{2}$.

Remarks: $1$. If I put my logic hat on, the answer to your question becomes entirely different. The result cannot be proved without induction. Indeed almost nothing about the natural numbers can be proved without using induction. In the Peano axioms, omit the induction axiom scheme. We end up with a system that is very very weak. Almost any argument that has a $\dots$, or a "and so on" in it involves induction. Indeed the very *definition of $\sum_{k=1}^n k^2$ requires induction.

$2$. The proof of $\sum_{k=2}^n \binom{k^2}=\binom{n+1}{3}$, and its generalizations, is very natural, and the resulting formula has a nice structure. The closed form expression for $\sum_{k=1}^n k^2$ is definitely less attractive. It turns out that one can give a slightly messy but purely combinatorial proof of the formula $$\sum_{k=1}^n 4k^2=\binom{2k+2}{3}.$$ so the somewhat "unnatural" $\frac{n(n+1)(2n+1)}{6}$ turns out to "come from" the more structured $\frac{1}{4}\cdot \frac{2n(2n+1)(2n+2)}{6}$.

share|improve this answer

There are probably many ways. For example, if you already know that $\sum_{i=1}^n i = \frac{n(n+1)}{2}$, it follows $$3\sum_{i=1}^n i^2 + 3\sum_{i=1}^n i + n = \sum_{i=1}^n (3i^2 + 3i + 1) = \sum_{i=1}^n ((i+1)^3 - i^3) = (n+1)^3 - 1$$ since the last sum telescopes, so $$\sum_{i=1}^n i^2 = \frac{1}{3}((n+1)^3 - 1 - 3\sum_{i=1}^n i - n) = \frac{1}{3}(n^3 + 3n^2 + 2n - \frac{3}{2}n(n+1))$$ $$=\frac{1}{6}(2n^3 + 3n^2 + n) = \frac{n(n+1)(2n+1)}{6}.$$

The second problem can be done in the same way.

share|improve this answer
    
Saying "the last sum telescopes" is using induction without saying so, isn't it? –  Gerry Myerson Aug 19 '12 at 5:41
    
@GerryMyerson True, that may be. –  Cocopuffs Aug 19 '12 at 5:47
    
@Gerry The statement to be proved is an equality for all natural numbers, so any proof would use induction in some form if we look deep enough. I think Cocopuffs answer is the type of proof the OP intended. –  Ragib Zaman Aug 19 '12 at 5:53
    
@Ragib, $n(n+1)=n^2+n$ is an equality for all natural numbers, proved by invoking the distributive law, with no need for induction however deep we look. You may be right about what OP wants, but only OP knows. –  Gerry Myerson Aug 19 '12 at 6:27

Let $S(n,t)=\sum_{1 ≤r ≤n} r^t$

We know, $(r+1)^2-r^2=2\cdot r+1$

Putting r=1,2,3,...,n-1,n we get,

$(1+1)^2-1^2=2\cdot1+1$

$(2+1)^2-2^2=2\cdot2+1$

...

$(n-1+1)^2-(n-1)^2=2\cdot (n-1)+1$

$(n+1)^2-n^2=2\cdot n+1$

Adding both sides, $(n+1)^2-1=2S(n,1)+n$

=>$S(n,1)=\frac{n(n+1)}{2}$

We know, $(r+1)^3-r^3=3\cdot r^2+3\cdot r+1$

Putting r=1,2,3,...,n-1,n and adding them we get,

$(n+1)^3-1=3S(n,2)+3S(n,1)+n$

But $S(n,1)=\frac{n(n+1)}{2}$

$=>3S(n,2)=n^3+3n^2+3n+1-1-n-3\frac{n(n+1)}{2}$

$=>6S(n,2)=2n^3+6n^2+6n-2n-3n(n+1)$

$=2n^3+3n^2+n=n(2n^2+3n+1)=n(n+1)(2n+1)$

$=>S(n,2)=\frac{n(n+1)(2n+1)}{6}$

Now we know, $(r+1)^4-r^4=4\cdot r^3+6\cdot r^2+4\cdot r+1$

Putting r=1,2,3,...,n-1,n and adding them we get,

$(n+1)^4-1=4S(n,3)+6S(n,2)+4S(n,1)+n$

Putting the values $S(n,1)$ and $S(n,2)$

$n^4+4n^3+6n^2+4n+1-1=4S(n,3)+(2n^3+3n^2+n)+2(n^2+n)+n$

$=>4S(n,3)=n^4+2n^3+n^2$

$=>S(n,3)=(\frac{n(n+1)}{2})^2$

We can go as far as we like.

share|improve this answer

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