Thread: 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.



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!

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.

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?

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 $\displaystyle \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 $\displaystyle n\times n$ grid?

The larger question is:
What counts the number of squares in an $\displaystyle m\times n$ grid?

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?

I still am not understanding how to prove part i????

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 $\displaystyle \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.