Boring (or not) Math Post Ahead

Dan seems to have gone back to his roots with a post about lit, so I guess it wouldn't hurt me to go back to mine.

A few days back, I had to teach this lesson about numbers using our still somewhat infuriating new textbook, which contained a bit about counting the number of times you could find a certain shape within another shape. That is, there was an irregular shape made of square tiles, and you had to find how many 1 x 1 squares, how many 2 x 2 squares, how many 2 x 3 rectangles, etc. are contained in it. I didn't read the directions, though, because most of the activities are stupid I don't really care about them, especially if another teacher is going to do all the work, anyway. So, I thought at first that it was asking how many squares total were contained in each of the previous shapes. As in, a 1 x 1 square contains one sqaure, and that's it; a 2 x 2 square contains 4 1 x 1 sqaures and 1 2 x 2 sqaure, so it contains five squares total. That got me to a problem of finding the number of squares in a given shape, which is way too hard, so I decided to reduce it to how many squares are in an n x n sqaure. This is a combinatorics problem of a sort, for any of those who have forgotten about that post.

So, let's define our counting function, say f(n) for n = 0, 1, 2, ... A good way to start is just by looking for a pattern.

f(0) = 0
f(1) = 1
f(2) = 1 + 4 = 5
f(3) = 1 + 4 + 9 = 14

And thus, a pattern emerges! What we are really looking for, it seems is a sum of the squares of the integers up to n. Or maybe that is just the first few steps of the pattern and then it diverges somehow. Now we will need a proof. Can you work one out? Probably. Here is how I figure it.

If we have an n x n square, we can label each tile by coordinates like so:

(1, 1) (1, 2) (1, 3)... (1, n)
(2, 1) (2, 2) ...
...
(n, 1) ... (n, n)

Forgive me if that doesn't hold up to html, but you should be able to figure it out.

If we want to count 1 x 1 squares, we can start in the upper left corner at (1, 1). From there, we can move right one tile, then right another, etc. and down one tile, then again, etc. Leaving us with n x n places to put that square.

To count 2 x 2 squares, we can start again in the left corner and move right, but we aren't able to move the left column of our 2 x 2 square to the final column, so we have only (n -1) places that way. Similarly, we can't move it all the way to the bottom, so we only have (n -1) places that way, too. That means there are (n-1) x (n-1), 2 x 2 squares.

Following the pattern, we will end with exactly 1 n x n square, and we see that what we have done here is add the squares of the integers up to n, though in reverse. So, our formula is good!

Good in a sense, anyway. Anyone who has taken calculus (and probably anyone who has taken Algebra II) should be able to tell you that these summations, with their sigma forms and all, for those who remember, aren't particularly nice when your n gets anywhere even remotely considered "big." For us, "big" means probably around 4 or 5, but for John it's probably more like 13 or 29 or something. For the computer science-y people there, we can actually figure an operation count here. For some n, we are doing n multiplications and n additions (assuming we add 0, which seems stupid unless you want to make your program crash when it gets n=0). So, I suggest we pull an 8 year old Gauss maneuver and get us a nice fixed number of multiplications/additions.

When I say Gauss maneuver, I am referencing Carl Friedrich Gauss, who was possibly the smartest dude to have ever lived. There is a story about him that when he was still a wee lad, one of his teachers got annoyed with him being so smart and had him sum all the integers from 1 to 100, thinking it would take quite a bit of time. Gauss almost immediately came up with the formula for doing this. It was already known, but it's still pretty impressive since he was doing it at an age when people generally can't abstract whatsoever. That formula is actually pretty easy to prove for us adults if you think about it a bit. It's

g(n) = (1/2)n(n+1). If you can't get it, I'd suggest stacking up boxes like a staircase and noting how much easier it would be to count if you had a rectangle instead of a staircase.

Anyway, the point of that little sidebar is to note that when adding the first power of n, we get a quadratic polynomial as the closed form. It is intuitive, maybe, to think that if we add the squares of integers, our closed form will be a cubic. It is fortunate for us that our intuition is right. I don't actually know how intuitive it is, but we can come back to that with a later problem that should sort of bound our form here in a sense. I really just remembered that the powers need to go up, but could never remember what affine functions of n are the factors. I don't think anyone ever does, but that is why textbooks have appendices.

So, what do we do if we are looking for a cubic polynomial? You could always ask your graphing calculator, assuming it is TI-high enough. But why not do it the old fashioned way? Because it turns out that the way to do that is a system of equations, which nobody likes.

A cubic should look like this

f(x) = ax^3 + bx^2 + cx + d. Now we just need to plug in our values of x. I switched to x because that is what I am used to for algebra but it is the same as the n from before.

We are fortunate that f(0) = 0, since that means d = 0, so we have really only a system of three unknowns to deal with. What's the difference? You can look at operation counts for Gauss-Jordan elimination on matrices of size m x m if you are really curious. Suffice it to say that solving a system of even three variables is deemed computer work once you get out of Algebra II.

Our other points here are

f(1) = 1; f(2) = 5; f(3) = 14, if you forgot. Coupled with the handy zero, that gives us four points, just enough to define a cubic.

So, we have

a + b + c = 1
8a + 4 b + 2c = 5
27a + 9b + 3c = 14

That should be enough to send you running for the hills of Mathematica, but I didn't have that as an option at the time, so I brute forced a solution, which you are free to do if you want. Here is what you should get

(1/6)n(n+1)(2n+1). Lots of work for no reason. We don't yet actually know that this is the formula since we were just guessing that it is a cubic. If you want to prove it, you can apply mathematical induction, which I will post about doing if anyone asks for it, but this post is already long enough.

I will mention one last thing about intuiting the degree from before. If you look at the sum of the cube of the integers up to n, you will get

h(0) = 0
h(1) = 1
h(2) = 1 + 8 = 9
h(3) = 1 + 8 + 27 = 36
h(4) = 1 + 8 + 27 + 64 = 100

Those last number should set off a whistle in your math brain. They're all perfect squares, of 0, 1, 3, 6, and 10, in that order. Those numbers should set off another whistle if you were working on Gauss's problem from before. What you have here is that the sum of the cubes up to n is equal to the square of the sum up to n. You don't have to go through the whole algebra here to prove it or anything, just induct like before.

But here we see that we have a fourth degree polynomial. When we summed just the integers, we got a second degree polynomial. Since the sum of the squares should be in the middle of these two sums all the way, it makes sense to guess that we are looking for a third-degree polynomial.

Rock on!