# Thread: 1^2 + 2^2 + ... + n^2 = ?

1. ## 1^2 + 2^2 + ... + n^2 = ?

I need a simpler formula for that expression. Im supposed to prove by induction that the number of squares within an n x n checkerboard is that expression. I definately need a simpler formula, but any help towards the proof would be appreciated, thanks!

2. Originally Posted by Dubulus
I need a simpler formula for that expression. Im supposed to prove by induction that the number of squares within an n x n checkerboard is that expression. I definately need a simpler formula, but any help towards the proof would be appreciated, thanks!
Generally speaking, if you are adding terms, each of which is a polynomial degree N, then the sum is a polynomial of degree N+1. Here each term is of degree 2 so the sum is a polynomial of degree 3: $\displaystyle ax^3+ bx^2+ cx+ d$. When n= 1, the sum is 1 so a+ b+ c+ d= 1. When n= 2, the sum is 1+ 4= 5 so 8a+ 4b+ 2c+ d= 5. When n= 3, the sum is 1+ 4+ 9= 14 so 27a+ 9b+ c+ d= 14. Finally, when n= 4, the sum is 1+ 4+ 9+ 16= 30 so 64a+ 16b+ 4c+ d= 30. Solve those 4 equations for a, b, c, d.

3. If you just need the formula.

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

4. The formula for the sum of squares of first n natural numbers is given by:
1^2+2^2+3^2+..........+n^2 = n(n+1)(2n+1)/6, ................ eqn(1)

and as far as the proof is concerned, it can be proved by using the concept of mathematical induction as follows:-
Let n= 1, therefore L.H.S of the above expression becomes
1^2 = 1
and R.H.S becomes
1(1+1)(2x1+1)/6
=6/6
=1
Hence the result is true for n=1.

Let us suppose that the result is true for n=k,i.e.
1^2+2^2+3^2+..........+k^2 = k(k+1)(2k+1)/6

Let us prove the result for n=k+1.
If we put n = k+1 on the L.H.S of the eqn (1) then it becomes
1^2+2^2+3^2+..........+k^2+(k+1)^2
=k(k+1)(2k+1)/6 + (k+1)^2
=(k+1){k(2k+1)/6 +(k+1)}
=(k+1)[{k(2k+1)+6(k+1)}/6]
=(k+1)[{2(k)^2+k+6k+6}/6]
=(k+1){2(k)^2+7k+6}/6

Now let us put n=k+1 on the R.H.S of eqn (1),we have
(k+1)((k+1)+1)(2(k+1)+1)
=(k+1)(k+2)(2k+3)
=(k+1){2(k)^2+7k+6}/6

Hence L.H.S = R.H.S,
Hence the result is true for n=k+1 whenever it is true for n=k.
Thus it is true for all n.

For more details on other topics like probability check out my link
http://mysteriousmathematicssimplified.blogspot.com/

5. There is a beautiful proof not using induction but rather calculus. Try come up with it.

6. In general, you can easily estimate
$\displaystyle \sum_{i=0}^{n-1}i^{k},$
where $\displaystyle n,k\in\mathbb{N}$.
But before let me introduce some basic concepts on difference operator, factorial function and the Stirling numbers.
The forwards difference operator is defined to be $\displaystyle \Delta f(n)=f(n+1)-f(n)$.
And the factorial function for $\displaystyle n,k\in\mathbb{N}$ is defined as $\displaystyle n^{(k)}:=n(n-1)\cdots(n-k+1)$ (exactly $\displaystyle n$ numbers of successive terms are being factored), and for convenience $\displaystyle n^{(0)}:=1$.
It is not hard to see that
$\displaystyle \Delta n^{(k)}=kn^{(k-1)}$ and $\displaystyle \sum_{i=0}^{n-1}i^{(k-1)}=\sum_{i=0}^{n-1}\frac{1}{k}\Delta i^{(k)}=\frac{n^{(k)}}{k}$
are true.
Now, let $\displaystyle s$ and $\displaystyle S$ satisfy the following relations:
$\displaystyle n^{(k)}=\sum_{j=1}^{k}s(k,j)n^{j}$
and
$\displaystyle n^{k}=\sum_{j=0}^{k}S(k,j)n^{(j)},$
which are called as the Stirling numbers of first and second kind, respectively (also see Stirling number - Wikipedia, the free encyclopedia).
Then, lets turn back to the problem.
$\displaystyle \sum_{i=0}^{n-1}i^{k}=\sum_{i=0}^{n-1}\sum_{j=0}^{k}S(k,j)i^{(j)}$
.........$\displaystyle =\sum_{j=0}^{k}S(k,j)\sum_{i=0}^{n-1}i^{(j)}$
.........$\displaystyle =\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}\sum_{i=0}^{n-1}\Delta i^{(j+1)}$
.........$\displaystyle =\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}n^{(j+1)}$
.........$\displaystyle =\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}\sum_{\ell=1}^{j +1}s(j+1,\ell)n^{\ell}$
.........$\displaystyle =\sum_{j=0}^{k}\sum_{\ell=0}^{j}\frac{S(k,j)s(j+1, \ell+1)}{j+1}n^{\ell+1}.$
Finally, if $\displaystyle k$ is known, you may simplify the last term above.
Check the result for $\displaystyle k=2$.

7. We can use more simple formula to find a sum $\displaystyle 1^m+2^m+...+n^m$:

$\displaystyle \sum\limits_{k = 1}^n {k^m } = \frac{{(n + 1)^{m + 1} - 1}}{{m + 1}} - \frac{1}{{m + 1}}\sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} ,{\text{ }}m \in \mathbb{Z}^ + .$

We can deduce this formula with a binomial theorem.

8. Originally Posted by DeMath
We can use more simple formula to find a sum $\displaystyle 1^m+2^m+...+n^m$:

$\displaystyle \sum\limits_{k = 1}^n {k^m } = \frac{{(n + 1)^{m + 1} - 1}}{{m + 1}} - \frac{1}{{m + 1}}\sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} ,{\text{ }}m \in \mathbb{Z}^ + .$

We can deduce this formula with a binomial theorem.
I agree with my countryman.

9. Originally Posted by DeMath
We can use more simple formula to find a sum $\displaystyle 1^m+2^m+...+n^m$:

$\displaystyle \sum\limits_{k = 1}^n {k^m } = \frac{{(n + 1)^{m + 1} - 1}}{{m + 1}} - \frac{1}{{m + 1}}\sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]} ,{\text{ }}m \in \mathbb{Z}^ + .$

We can deduce this formula with a binomial theorem.
I am worried about the "simplicity" of this formula...

Doesnt $\displaystyle \sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]}$ look more formidable than $\displaystyle 1^m+2^m+...+n^m$?

Or do you have a closed form solution for that beast?

10. I do not think there is a closed formula...but i may be wrong

11. Originally Posted by Isomorphism
I am worried about the "simplicity" of this formula...

Doesnt $\displaystyle \sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]}$ look more formidable than $\displaystyle 1^m+2^m+...+n^m$?

Or do you have a closed form solution for that beast?
To add on to this...would you have to calculate $\displaystyle \sum_{k=1}^{n}k^{2},\sum_{k=1}^{n}k^3,\cdots,\sum_ {k=1}^{n}k^{m-1}$ haha

12. Originally Posted by Isomorphism
I am worried about the "simplicity" of this formula...

Doesnt $\displaystyle \sum\limits_{s = 1}^m {\left[ {\frac{{\left( {m + 1} \right)!}}{{\left( {m - s} \right)!\left( {s + 1} \right)!}}\sum\limits_{k = 1}^n {k^{m - s} } } \right]}$ look more formidable than $\displaystyle 1^m+2^m+...+n^m$?

Or do you have a closed form solution for that beast?
Of course, you're right.
I wanted to show that we can represent $\displaystyle 1^m+2^m+...+n^m$ as the amount of the amounts of less powers $\displaystyle m$ with the binomial theorem.

I am sorry, I perhaps incorrectly said that the formula is simple.

13. Judging from the number of off-topic posts this thread collected at its tail-end (and which you can now find here: http://www.mathhelpforum.com/math-he...countries.html), I'd say that nothing much more that's on-topic is going to get added so (drum roll, maestro, if you please) .......