A math puzzle

BuzzLY

I was hoping that Weedpacket could help me with this, but I suppose any of you that are mathematically inclined could tackle this.

There is a puzzle that asks how many squares there are on a chessboard. This includes the obvious 64, but also includes all squares 2x2, 3x3, etc. Feel free to figure it out before you move on.

The answer (highlight to see it): 204, which is the sum of 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1
Of course, that was not good enough for me -- I wondered if there was a way to figure this out mathematically. I remembered something Weedpacket said a while ago, about any ordered sequence of numbers being describable as a formula. The answer in this case is "yes."

Now, I know what the formula is, but here's my problem -- how does one arrive at this formula? Does anyone know how to derive the formula for this puzzle given a square of n x n squares? In other words, prove that the formula is correct. Good luck.

Extra credit: Discover the formula for finding the number of squares in a rectangle that is n x m squares in dimension.

madwormer2

Lol. People have better things to do..... I hope.

Had a quick look, but I mean, it baffles me :S

jara06

Guess im somwhat bored ..

/*
64 = 15 + 49
49 = 13 + 36
36 = 11 + 25
25 =  9 + 16
16 =  7 +  9
 9 =  5 +  4
 4 =  3 +  1
 1 =  1 +  0
*/

$j = 0;
for ($i = 1; $i <= 15; $i = $i + 2)
{
	$j = $i + $j;
	echo $j ."<br>\n";
}

BuzzLY

Well, that's nice, Jara, but I think you misunderstand me. I'm not looking for a PHP program. I'm looking for the mathematical formula. This is the formula, in case anyone doesn't want to figure it out:

highlight to see it:
[color=#E1E4F2]n (n + 1) (2n + 1)
------------------
        6        

[/color]

What I'm looking for is WHY is that the formula? How is it derived? I'm thinking some mathematical incursion is involved, but I'm not entirely sure (and I really don't have a LOT of time on my hands 🙂 )

Incidentally, Jara, I think you're looking for this:

$n = 50;
$j=0;
for ($i = 1; $i <= $n; $i++)
{
    $j = $j + ($i ^ 2);
    echo "Number of squares in a $i by $i square: $j";}

jara06

heh, told you i was bored .. didnt mean anything by that piece of code... 🙂

Sgarissta

BuzzLY wrote:
Well, that's nice, Jara, but I think you misunderstand me. I'm not looking for a PHP program. I'm looking for the mathematical formula. This is the formula, in case anyone doesn't want to figure it out:
highlight to see it:
[color=#E1E4F2]n (n + 1) (2n + 1)
------------------
        6        

[/color]
What I'm looking for is WHY is that the formula? How is it derived? I'm thinking some mathematical incursion is involved, but I'm not entirely sure (and I really don't have a LOT of time on my hands 🙂 )

I'm really rusty, but I believe that's the general formula for the Summation of i^2. So basically, where 'n' is the number of repititions, the and 'i' is the incrementing value, and i² is the general formula, the equation you showed is the general form. Now, as to EXACTLY how that is derived, I couldn't tell you off hand, but in code, it looks something like:

$total=0;
while($i<=$n){
$total += $i^2; $i++;
}

Weedpacket

Okay, the formula is right; now the derivation. You want the intuitive "look and see" proof or the formal jobbie?

The look and see proof involves focussing on where the lower-left corner of each square can go. For the 8x8 square there's only one possibility. For the 7x7 square, its lower-left corner can go in the lower-left corner of the chessboard, or it could be moved one square up (but only one square), or one square to the right (but only one square), or one square each way. To give a total of four.

The lower-left corner of the 6x6 square can be in nine different locations, because it can be slid upwards or rightwards or both a maximum of two squares before running out of headroom.

And so on up to (or is that down to?) and including the 1x1 square.

Drakla

I tried to do some empirical way as I've completely rusted over with doing proofs, so far given an example 5 by 5 grid

x x x x x
x x x x x
x x x x x
x x x x x
x x x x x

Possible positions of each size of square

n n all small squares = 25
1 1 squares = (n - 0) (n - 0) = 5 5 = 25
2 2 squares = (n - 1) (n - 1) = 4 4 = 16
3 3 squares = (n - 2) (n - 2) = 3 3 = 9
4 4 squares = (n - 3) (n - 3) = 2 2 = 4
5 5 squares = (n - 4) * (n - 4) = 1

So it's the sum of

n² + (n - 1)² + (n - 2)² + (n - 3)² + (n - 4)² =

5n² + 1 + 4 + 9 + 16 - 2n - 4n - 6n - 8n =

n³ +

And I can't work it out from there, but some patterns are clear.

BuzzLY

Weedpacket wrote:
Okay, the formula is right; now the derivation. You want the intuitive "look and see" proof or the formal jobbie?

The look and see proof involves focussing on where the lower-left corner of each square can go. For the 8x8 square there's only one possibility. For the 7x7 square, its lower-left corner can go in the lower-left corner of the chessboard, or it could be moved one square up (but only one square), or one square to the right (but only one square), or one square each way. To give a total of four.

The lower-left corner of the 6x6 square can be in nine different locations, because it can be slid upwards or rightwards or both a maximum of two squares before running out of headroom.

And so on up to (or is that down to?) and including the 1x1 square.

Yes, I understand that... what I want to know is how the formula was originally created.

There are a couple of ways to show that the formula does indeed work. The first is by using mathematical induction. First, you assume that the formula works for the first few n values, by plugging in numbers. We'll show through induction that if it works for n, it also works for n+1. If we can prove that, we know it works for any value of n.

n(n+1)(2n+1)                6(n+1)^2 + n(n+1)(2n+1)
------------ + (n+1)^2   =  -----------------------
     6                                6

                       (n+1)[6(n+1) + n(2n+1)]
 Factor out (n+1):   = -------------------------
                                  6

                       (n+1)[6n + 6 + 2n^2 + n]
                     = -------------------------
                                  6

                       (n+1)[2n^2 + 7n + 6]
                     = --------------------
                                  6

                       (n+1)[(n+2)(2n+3)]
      Factor:        = -------------------
                                  6

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

You can see that this formula is the same as the original formula, with (n+1) substituted in for n. That is our proof that the formula does work.

Another way to "prove" the formula has merit is to picture the building of a pyramid out of the squares. The first level has 1 block, the second has 4, the third 9, etc. Now, the formula for the volume of a pyramid is base x width x height / 3. In this case, since base = width = height, the formula simplifies to n^3/3.

As we increase the size of our pyramid by adding more cubes, the "+1"s of our formula become less significant. If we remove them to simplify the equation, we get:

[code]n(n)(2n)

6[/code]
which of course simplifies to n^3/3.

That still does not show how the formula was originally derived. It may be that it's too complicated -- if anyone knows where to find the info, just point the way 🙂

Weedpacket

Well, that was how the formula was originally derived; the lower-left corners of the squares of a common size are themselves arranged in a square....

Oh, I see what you mean: you can prove that the sum of consecutive squares starting from 1 is such-and-such, but how did you know that it such-and-such in the first place?

Hang on, might have to be a few minutes before I get back to you on that; this board doesn't do MathML embedding 🙂

Hokay....
A standard tactic used to find sums of sequences is called the method of differences. Something to try just to see if it works. If the sum is

u +u +u ...+u
 1  2  3     n

You look around for a sequence v[r] such that u[r]=v[r]-v[r-1].

Replacing u[r] by v[r]-v[r-1] in the sum produces

v -v +v -v +v -v +v -v ...v -v
 1  0  2  1  3  2  4  3    n  n-1

The nice thing about this is that it is a lot simpler than it looks: most of the term cancel out, and you're left with v[n]-v[0].

All well and good. Now to apply it. u[r]=r^2. What should the v[r] be? We need v[r]-v[r-1]=r^2. It's a guess that v[r] will involve cubes: a guess suggested by the way squares stack to form a pyramid, and for that matter the way the natural numbers themselves stack to form a triangle (with T[n]=n(n+1)/2 which is a quadratic.) Let's try something simple. v[r]=(r+1)^3. Do that and

               3  3    2
v -v    = (r+1) -r = 3r +3r+1.
 r  r-1

Now we know what happens on the left if we sum from r=1..n - most of the terms cancel out and we're left with v[n]-v[0] - which in this case would be (n+1)^3-1. What happens on the right?

     3
(n+1) -1
=
   2              2              2                  2
3(1 )+3(1)+1 + 3(2 )+3(2)+1 + 3(3 )+3(3)+1 + ... 3(n )+3(n)+1

=
   2  2  2     2
3(1 +2 +3 +...n ) + 3(1+2+3+...+n) + 1+1+1+...+1 (n of those)

And just like that we're pretty much sweet - there's the sum of squares and I presume we already know how to simplify 1+2+...+n: now we just need to isolate the bit we really want by moving bits over to the other side of that equals sign:

     3        2  2  2     2     n(n+1)
(n+1) -1 = 3(1 +2 +3 +...n ) + 3------ + n
                                  2

 3            2  2  2     2     n(n+1)
(n+1) -1 - n = 3(1 +2 +3 +...n ) + 3------
                                      2

 3           n(n+1)      2  2  2     2
(n+1) - 1 - n - 3------ = 3(1 +2 +3 +...n )
                   2

 3           n(n+1)    2  2  2     2
(n+1) - 1 - n - 3------ = 1 +2 +3 +...n
                   2
-----------------------
            3

And there's the formula; now it's just a matter of tidying up:

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

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

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

  3     2                       2
2n  + 6n  + 6n + 2 - 2 - 2n - 3n - 3n
-------------------------------------
            6

  3     2
2n  + 3n  + n
-------------
      6

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

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

And as Gaspode the Wonder Dog would say, "Et Woller".

BuzzLY

Very nicely done. Thanks. You are officially "da man." 😃

The_Chancer

Gaspode ?? As in 500mile walkies ?? (or was I reading the wrong books ???)

Weedpacket

"Woof?", he said.

But now you can forget all that, because here's another MUCH simpler attack^{H^{H^{H^{H^Hpproach}}}} (dunno why it didn't occur to me in the first place):

First, we notice that the sum 1+1+1+...+1 = 1^{0+2^0+...+n⁰} is a linear polynomial in the number of terms (it's just n) and the sum 1+2+3+...+n = 1^{1+2^1+...+n¹} is a quadratic polynomial in the number of terms: (n^2+n)/2.

It's safe to expect that the function for 1^{2+2^2+...+n²} will be a polynomial - all we're doing is adding and multiplying integers - and let's take a punt based on the previous two formulae and guess that it may be a cubic, i.e., of the form an^3+bn^2+c*n+d. So what are the coefficients a, b, c, and d?

Well, whatever the formula is, we know that when n=1 the formula's value is 1, when n=2 the formula's value is 1+4=5, when n=3 the formula's value is 1+4+9=14, and when n=4 the formula's value is 1+4+9+16=30. In other words,

W	a*1^3 + b*1^2 + c*1^1 + d*1^0 =  1a +  1b + 1c + 1d = 1
X	a*2^3 + b*2^2 + c*2^1 + d*2^0 =  8a +  4b + 2c + 1d = 5
Y	a*3^3 + b*3^2 + c*3^1 + d*3^0 = 27a +  9b + 3c + 1d = 14
Z	a*4^3 + b*4^2 + c*4^1 + d*4^0 = 64a + 16b + 4c + 1d = 30

We have a set of four simultaneous linear equations W,X,Y,Z in four unknowns. If we're lucky, we should be able to use standard elimination techniques to solve this. For example, 4W-6X+4*Y-Z says that d=0. Not surprising: if d was anything else, the formula would give the wrong pyrimidal number for n=0. If we're unlucky we'd have to think of something else (maybe it's not a cubic but a quartic?)

We are lucky. There is a unique solution, in which a=1/3, b=1/2, c=1/6, and d=0, giving us a formula of (1/3)n^{3+(1/2)n^2+(1/6)n,} or n/i(2n+1)/6.

But is this correct, or are we just kidding ourselves? We can verify it in the usual inductive manner already mentioned in an earlier post, and it does indeed work for all natural n. Found, verified, proven. QED.