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

Dubulus · #1 $Old$ 11-03-2008, 11:21 AM

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!

HallsofIvy · #2 $Old$ 11-03-2008, 11:50 AM

Quote:

Originally Posted by Dubulus $View Post$

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

whipflip15 · #3 $Old$ 11-05-2008, 04:52 AM

If you just need the formula.

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

shwetabhageria · #4 $Old$ 11-08-2008, 10:30 PM

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.

I hope this will help you in clarifying your doubts.

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

whipflip15 · #5 $Old$ 11-09-2008, 02:39 AM

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

never_fear · #6 $Old$ 11-12-2008, 04:34 AM

very good analysis

bkarpuz · #7 $Old$ 12-20-2008, 11:01 AM

In general, you can easily estimate
$\sum_{i=0}^{n-1}i^{k},$
where $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 $\Delta f(n)=f(n+1)-f(n)$ .
And the factorial function for $n,k\in\mathbb{N}$ is defined as $n^{(k)}:=n(n-1)\cdots(n-k+1)$ (exactly $n$ numbers of successive terms are being factored), and for convenience $n^{(0)}:=1$ .
It is not hard to see that
$\Delta n^{(k)}=kn^{(k-1)}$ and $\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 $s$ and $S$ satisfy the following relations:
$n^{(k)}=\sum_{j=1}^{k}s(k,j)n^{j}$
and
$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.
$\sum_{i=0}^{n-1}i^{k}=\sum_{i=0}^{n-1}\sum_{j=0}^{k}S(k,j)i^{(j)}$
......... $=\sum_{j=0}^{k}S(k,j)\sum_{i=0}^{n-1}i^{(j)}$
......... $=\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}\sum_{i=0}^{n-1}\Delta i^{(j+1)}$
......... $=\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}n^{(j+1)}$
......... $=\sum_{j=0}^{k}S(k,j)\frac{1}{j+1}\sum_{\ell=1}^{j+1}s(j+1,\ell)n^{\ell}$
......... $=\sum_{j=0}^{k}\sum_{\ell=0}^{j}\frac{S(k,j)s(j+1,\ell+1)}{j+1}n^{\ell+1}.$
Finally, if $k$ is known, you may simplify the last term above.
Check the result for $k=2$ .

DeMath · #8 $Old$ 01-05-2009, 02:50 PM

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

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

Russian · #9 $Old$ Yesterday, 05:57 PM

Quote:

Originally Posted by DeMath $View Post$

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

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