Grid Formula Proof

• Nov 23rd 2011, 08:28 PM
jstarks44444
Grid Formula Proof
Hey all, I need some guidance on a problem I've been working on involving a grid formula. Please see the problem below:

(i) Consider a n x n grid of uniform size. Guess a formula for the number of different squares (of varying size) and prove it.

Attachment 22869

Above is an illustration for a 2 x 2 grid.

(ii) What is your answer when we consider the same problem for a m x n grid?

Not sure where to start off with this one....all help is appreciated!
• Nov 24th 2011, 03:26 PM
HallsofIvy
Re: Grid Formula Proof
Well, do you understand the illustration? How many square are there?

Now draw a corresponding illustration for the 3 by 2 and 3 by 3 grids. look for a pattern.
• Nov 25th 2011, 04:59 PM
jstarks44444
Re: Grid Formula Proof
Well, 3 x 3 would produce 14 possible squares. I believe the following formulas work but I'm not sure how to prove it:

Summation from i=1 to n of [ i^2 ]
and
n(n+1)(2n+1) / 6

Maybe induction?
• Nov 25th 2011, 05:11 PM
Plato
Re: Grid Formula Proof
Quote:

Originally Posted by jstarks44444
Well, 3 x 3 would produce 14 possible squares. I believe the following formulas work but I'm not sure how to prove it: Summation from i=1 to n of [ i^2 ]
and n(n+1)(2n+1) / 6

It is very well know that $\sum\limits_{k = 1}^n {k^2 } = \frac{{n(n + 1)(2n + 1)}}{6}$.

So that is not the question here.
Why does that count the number of squares in an $n\times n$ grid?

The larger question is:
What counts the number of squares in an $m\times n$ grid?
• Nov 26th 2011, 04:47 AM
bourbaki87
Re: Grid Formula Proof
Hi Plato, I've got a formula f(n,m) to count the number of squares an n by m generates. I've got a question on proving it. The smallest case is n=2,m=1 (I let n>m WLOG) so the formula must be shown to be true for any n>=2,m>=1. Using induction and assuming f holds for some (a,b), should I show that f(a+1,b) holds and f(a.b+1) holds. Given both of these cases hold f(n,m) holds for n>=2,m>=1, as requied?
• Dec 7th 2011, 08:16 AM
jstarks44444
Re: Grid Formula Proof
I still am not understanding how to prove part i????
• Dec 7th 2011, 10:37 AM
Plato
Re: Grid Formula Proof
Quote:

Originally Posted by jstarks44444
I still am not understanding how to prove part i????

I really do not understand what you are asking.

If you are asking how to prove $\sum\limits_{k = 1}^N {k^2 } = \frac{{N\left( {N + 1} \right)\left( {2N + 1} \right)}}{6}$
then by all means use induction.

However, as I said before I do not think that is the point of this question. I think you are to say why that sum counts the squares.

That why part b) is a generalization question.