Squares in Rectangle Formula

Date: 06/30/2003 at 14:26:29
From: Jamie
Subject: Squares in rectangle formulae

What is the equation for the number of squares in a rectangle (like 
the chessboard puzzle)? 

I have worked out that if the width is 2, then the formula for 2xn is 
equal to 3n-1. Is there an equation for a rectangle with a width of 
three? If so, how do you work it out and what is it?

I have made a chart but can see no relationship.

dimensions  1x1      2x2     3x3     total
3x2          6        2        0        8
3x3          9        4        1       10
3x4         12        6        2       20

Date: 07/03/2003 at 04:29:48
From: Doctor Anthony
Subject: Re: Squares in rectangle formulae

In the general case we have an n x m rectangular board.

Consider the left-hand vertical edge of a square of size 1 x 1. This 
edge can be in any one of n positions. Similarly the top edge can 
occupy any one of m positions for a 1 x 1 square. So the total number 
of 1 x 1 squares = n x m.

For a 2 x 2 square the left-hand edge can occupy (n-1) positions and 
the top edge (m-1) positions, giving (n-1)(m-1) squares of size 2 x 2.

Continuing in this way we get squares of size 3 x 3, 4 x 4 and so on.

If we have an 8 x 9 board the numbers of squares are as follows:

 Size of Square        Number of Squares
 --------------        -----------------
    1 x 1                  8 x 9  = 72
    2 x 2                  7 x 8  = 56
    3 x 3                  6 x 7  = 42
    4 x 4                  5 x 6  = 30
    5 x 5                  4 x 5  = 20
    6 x 6                  3 x 4  = 12
    7 x 7                  2 x 3  =  6
    8 x 8                  1 x 2  =  2
  ----------------------------------------
                           Total  = 240

For the general case of an  n x m  board, where m = n + t

             n                n
We require  SUM[r(r + t)]  = SUM[r^2 + rt} 
            r=1              r=1


           = n(n + 1)(2n + 1)/6 + tn(n + 1)/2

           = [n(n + 1)/6]*[2n + 1 + 3t]

No. of squares = [n(n + 1)/6]*[2n + 3t + 1]  .......(1)

In the example above t = 1 and so

     No. of squares  = 8 x 9/6[16 + 3 + 1]

                     = (72/6)[20]

                     = 240    (as required)

The general formula for an (n x n+t) board is that given in (1) 
above.

    No. of squares = [n(n + 1)/6]*[2n + 3t + 1]  


Example(1): How many squares are there in 20 x 30 rectangular board?

Here n = 20 and t = 10

  Number of squares = 20 x 21 x (1/6) x [40 + 30 + 1]

                    =  (1/6) x 20 x 21 x 71

                    =  4970

Example(2): How many squares are there in a 31 x 42 rectangular board?

Here n = 31 and t = 11

 Number of squares = 31 x 32 x (1/6) x [62 + 33 + 1]

                   = (1/6) x 31 x 32 x 96

                   =  15872

For the moment I think you should simply remember the formula

Number of squares = (1/6)*n(n + 1)(2n + 3t + 1)

where the rectangle has sides n and n + t.

The derivation depends on knowing the formulae for the sums of 
series like

   1^2 + 2^2 + 3^2 + 4^2 + ...... + n^2  = n(n+1)(2n+1)/6

and  1 + 2 + 3 + 4 + ..... + n   = n(n+1)/2

You will probably be covering this topic in lessons before long and 
the formula I used for the number of squares in a rectangle will then 
become clear.

If you want to see the derivation of the sums of the series above you 
can write in again, but at the moment you may find the work difficult 
to follow.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/13/2004 at 11:17:30
From: Brooke
Subject: The number of squares in rectangles/squares

I still don't get how you came to find the rules as:

  Squares in Rectangles:  n(n + 1)/6*[2n + 3t + 1]
  Squares in Squares:  (n(n + 1)(2n + 1))/6

I don't understand where you have gotten the 6 from and how to 
section the equation into brackets.  Is there some way that you
can point me in the right direction to coming to these conclusions?

Date: 02/13/2004 at 16:30:39
From: Doctor Greenie
Subject: Re: The number of squares in rectangles/squares

Hi, Brooke -

I found Doctor Anthony's explanation of the problem on that page 
quite good -- but then, I already understand the problem.  I think 
there are a couple of things that could be done to improve his 
presentation of the material on that page.

The key to his method of deriving the formula (which is the method I 
find easiest to understand) is to consider the rectangle as a square 
array of squares with "extra" columns of squares added on.  With this 
approach, we can find

(1) The number of squares in an n-by-n square is

  1^2 + 2^2 + 3^2 + ... + n^2

This sum is given by the formula

  n(n + 1)(2n + 1)/6

(2) When we start with this n-by-n square and add 1-by-n columns of 
squares, the number of additional squares in the overall array 
resulting from the addition of each new column is

  1 + 2 + 3 + ... + n

This sum is given by the formula

  n(n + 1)/2

So, for example, the total number of squares in a 10-by-6 array of 
squares is the number of squares in the square 6-by-6 array, plus 4 
(that is, 10-6) times the number of squares added with each 
additional column of 6 squares.  Doctor Anthony uses "n" as the 
dimension of the square array of squares and "t" as the number of 
additional columns, so the total number of squares in this case is 
given by the formula

  n(n + 1)(2n + 1)/6 + (t)*[n(n + 1)/2]

With the specific case of a 10-by-6 array (n=6, t=4), this formula 
gives the total number of squares as

  6(7)(13)/6 + 4(6)(7)/2 = 91 + 84 = 175

Perhaps the most confusing part of Doctor Anthony's response (in my 
mind, at least) is that he disguises the formula above by combining 
the two terms into a single fraction with a common denominator.  To 
do that, the second fraction is multiplied by 3 in the numerator and 
denominator (to get the common denominator "6"), the two fractions 
are combined into a single fraction, and the common factors "n" and
"(n+1)" in the numerator are factored out.  The steps are:

  n(n+1)(2n+1)   (t)(n)(n+1)
  ------------ + -----------
       6              2

  n(n+1)(2n+1)   3(t)(n)(n+1)
  ------------ + ------------
       6              6

  n(n+1)(2n+1) + 3(t)(n)(n+1)
  ---------------------------
               6

  [n(n+1)]*[(2n+1) + 3t]
  ----------------------
             6

  n(n+1)(2n + 1 + 3t)
  -------------------
           6

  n(n + 1)(2n + 3t + 1)
  ---------------------
            6

  n(n + 1)(2n + 3t + 1)/6

I much prefer the formula in the original form, because in that 
form you can see how the formula was obtained.  

Here are a couple of other links I found in the Dr. Math archives 
which I thought were useful; each of them also contains links to 
additional pages in the archives:

  Formula for Sum of First N Squares
    

  Sum of Squares Derivation
    

These pages provide more details on this topic.  Specifically, one of 
them contains a derivation of the formula for the sum of the first n 
squares, which appears to be one of the things you specifically asked 
about in your message to us.

I hope all this helps.  Please write back if you still have questions 
about any of this.

- Doctor Greenie, The Math Forum