Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

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

enter image description here

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

share|improve this question
    
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
add comment

1 Answer 1

up vote 3 down vote accepted

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.