Monday, August 30, 2010

Generating perfect squares without memorization

Hey, ever had to memorize the perfect squares for a school assignment, to be able to list them all, say, up to like 20 or so, such that you can give them without using a calculator?
I did once, in 8th grade algebra!

Well, I was at least expected to memorize them. But I didn't. Because I didn't need to! I had a generating function for the perfect squares, and for relatively small numbers I could list them without a calculator!

Since the assignment -- a pop quiz -- was just to list the squares of the first 20 counting numbers (so 1^2, 2^2, 3^2, etc.), basically in order, all I needed to do was find some sort of relationship between one square and the next. It's pretty clear that, y'know, the difference between the first two squares (1 and 4) is 3, then the second (4 and 9) is 5, etc. In fact, the difference between any two consecutive perfect squares is consecutive odd numbers!

Now, I bet one or two of you seriously don't believe me on that one. But I'll show you it's for real. Of course, you could just look up a multiplication table, but it'll be a bit more enlightening to do something more like induction to demonstrate.

For a given counting number n, the formula for that value's square is, of course, just n^2.
For the consecutive perfect square, (n+1)^2, that's just (n+1)(n+1).
If we expand that out we have n^2+2n+1, which you might remember as a formula from your high school algebra courses.

Although I don't think memorization is the path to mathematic success, the formula (x+y)^2=x^2+2xy+y^2 comes up often enough that's it's worth recalling. Still, it's not something too hard to figure out either way, if you know what you're doing.

Thus we actually can express the next perfect square in terms of the previous square; note the "n^2" term in it. So we're taking the previous square and adding other terms to it.

What are those other terms? 2n+1, in fact. 2n is an even number, fairly clearly, due to that factor of two you see right there. Adding 1 to it makes it an odd number. Increasing n by one causes 2n+1 to increase by two. Hence, you'll add a consecutively higher odd number to the previous perfect square in order to get the next one; if you list them all starting at 1^2=1, you can get pretty far.

In fact, 0^2=0 and then 1^2=0+2(0)+1=1, so we've demonstrated the initial case. We've also shown it holds for (n+1) too, so let's just try this for (n) then, just to demonstrate that what he have here holds true for all the natural numbers!

n^2=(n-1)^2+2(n-1)+1=2n^2-2n+1+2n-2+1=2n^2 -- hey, we get the initial expression back! It definitely works -- not that this is surprising, since we did in some sense derive it back in high school.

That's basically mathematical induction in a nutshell. Take an expression for (n), demonstrate it works for the initial case (which is generally 1 or 0), and then demonstrate it for (n+1) -- which means it holds for every natural number after the initial case! We've done a few other steps along the way to try to make it a little clearer that the formula works like that, but that's the basic setup.

Lest you stand in awe at undeserved mathematical prowess, at the time I found the pattern, I wasn't interested in formalizing my formula. I just understood that it worked, at least for the numbers I was working with. So don't feel too bad if this is a little bit confusing, especially since I don't have the luxury of LaTeX.

But yeah, you start with 1, add 3 and get 4, add 5 and get 9, add 7 and get 16, add 9 and get 25, add 11 and get 36, add 13 and 49, add 15 and get 64, add 17 and get 81, add 19 and get 100, add 21 and get 121, etc. etc.

This was going to be a blog post on the alcohols I've had recently, but I've still got a few different beer bottles hanging out in the minifridge (and indeed, a couple of them are pretty good), but I didn't want to post it until I'd had all of them, and I didn't want to drink them all at once.

1 comment:

  1. I remember one of the first math "tricks" I ever learned was for calculating squares in your head. Say you want to calculate 51 squared. You add and subtract 1 and calculate

    50*52 = 2600,

    then you add back in 1^2 since that's what you added and subtracted to get

    51^2 = 2601.

    Works because n^2 = (n-a)*(n+a) + a^2 for any a. You just choose a so that either n-a or n+a is something easy to multiply.

    More examples:

    16^2 = 20*12 + 4^2 = 240 + 16 = 256.

    73^2 = 70*76 + 3^2 = 4900 + 420 + 9 = 5329.

    Thought you might like this since it's about squares.