# Squares on a checkerboard

How many squares of all sizes arise using an $n$-by-$n$ checkerboard? How many triangles of all sizes arise using a triangular grid with sides of length $n$ ?

-
I actually think I have the first part down, it should just be $\displaystyle \sum_{i=1}^{n}i^2$. For the second part, I've got nothing. – rapidash Jun 27 '11 at 19:40
the square formed by a2,b1,b2,b3,c2 (in chess notation) is not counted? You need to clarify which squares you intend to count... – Aryabhata Jun 27 '11 at 19:44
@Aryabhata: just curious...How does chess notation work? (I suppose I could try googling "chess" or the like). – amWhy Jun 27 '11 at 19:51
@amWhy: The columns are labelled a to h (starting from left) and rows are 1 to 8 starting from bottom. a1 is the bottom left square. – Aryabhata Jun 27 '11 at 19:56
Aryabhata's question is whether you only count squares with sides parallel to the sides of the board, or count diagonally positioned squares as well. – Ross Millikan Jun 27 '11 at 20:01

HINT:

It is very simple to see how many 1-squares fit. What about a 2-square (natural notation)? Well, let's only place the top-left square. How many places can we put the top-left square of a 2 by 2 on the board and have it fit? And so on? This leads to your intuition being correct.

This works for triangles too - but I'll let you figure that out.

-
It is slightly harder for triangles when you try to count those pointing in the other direction. – Henry Jun 28 '11 at 0:02

For the triangular grid, can you convince yourself that all the triangles are equilateral (assuming the grid is)?

-

Your answer for the squares is correct. For the triangles, you do something similar, with a twist.

For the triangles in the original direction you have 1 big triangle, 3 triangles one size smaller, 6 another size smaller and you should be able to persuade yourself that these continue as the triangle numbers $1,3,6,10,15,21,\ldots$.

For the triangles in the other direction, if you have an original triangle with an even length side you have 1 triangle with side half that of the original triangle, 6 triangles one size smaller, 15 another size smaller etc., while if you have an original triangle with an odd length side you have 3 triangles with side half that of the original triangle rounded down, 10 triangles one size smaller, 21 another size smaller etc.

Adding all these up is not trivial, but you should get OEIS A002717 as your result.

-