Question in validity of proof that $9|n^3 + (n+1)^3 + (n+2)^3$

Question

I wanted to prove that 9 divides the cubes of 3 consecutive integers. I represented this as:

For $n \in \mathbb{Z}, 9|n^3 + (n+1)^3 + (n+2)^3$

By the definition of divisibility, if $9|n^3 + (n+1)^3 + (n+2)^3$ then there would exist an integer, let's say m such that $n^3 + (n+1)^3 + (n+2)^3 = 9m$

$$n^3 + (n+1)^3 + (n+2)^3 = 3n^3 + 9n^2 + 15n + 9$$ $$= (9n+9) + (3n^3 +5n)$$ $$= 9(n^2 + 1) + 3(n^3 + 5n)$$ At this point I noticed that if I could prove $3|n^3 + 5n \rightarrow n^3 + 5n = 3q$, for some $q \in \mathbb{Z}$ and I'd have essentially completed the proof.

I proved this by induction, I will omit the trivial base case $n=1$. I assumed that for an arbitrary intger $k$, that $3|k^3 + 5k \rightarrow k^3 + 5k = 3p$ for $p \in \mathbb{Z}$. I sought to prove that for an arbitrary integer $k+1$, that $3|(k+1)^3 + 5(k+1)$.

$$(k+1)^3 +5(k+1) = k^3 + 3k^2 + 8k + 6$$ $$= (k^3 + 5k) + (3k^2 + 6)$$ $$= 3p + 3k^2 + 6$$ $$= 3(p+ k^2 + 2)$$ $$= 3q$$ Where by multiplicative closure of the integers, $q=p+k^2+2$.

So by induction $3|k^3 + 5k \rightarrow k^3+5k = 3q$ where $q$ is some integer.

Now we can finish where we left off.

$$9(n^2+1)+3(k^3+5k)$$ $$= 9(n^2+1) + 3(3q)$$ $$= 9(n^2 + 1 + q)$$

Since $n^2, 1, q \in \mathbb{Z}, n^2 + 1 + q \in \mathbb{Z}$ by additive closure. We denote the integer sum $n^2 + 1 + q$ as $m$ so we now have:

$$n^3 + (n+1)^3 + (n+2)^3 =9m$$ where $m \in \mathbb{Z}$, so I've rearranged the formula to show that the sum of the cubes of 3 consecutive integers is divisible by 9 by the definition of divisibility.

My question is, for most other proofs like this, I've had to use induction before. Am I able to rigorously say that this will hold $\forall n \in \mathbb{Z}$ even though I did not prove it with induction? To me, it would seem the case, just operating off the divisibility definition, but I am not sure if this actually proves that 9 divides that sum for all $n$, or if I just did some algebra that appears, to show that, but wouldn't hold up under scrutiny?

I am sorry if this is considered a "duplicate", I am just not sure if this is an acceptable way to prove the claim, without induction.

Answer 1

It should be fine that you have split out part of it to be proven by induction, while the other part is true algebraically without induction.

Another way to see what Will and John mentioned is that with three consecutive integers, you will always have one of each remainder (divide by 3) from 0, 1, and 2. Say you are given consecutive integers $a$, $b+1$, and $c+2$, where $3|a,b,c$ and $a$, $b$, or $c$ may be equal to one another. You can derive after cubing and expanding the binomials that the sum divides 9, algebraically.

Answer 2

In general, induction is a great tool, but when considering divisibility problems, looking at prime factors (i.e. 3 instead of 9) and using casework on the remainder (which could be simplified with modular arithmetic) often works better.

Here’s a quick way without induction nor modular arithmetic.

Letting $n$ be the middle number, we have that: $$(n-1)^3+ n^3+ (n+1)^3 \equiv 3n(n^2+2) \ \mod 9$$

Thus, it suffices to show that $3$ divides $n(n^2+2)$.

Now we can do casework on the remainder of $n$ when dividing by 3. If $n=3a$, then $3$ divides $n=3a$. If $n=3a+1$, then 3 divides $n^2+2=9a^2+6a+3$. If $n=3a+2$, then 3 divides $n^2+2=9a^2+12a+6$.

Thus, 3 either divides $n$ or $n^2+2$, so $3$ divides $n(n^2+2)$, so 9 divides $3n(n^2+2)$

Answer 3

Basically you have taken it upon yourself to prove $X$ and you decided to do it in two steps.

Step 1: By pure algebra you proved that $X$ is equivalent to $Y$.

And Step 2: By induction $Y$ is true.

Now you are worrying that because you proved the two steps by different methods, it can't be valid unless they were both proven by the same method.

Well... of course it's valid. True is true, and a proof is a proof so you can always break a proof into steps and you can prove each step individual it absolutely doesn't matter for one step what method you used on the other.

.... unless there is some "induction only club" you want to join and the members will blackball you if any step doesn't use induction.

=====

All the need for induction on this proof is pretty minimal.

To prove $n^3 + 5n$ is divisible by $3$ we can let $n=3k + j$ where $j=0, 1,$ or $2$. Then $n^3 + 5n = (3k+j)^3 + 5(3k +j) =27k^3+ 27k^2j + 9kj^2 + j^3 + 15n+5j$ and that divisible by $3$ if and only if $j^3 + 5j$ is.

Which is exactly were we started but we know $j = 0,1,2$ so we just check each one. $0^3+5\cdot 0 = 0; 1^3 + 5\cdot 1 = 6$ and $2^3 + 5\cdot 2 = 18$.

That's it. No induction anywhere so you don't have to worry about saying it wasn't all induction (which you wouldn't have had to worry about anyway.)

====

And just a tip. Instead of using "three consecutive numbers are $n, n+1, n+2$" you can say "three consecutive numbers are $n-1, n, n+1$ and your calculations are much more contained.

$(n-1)^3 + n^3 + (n+1)^3 = 3n^3 + 6n $ so we just need show $n^3 +2n$ is divisible by $3$. If I write that $n= 3k + j$ where $j = -1, 0, 1$ things go quicker too.

$(3k\pm 1,0)^3 + 2(3k\pm 1,0)=$

$27k^3 + 27k^2\cdot(\pm 1,0) + 9k\cdot (\pm 1, 0)^2 + (\pm 1, 0)^3 + 6k\pm 2,0=$

This is divisible by $3$ if and only if $(\pm 1, 0)^3 \pm 2,0$ is.

$(-1)^3 -2 = -3$ and $0^3 + 0 =0$ and $1^3 + 2 = 3$ and we are done.