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:
Quote:
|
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?
Linear Mode
