Finite summation 
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}$
 A: 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}$.  
A: 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. 
A: 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.
