2
$\begingroup$

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

  • 0
    possible duplicate: http://math.stackexchange.com/questions/48047/squares-on-a-checkerboard2012-11-27
  • 0
    in the comments there you can find the formula2012-11-27

1 Answers 1

3

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$

  • 0
    how can i induce this & apologies for this question, i am new to this sorta stuff plus i am not a mathematician..2012-11-28
  • 0
    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?2012-12-01
  • 0
    the second part.. i want to know the steps used to arrive at this conclusion... for the learning purposes..2012-12-02