Precalc problem (mathmetical induction)

"Prove that for 3 consecutive numbers (n, n+1, n+2), the sum of their cubes is a factor of nine."

Can anyone show me how to prove this through mathematical induction?

I haven't done this for years, but I can give it a shot.

Prove true for n = 1, ie prove 1^3 + 2^3 + 3^3 is divisible by 9.
Proof
= 1^3 + 2^3+ 3^3
= 1 + 8 + 27
= 36
= 4*9
Therefore it's true for n = 1

Assume true for n = k, ie assume k^3 + (k+1)^3 + (k+2)^3 = 9M where M in an integer.

Prove true for n = k+1, ie prove (k+1)^3 + (k+2)^3 + (k+3)^3 is divisible by 9.
Proof:
= (k+1)^3 + (k+2)^3 + (k+3)^3
= (k+1)^3 + (k+2)^3 + k^3 + 9k^2 + 27k + 27
= 9M + 9k^2 + 27k + 27
= 9(M+ k^2 + 3k+ 9)

Therefore it's true for n = k+1

Since it's true for n = 1 and it's true for n = k+1, blah blah blah, true for all n.

Base case: Prove it's true for (-1, 0, 1)
Sum of their cubes is... hey presto: 0. Which is to some extent divisible by 9.

Induction: Prove if it's true for n, then it's true for n+1
n: [n^3 + (n+1)^3 + (n+2)^3] has a factor of 9
n+1: [(n+1)^3 + (n+2)^3 + (n+3)^3]
So you have to prove that if the first equation is divisible by 9, so is the second one - probably by demonstrating that when you subtract one from the other, the difference is divisible by 9.

ohh i'm fucked. none of this rings a bell from when i took precal.

ohh i'm fucked. none of this rings a bell from when i took precal.

?

The idea is pretty straightforward:
- Prove that the hypothesis is correct for the next case if it is correct for one case. Basically forming a chain.
- Prove that it is true for a base case (most often, idk if all of them apply, is when k = 1 )

With the above two, it is deductively sound to conclude that the case k = 2 is also true, when k = 2 is true, k = 3 is also true, so on and so forth.

Can anyone show me how to prove this through mathematical induction?

I'll just assume that you know very briefly what induction is, so my explanation may be a little too detailed. Hopefully that's not an issue.

Many people have already given you a good start, but let us for convenience just state what an induction proof of the statement S does:

1. Prove that S is true for some number m.
   
2. Prove that if S(n) is true, then S(n+1) is also true.
   

The last part may not only be S(n+1), but S(n-1) as well. We'll look into this, as the case you showed us is such a proof.

First, start off by defining a function - people usually call this one P, but it doesn't matter - which is related to the proof you're supposed to show.
For this case, we can define P as one of these functions:



I'll use the latter, as it fits better to the proof - however, both works just as fine.

Next we need to find out is, as this is induction, if we need to prove the induction one direction or two directions. In this case, we need to prove it two ways (namely, both for n + 1 and n - 1). This is extremely important! If you only prove it one way, you've just done a halfway correct proof.

Now, as people earlier has shown, P(-1) and P(1) are both divisible by 9. I prefer to use P(0) (or P(1) whenever P(0) is not defined or not within the scope we're proving for) as it's convenient and looks nice, but it doesn't really matter.

So, if a number n is divisible by 9, it can be written as



It may sound stupid to point that out, but it'll be very important later on.

So, is P(0) divisible by 9? Indeed it is, we can split it up as above:



Now, we've done step 1: We've proven that P(n) is true for n = 0. Next thing we need to do, is to prove that if P(n) is divisible by 9, then P(n + 1) is also divisible by 9. As we need to prove this both ways, we'll do P(n - 1) afterwards.

Now, this is probably the hardest part: How can we use what we already know to show that this is true? Well, as Stereo stated, we can prove that the difference between these 3-sums are divisible by 9: We know that the difference between two numbers which is divisible by 9 is also divisible by 9!

Assume now that P(n) is divisible by 9: then we have that



Now, as we know that 9m is divisible by 9, we only have to prove that (n+3)^3 - n^3 is divisible by 9. If you expand the algebraic monster (n + 3)^3, you get



As we see, in the expanded version of (n+3)^3, only n^3 is not divisible by 9, but we're subtracting it from the value. Let's see here:



This proves that if P(n) is divisible by 9, then P(n + 1) is divisible by 9 as well! Now, as we showed earlier, P(0) is divisible by 9. This means that P(1) is divisible by 9, which again means that P(3) is divisible by 9. As you probably understand, now we've proven that for all numbers n >= 0, P(n) is divisible by 9.

But what about n - 1? This is usually very similar to the n + 1 case, so you can usually just modify the n + 1 case to work for n - 1 cases. I'll do that here: The first line contains an earlier line we've shown, and by shifting n + 1 to n and n to n - 1 in the second line, we can "swap" the places between P(n-1) and P(n):



Now, this is very simple. As you can see n^3 - (n + 3)^3 is just - ((n + 3)^3 - n^3), and we know that this is divisible by 9. Therefore, if P(n) is divisible by 0, then P(n - 1) is divisible by 9. Now we see that this holds for all integers!

(PS: The last part is not a proof, it's just an explanation on how to prove it.)

Noah

Looks like the explanation is pretty well covered, so I gotta ask... You're doing this in precalc? I didn't do this until "Beyond" Calc in Highschool. o__o

Looks like the explanation is pretty well covered, so I gotta ask... You're doing this in precalc? I didn't do this until "Beyond" Calc in Highschool. o__o

Yep, precalc. My school tends to excel in the math/science field so yeah....
@Noah
Got ninja'd like twice, but thanks for the help.