• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Another math problem.

Novriil

Member
Joined
Mar 2, 2009
Messages
738
Location
Estonia
WCA
2009KRUU01
YouTube
Visit Channel
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

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
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

Member
Joined
Feb 27, 2010
Messages
294
Location
Brazil
WCA
2009DINI01
YouTube
Visit Channel
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.
 

Carrot

Member
Joined
Feb 9, 2009
Messages
1,910
WCA
2008ANDE02
YouTube
Visit Channel
hmmm...
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 :p), 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 :p
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
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.

(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

Member
Joined
Feb 27, 2010
Messages
294
Location
Brazil
WCA
2009DINI01
YouTube
Visit Channel
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

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
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.

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

Premium Member
Joined
Dec 22, 2008
Messages
2,504
Location
Guildford! UK!
WCA
2009SHEP01
YouTube
Visit Channel
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.

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

Member
Joined
Oct 14, 2009
Messages
2,477
Location
Near Toronto
WCA
2009METH01
YouTube
Visit Channel
[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?
 
Last edited:

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
[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:
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
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
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

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.
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
not really

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?
 
Last edited:

BigSams

Member
Joined
Jan 3, 2009
Messages
215
Non-inductive proof for enrichment if anyone is interested.
\( (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

Member
Joined
Mar 2, 2009
Messages
738
Location
Estonia
WCA
2009KRUU01
YouTube
Visit Channel
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

Member
Joined
Feb 27, 2010
Messages
294
Location
Brazil
WCA
2009DINI01
YouTube
Visit Channel
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)
 
Top