# Find number of sub-squares in portion of graph

i cam across this puzzle, we are supposed to find out the total number of squares present in this picture...

as being a computer programmer i designed a algo in my head for the solution and did a dry run in my head as well.

Start counting by square with highest dimension and then decrement the dimension by 1 step by step and at every decrement iterate the whole graph for matching dimensions & count them untill the dimension becomes zero... so

4x4 squares = 1
3x3 square  = 4
2x2 squares = 9
1x1 squares = 16


that makes 30 squares..

i was thinking isn't there a mathematical formula to calculate the number of sub-squares in a given squared-section of graph?

p.s.

i can see a pattern, here in the above square(4) + square(3) + square(2) + square(1) but i don't enough skills in discrete mathematics & numerical analysis to bring it down to an equation or formula but i am sure the formula already exists

-
possible duplicate: math.stackexchange.com/questions/48047/… – Julian Kuelshammer Nov 27 '12 at 7:51
in the comments there you can find the formula – Julian Kuelshammer Nov 27 '12 at 7:51

It is $$\sum_{k=1}^{n} k^2 = \frac{1}{6}n(n+1)(2n+1)$$

which can be prooved via induction.

For $n=4$ this will give you $\frac{1}{6}\cdot4\cdot5\cdot9=30$

-
how can i induce this & apologies for this question, i am new to this sorta stuff plus i am not a mathematician.. – Junaid Saeed Nov 28 '12 at 18:20
Do you want to know how to proof the formular I gave to you, or do you want to proof that there are really $\sum k^2$ subsquares? – user127.0.0.1 Dec 1 '12 at 8:30
the second part.. i want to know the steps used to arrive at this conclusion... for the learning purposes.. – Junaid Saeed Dec 2 '12 at 14:36