# Another math problem.



## Novriil (Dec 2, 2010)

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 (Dec 2, 2010)

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 (Dec 2, 2010)

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 (Dec 2, 2010)

My question is what is the sum of this alg?

Also it would be good if there is an explanation.


----------



## Carrot (Dec 2, 2010)

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 (Dec 2, 2010)

3 consecutive numbers 

But I think that I understand by now.

E: I got it. Thanks Diniz!

Also thanks to Oscar and Chris!


----------



## cmhardw (Dec 2, 2010)

Diniz said:


> Spoiler
> 
> 
> 
> ...



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 (Dec 2, 2010)

cmhardw said:


> Spoiler
> 
> 
> 
> ...


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 (Dec 2, 2010)

Diniz said:


> 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 (Dec 2, 2010)

cmhardw said:


> 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.
> 
> ...


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 (Dec 2, 2010)

[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 (Dec 2, 2010)

vcuber13 said:


> [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
> ...


 
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 (Dec 2, 2010)

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 (Dec 2, 2010)

vcuber13 said:


> 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.



vcuber13 said:


> 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 (Dec 2, 2010)

not really


----------



## cmhardw (Dec 2, 2010)

vcuber13 said:


> 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 (Dec 2, 2010)

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 (Dec 2, 2010)

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 (Dec 2, 2010)

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 (Dec 2, 2010)

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


----------



## Novriil (Dec 2, 2010)

Diniz said:


> Spoiler
> 
> 
> 
> ...


 
can somebody explain since the bold part. This ise the first line I can't understand how he got it.


----------



## uberCuber (Dec 2, 2010)

Novriil said:


> can somebody explain since the bold part. This ise the first line I can't understand how he got it.


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

since the 4^(n+1) and the -1 + 45n are the same in both lines, take them out to make it clearer:

15n - 3
15(n+1) - 18

he added another 15 to the 15n, making it (n+1) * 15 instead of just n * 15, and then to keep it equal, subtracted 15 at the end, changing the - 3 into a - 18.


----------



## keemy (Dec 2, 2010)

slightly different inductive proof(well basically the same but a little shorter)

clearly true for \( n=0, 0+1+8=9 \)

assuming true up to n let \( n^3\equiv k \pmod 9, (n+1)^3 + (n+2)^3 \equiv l \pmod 9, k+l\equiv 0 \pmod 9 \)
so just nts \( n^3\equiv (n+3)^3 \pmod 9 \)
which is true since \( 9n^2+27n+27\equiv 0 \pmod 9 \)
so \( n^3 +(n+1)^3 + (n+2)^3 \equiv (n+1)^3 + (n+2)^3 + (n+3)^3 \equiv 0 \pmod 9 \)


----------



## cmhardw (Dec 3, 2010)

keemy said:


> slightly different inductive proof(well basically the same but a little shorter)
> 
> clearly true for \( n=0, 0+1+8=9 \)
> 
> ...


 
that's pretty


----------



## maggot (Dec 3, 2010)

oooh, very nice. deep @[email protected] i wonder if he put this on his homework, however, the teacher would know he got help LMAO! this is very nice though.
the line i really like in this is that 
it is clearly true for n=0, 0+1+8=9 . . .
i find this line to bring it together where sometimes 0 can be ambiguous. hence sometimes the need for proof of 0 exclusively to include 0 from the set of naturals. good job!


----------



## malcolm (Dec 3, 2010)

\( \frac{(n-1)^3 + n^3 + (n+1)^3}{9} = 2C^{n+1}_{3} + n \) which is obviously an integer. Actually any polynomial in \( x \) which takes integer values for integer values of \( x \) can be written as a sum of binomial coefficients in \( x \), you can prove this by induction on the degree


----------



## keemy (Dec 3, 2010)

malcolm said:


> \( \frac{(n-1)^3 + n^3 + (n+1)^3}{9} = 2C^{n+1}_{3} + n \) which is obviously an integer. Actually any polynomial in \( x \) which takes integer values for \( x \) can be written as a sum of binomial coefficients in \( x \), you can prove this by induction on the degree


(fixed mistake I think)

hmm I'm not sure how the later statement helps with the first(I mean unless there is a trick for finding sum of of binomial coefs). But either way that's pretty nice, I always like proofs that an expression must be an integer by showing it counts something.


----------



## malcolm (Dec 3, 2010)

Thanks, I've fixed the mistake. The first statement doesn't follow from the second, but the second does tell us that if the sum of three consecutive cubes is always divisible by 9, then we must be able to write \( \frac{(n-1)^3 + n^3 + (n+1)^3}{9} \) as a sum of binomial coefficients, since the polynomial \( \frac{(n-1)^3 + n^3 + (n+1)^3}{9} \) takes integer values whenever n is an integer. The second statement is just an interesting fact - try to prove it!


----------



## keemy (Dec 4, 2010)

I think I got a proof (to malcolm's statement)

lemma 1: given 2 polynomials \( P(x) \) and \( Q(x) \) with said properties \( P(x)\pm+Q(x) \) also has said properties.(duh)

lemma 2: if \( P(x) \) has said properties and \( deg(P(x))=l \) then the denominator of the coefficient of the \( x^l \) term is at most \( l! \)(and divides \( l! \)). This is slightly less obvious but if you notice that \( (x+1)(x+2)\ldots(x+l) \) is always divisible by \( l! \) and that there isn't any other polynomial that will have more factors or be divisible by more than \( l \) @ all \( x \) it becomes clearer.

so now a proof by induction

again the base is easy: if \( P(x) \) has said properties and \( deg(P(x))=0 \) then \( P(x)= A\tbinom k0 \) for some \( A\in\mathbb{Z} \)

now given that any polynomial \( P(x) \) with said properties and degree \( deg(P(x))=l \) can be written as the sum of some binomial coefficients.

well lets work backwards and assume we have a \( Q(x) \) with \( deg(Q(x))=l+1 \) and said properties now we know by lemma 2 that the denominator of the coefficient(lets call this \( a_{l+1} \)) of the \( x^{l+1} \) term is at most \( (l+1)! \) 

then lets take just take the binomial coefficient \( {x+l+1 \choose l+1} = \frac{(x+1)(x+2)\ldots(x+l+1)}{(l+1)!} \), set\( m=\frac{(l+1)!}{a_{l+1}} \)and make the polynomial \( R(x)=m{x+l+1 \choose l+1} \) noting that the coefficient of the \( x^{l+1} \) term is equal to \( a_{l+1} \) 

now just have \( Q(x)-R(x)=P(x) \) (by lemma 1 they all have said properties) and notice \( deg(P(x))=l \) 

so any \( Q(x) \) with said properties and degree \( l+1 \) can be written as \( P(x) + R(x)= Q(x) \) for some \( P(x) \) with said properties and degree \( l \) and some \( R(x)= B{x+l+1 \choose l+1} \) with \( B \in \mathbb{Z} \)


----------

