Results 1 to 7 of 7

Math Help - Grid Formula Proof

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    86

    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.

    Grid Formula Proof-grid.png

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,971
    Thanks
    1637

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    86

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1

    Re: Grid Formula Proof

    Quote Originally Posted by jstarks44444 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2011
    Posts
    7

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2010
    Posts
    86

    Re: Grid Formula Proof

    I still am not understanding how to prove part i????
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1

    Re: Grid Formula Proof

    Quote Originally Posted by jstarks44444 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. formula proof?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 10th 2010, 03:15 PM
  2. Complex Formula Proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 20th 2010, 03:52 AM
  3. Proof of the Lagrange formula
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 13th 2010, 09:11 PM
  4. Midpoint formula (proof) ??
    Posted in the Geometry Forum
    Replies: 8
    Last Post: April 28th 2009, 04:32 AM
  5. Integration formula proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 7th 2007, 10:13 AM

Search Tags


/mathhelpforum @mathhelpforum