# Magical Numbers



## Skyler (Oct 13, 2009)

I just concluded a session of helping out some classmates in the Discrete Mathematics course I'm taking, and I thought I'd share one of the most amazing math problems I've done.


[Executive summary for those who dislike algebra: I take the formula *n^3 - n* and prove that it's divisible by the number 6. True story.]


The problem was as follows:



> Prove that 6 divides n^3 - n whenever n is a nonnegative integer.



You look at that, and you're thinking "Oookay... ain't no way 6's comin' out o' that!" (At least, if you're from around here, you do; your favorite local accent may vary.) But, not so!

In fact, _*n^3 - n*_ is divisible by 6 when n is, say, 0. Then you have 0^3-0, which is 0, which, interestingly enough, is divisible by 6.

Okay, but that doesn't tell us that it's true for ALL nonnegative integers. You have to use a tool called mathematical induction--that means, if you can show that n^3 - n is divisible by 6 when n is some integer(we used 0), then you just have to show that that's also true when you substitute (n+1) for n.

Which basically means, you have to take "_*n^3 - n*_" and somehow squeeze a 6 out of it.

Actually, you take _*(n+1)^3 - (n+1)*_ and squeeze a 6 out of it. 

Anyway, if you spread that out, you get _*(n+1)(n+1)(n+1) - (n+1)*_. I still don't see a 6 here anywhere. Not up this sleeve... ahem.

_*(n+1)*(n+1) is (n^2 + 2n + 1)*_, so we have _*(n^2 + 2n + 1)(n+1) - (n+1)*_. Multiplying the _*(n^2 + 2n + 1)*_ and the last _*(n+1)*_ gives us _*(n^3+ 3n^2+ 3n+1)*_.

So now we are at _*(n^3 + 3n^2 + 3n + 1) - (n + 1)*_. It's looking a little more promising--there's some threes there now that weren't there before--but still no sixes. I guess we'll have to squeeze some more. Let's start by eliminating the parentheses.

_*n^3 + 3n^2 + 3n + 1 - n - 1*_ (when we distribute the negative sign in front of the (n+1))

Now hang on just a second. We just showed that _*(n^3 - n)*_ was divisible by 6 when we plugged in 0, remember? Looking at the variables we have now, I see an n^3 and a -n. Let's pack those in a parenthese and set them aside for now.

_*(n^3 - n) + 3n^2 + 3n*_ (Notice the +1 and -1 canceled!)

Hmm... let's start by getting factoring the 3s out of those last two variables.

_*(n^3 - n) + 3(n^2 + n)*_

Now it's starting to look like all is lost. There's a three, but everyone knows you have to have a two to make six!

But wait, all is not lost yet. Believe it or not, we can still squeeze a two out of it!

Let's look at that formula: _*3(n^2 + n)*_. _*n^2*_ is the same thing as saying _*n*n*_, so what we have can also be written as _*3(n*n + n)*_. And remember from grade school that multiplication is just repeated addition? That means that saying 5*5 is like saying 5+5+5+5+5. It's the same way with n--you have n ns being added together. Only in this formula, we have an extra n being added too! So we really have n+1 ns being added together. That means we can rewrite the formula as _*3*n*(n+1)*_.

Big deal. Still no two.

Or is there?

Remember the laws about even numbers? Well, either n or (n+1) is going to be an even number. If n is even, then n is even(umm... yeah.) If n is odd, then n+1 is even. And what does even mean? *Divisible by two*.

Oh. There's the two. 

So, _*3*n*(n+1)*_ is divisible by 3, and it's divisible by 2. That means it's also divisible by 3*2, or 6.

Isn't it amazing how you can pull a 6 out of an _*n^3 - n*_?(well, okay, an _*(n+1)^3 - (n+1)*_, but still!) More to the point, isn't God(who created mathematics!) amazing?


----------



## ewenlin (Oct 13, 2009)

Yes, I agree God is amazing!

Thanks for sharing this.


----------

