Finite summation [duplicate]

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

marked as duplicate by J. M. is a poor mathematician, Ross Millikan, Pedro Tamaroff♦, user2468, Asaf Karagila♦Aug 30 '12 at 23:29

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

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.

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