Another math problem.

[Novriil]

Hi!
I have this problematic exercise:
Prove with mathematical induction that the sum of three consecutive natural numbers that are in ^3 can be divided by 9.

I got so far:
n^3 + (n+1)^3 + (n+2)^3 =

I guess it has something to do with times 9 in the sum but I'm not sure.

 

[cmhardw]

This can actually be proven with a constructive proof, but even the inductive proof is relatively straight-forward, and actually shorter than the constructive proof. I guess what I am trying to say is, what exactly is your question about this proof?

I guess it has something to do with times 9 in the sum but I'm not sure.

If I can infer that this is your question; then yes, if you can factor out 9 from the resulting expression after expanding your sum, then that expression is divisible by 9. This is the key to this proof whether you approach it constructively, or inductively.

If you have a more detailed question, please list it here so that someone can help you.

Chris

 

[Diniz]

Spoiler

For n=1
1^3+2^3+3^3 = 1 + 8 + 27 = 36 = 9*4 ok!
Suppose that its valid for an arbitrary N, we will show to N+1:
(N+1)^3 + (N+2)^3 +(N+3)^3 = (N+1)^3 + (N+2)^3 + N^3 + 3^3 + 9N^2 + 27 N = N^3+ (N+1)^3 + (N+2)^3 + 9 (3+ 3N+ 3N^2) , which by induction is a multiple of 9.

 

[Novriil]

My question is what is the sum of this alg?

Also it would be good if there is an explanation.

 

[Carrot]

hmmm...

Spoiler

every third digit is divideable by 3... which means you can rewrite one of them as 9^2*x^2 (I think someone would explain why ), this number is very easily know for being divideable by 9.

so the statement says that the sum of 2 consecutive numbers that are NOT divideable by 3 cubed, is divideable by 9.

so let's rewrite that as (3m+1)^3+(3m+2)^3.
that can be written out as (this is going to be long...) 27m^3+27m^2+9m+1+27m^3+54m^2+36m+8, which can be shortened as: 54m^3+81m^2+45m+9 and factorizing that by 9 leaves us with: 9(6m^3+9m^2+5m+1)


the sum of 2 numbers' sum that are divideable by 9 will continously be divideable by 9

EDIT: just put my proof in the spoiler

 

[Novriil]

3 consecutive numbers

But I think that I understand by now.

E: I got it. Thanks Diniz!

Also thanks to Oscar and Chris!

 

[cmhardw]

Spoiler

For n=1
1^3+2^3+3^3 = 1 + 8 + 27 = 36 = 9*4 ok!
Suppose that its valid for an arbitrary N, we will show to N+1:
(N+1)^3 + (N+2)^3 +(N+3)^3 = (N+1)^3 + (N+2)^3 + N^3 + 3^3 + 9N^2 + 27 N = N^3+ (N+1)^3 + (N+2)^3 + 9 (3+ 3N+ 3N^2) , which by induction is a multiple of 9.

Almost... There is something to watch for in the inductive step.

Spoiler

(N+1)^3 + (N+2)^3 +(N+3)^3 = (N+1)^3 + (N+2)^3 + N^3 + 3^3 + 9N^2 + 27 N

You can't make this assumption, testing the known formula for N by using (N+1) instead. You have to somehow manipulate the formula for N to become the formula for (N+1)

Here is the correct inductive step for the proof:

(K)^3 + (K+1)^3 +(K+2)^3 = 9*Q where Q is an element of the natural numbers.

This is the assumption that our formula works for some k.

Now I will add -K^3 + (K+3)^3 to both sides:

(K)^3 + (K+1)^3 +(K+2)^3 - K^3 + (K+3)^3 = 9*Q - K^3 + (K+3)^3
(K+1)^3 +(K+2)^3 + (K+3)^3 = 9*Q - K^3 + K^3 + 9K^2 + 27K + 27
(K+1)^3 +(K+2)^3 + (K+3)^3 = 9*Q + 9K^2 + 27K + 27
(K+1)^3 +(K+2)^3 + (K+3)^3 = 9*(Q + K^2 + 3K + 3)
(K+1)^3 +(K+2)^3 + (K+3)^3 = 9*P Where P is an element of the natural numbers.

This restates the inductive rule for K+1 and proves that if our rule is true for K, then it is also true for K+1.

Your inductive step simply showed that the rule works for (K+1), it did not show that if it works for K, then it works for (K+1) as well.

Make sense?

 

[Diniz]

Spoiler

You can't make this assumption, testing the known formula for N by using (N+1) instead. You have to somehow manipulate the formula for N to become the formula for (N+1)

Here is the correct inductive step for the proof:

(K)^3 + (K+1)^3 +(K+2)^3 = 9*Q where Q is an element of the natural numbers.

This is the assumption that our formula works for some k.

Now I will add -K^3 + (K+3)^3 to both sides:

(K)^3 + (K+1)^3 +(K+2)^3 - K^3 + (K+3)^3 = 9*Q - K^3 + (K+3)^3
(K+1)^3 +(K+2)^3 + (K+3)^3 = 9*Q - K^3 + K^3 + 9K^2 + 27K + 27
(K+1)^3 +(K+2)^3 + (K+3)^3 = 9*Q + 9K^2 + 27K + 27
(K+1)^3 +(K+2)^3 + (K+3)^3 = 9*(Q + K^2 + 3K + 3)
(K+1)^3 +(K+2)^3 + (K+3)^3 = 9*P Where P is an element of the natural numbers.

This restates the inductive rule for K+1 and proves that if our rule is true for K, then it is also true for K+1.

Your inductive step simply showed that the rule works for (K+1), it did not show that if it works for K, then it works for (K+1) as well.

Make sense?

Nah, my argument is fine, i didnt make any assumptions at that point, i just showed that (N+1)^3 + (N+2)^3 +(N+3)^3 is N^3+ (N+1)^3 + (N+2)^3 plus a multiple of 9 and then used the induction hypotesis.

 

[cmhardw]

Nah, my argument is fine, i didnt make any assumptions at that point, i just showed that (N+1)^3 + (N+2)^3 +(N+3)^3 is N^3+ (N+1)^3 + (N+2)^3 plus a multiple of 9 and then used the induction hypotesis.

Aaaah, oops my bad. I only glanced at your proof after the point that you started from (N+1)^3 + (N+2)^3 + (N+3)^3

I still think it would be more appropriate for you to do the following, but perhaps this is just based on how I was taught inductive proofs when I first learned them.

Spoiler

N^3+ (N+1)^3 + (N+2)^3 = 9*Q where Q is an element of the natural numbers.
Add 9 (3+ 3N+ 3N^2) to both sides
N^3 + (N+1)^3 + (N+2)^3 + 9 (3+ 3N+ 3N^2) = 9*Q + 9 (3+ 3N+ 3N^2)
(N+1)^3 + (N+2)^3 + (N+3)^3 = 9(Q + 3+ 3N+ 3N^2)
(N+1)^3 + (N+2)^3 + (N+3)^3 = 9*P where P is an element of the natural numbers.

I was taught that it is bad form to start with anything other than the inductive assumption, here that: N^3 + (N+1)^3 + (N+2)^3 = 9*Q with Q an element of the natural numbers.

Yes I agree that your proof is valid, I'm just used to that format being considered "bad form." Obviously my only experience with this is my time in that class with that one professor, and I can see that your proof uses the inductive assumption in an appropriate way and that your proof is valid.

Any other opinions on the point made in this spoiler?

 

[kinch2002]

Aaaah, oops my bad. I only glanced at your proof after the point that you started from (N+1)^3 + (N+2)^3 + (N+3)^3

I still think it would be more appropriate for you to do the following, but perhaps this is just based on how I was taught inductive proofs when I first learned them.

Spoiler

N^3+ (N+1)^3 + (N+2)^3 = 9*Q where Q is an element of the natural numbers.
Add 9 (3+ 3N+ 3N^2) to both sides
N^3 + (N+1)^3 + (N+2)^3 + 9 (3+ 3N+ 3N^2) = 9*Q + 9 (3+ 3N+ 3N^2)
(N+1)^3 + (N+2)^3 + (N+3)^3 = 9(Q + 3+ 3N+ 3N^2)
(N+1)^3 + (N+2)^3 + (N+3)^3 = 9*P where P is an element of the natural numbers.

I was taught that it is bad form to start with anything other than the inductive assumption, here that: N^3 + (N+1)^3 + (N+2)^3 = 9*Q with Q an element of the natural numbers.

Yes I agree that your proof is valid, I'm just used to that format being considered "bad form." Obviously my only experience with this is my time in that class with that one professor, and I can see that your proof uses the inductive assumption in an appropriate way and that your proof is valid.

Any other opinions on the point made in this spoiler?

At school I was initially taught to do it your way Chris, but after a few years I've found that Diniz's way is generally easier for me. I very very rarely use your way now.

 

[vcuber13]

[n^3]+[n+1]^3+[n+2]^3
can be expanded as [n^3]+[(n^3)+(3n^2)+3n+1]+[(n^3)+(6n^2)+12n+8]
and simplified:
(3n^3)+(9n^2)+15n+9
the +9 will always be divisible by 9 if the rest is
so [(3n^3)+(9n^2)+15n]/9 must be an integer
or [((n^3)/3)+(n^2)+(5n/3)]
idk how to prove this but hopefully it helps a bit
im not sure if this is completely correct so if someone can varify this?

 

[cmhardw]

[n^3]+[n+1]^3+[n+2]^3
can be expanded as [n^3]+[(n^3)+(3n^2)+3n+1]+[(n^3)+(6n^2)+12n+8]
and simplified:
(3n^3)+(9n^2)+15n+9
the +9 will always be divisible by 9 if the rest is
so [(3n^3)+(9n^2)+15n]/9 must be an integer
or [((n^3)/3)+(n^2)+(5n/3)]
idk how to prove this but hopefully it helps a bit

Vcuber, this is the constructive proof. Although I think this proof is also nice, it's not what the original problem is asking for.

To continue with your proof you can do the following:

Spoiler

Look at what happens when n = 3k, when n=3k+1, and when n=3k+2 all of which assume that k is an element of the natural numbers

 

[vcuber13]

i havent learned the different ways to prove something, it would be how i go about doing it.
i see what you mean about if n=3k

 

[cmhardw]

i havent learned the different ways to prove something, it would be how i go about doing it.

Look at the Wikipedia articles for inductive proof, and constructive proof for more info.

i see what you mean about if n=3k

Spoiler

Do you see why we must also look at when n=3k+1, and when n=3k+2? Those steps are very important as well.

 

[vcuber13]

not really

 

[cmhardw]

not really

Spoiler

You want to know when [((n^3)/3)+(n^2)+(5n/3)] is an integer. Notice that the n^3 term, and the 5n term, are both being divided by 3. It makes sense then to consider what happens when n has no remainder when divided by 3, when n has a remainder of 1 when divided by 3, and when n has a remainder of 2 when divided by 3. Would you agree?

 

[BigSams]

Non-inductive proof for enrichment if anyone is interested.

Spoiler

\( (n-1)^{3}+n^{3}+(n+1)^{3} \)
\( n^{3}+(n-1+n-1)((n-1)^{2}-(n-1)(n+1)+(n+1)^{2}) \)
\( n^{3}+2n(n^{2}-2n+1-n^{2}+1+n^{2}+2n+1) \)
\( n^{3}+2n(n^{2}+3) \)
\( n^{3}+2n^{3}+6n \)
\( 3n^{3}+6n \)
\( 3n(n^{2}+2) \)
If \( n \) is a multiple of \( 3 \) then clearly the entire expression is a multiple of \( 9 \).
If not, \( n^{2}+2=(3m+1)^{2}+2 \) or \( n^{2}+2=(3m+2)^{2}+2 \).
\( (3m+1)^{2}+2=9m^{2}+6m+3 \) and \( (3m+2)^{2}+2=9m^{2}-12m+6 \), both of which are divisible by \( 3 \).
Therefore, the original expression is divisible by \( 9 \).

Also, join http://www.artofproblemsolving.com/Forum/index.php? AoPS math forums where most of the world's best math olympiad students lurk.

 

[Novriil]

I have another one. Even though I understood the last one I can't understand that.
Basically the same thing with this alg: 4^n + 15n - 1. n is a natural number and I must show that it is dividable by 9.
I got this far:
n=1
4+15-1=18=9*2

4^(n+1) + 15(n+1) - 1 = 4^(n+1) + 15n + 14
But now I can't figure out what to do with the ^(n+1)

So I tried wolframalpha and it couldn't do with it either. But I found out that
n | 1 | 2 | 3 | 4 | 5
15 n+4^(n+1)+14 | 45 | 108 | 315 | 1098 | 4185

Which means that it is true but I just have to find out how to show it by solving it with the same method.

 

[Diniz]

Spoiler

4^n + 15n - 1 = 9k
4^(n+1) + 60 n - 4 = 4*9k
4^(n+1) + 15n -1 + 45n - 3 = 4*9k
4^(n+1) + 15(n+1) -1 + 45n - 18 = 4*9k
4^(n+1) + 15(n+1) -1 = 4*9k + 18 - 45n = 9*(4k + 2 - 5n)

 

[uberCuber]

note that he didn't get from 4^n to 4^(n+1) by replacing n with n+1, he got there by multiplying the whole thing by 4