Simple Proof by induction: “9 divides $n^3 + (n+1)^3 + (n+2)^3$”

I'm trying to prove using induction that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have:

1. Base case: P(1) = (1) + (8) + (27) = 36, 36 can be divided by 9 so the base case is valid
2. Inductive step: let p(n) be the statement 9 divides $n^3 + (n+1)^3 + (n+2)^3$ Assume p(k) is true, so 9 divides $k^3 + (k+1)^3 + (k+2)^3$

And this is where I'm stuck. I'm not sure how to demonstrate that 9 divides P(n) when n = k+1. If someone could step me in the right direction that would be awesome. Thanks!

-
k does not equal k+1. – anon Oct 14 '10 at 18:11
In the last paragraph, “when k = k+1” should be “when n = k+1.” – Tsuyoshi Ito Oct 14 '10 at 18:12
N.B. This question has absolutely nothing to do with induction. – anon Oct 14 '10 at 19:31
@Bill Dubuque, no. The question is about proving $P(k)\Rightarrow P(k+1)$. It happens to come from part of an induction proof but the question is not about any aspect of induction. – anon Oct 14 '10 at 20:02
But induction questions often focus on the only nontrivial step. – Bill Dubuque Oct 14 '10 at 23:24

You want to prove that if $9\mid[n^3+(n+1)^3+(n+2)^3]$ then $9\mid[(n+1)^3+(n+2)^3+(n+3)^3]$. This boils down to proving that $9\mid[(n+3)^3-n^3]$.

-

Here's an all-purpose technique for proving your kind of induction problems.

You are trying to prove using induction that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ whenever n is a non-negative integer.

You have already demonstrated the base case, so here's the inductive step.

Assuming it is true for n, is it also true for n+1?

That means to say: is $(n+1)^3 + (n+2)^3 + (n+3)^3$ divisible by 9?

Well, if $[(n+1)^3 + (n+2)^3 + (n+3)^3] -[n^3 + (n+1)^3 + (n+2)^3]$ (the difference of the inductive step and the formula) is divisible by 9, so is $(n+1)^3 + (n+2)^3 + (n+3)^3$.

Why? A bit of modular arithmetic here. If (x mod 9) - (0 mod 9) = (0 mod 9) then x = (0 mod 9). This means that if the difference is divisible by 9, and one of the numbers in our subtraction is divisible by 9, the other number must be too.

I'm not going to do the algebra on here, but you can verify that $[(n+1)^3 + (n+2)^3 + (n+3)^3] -[n^3 + (n+1)^3 + (n+2)^3]$ simplifies into $9n^2+27n+27$ which you can rewrite as $9(n^2+3n+3)$. Hence the difference is divisible by 9, and so is our inductive step.

Q.E.D.

-

HINT $\ \$ If $\rm\ 9\:|\:P(n)\$ then $\rm \ 9\:|\:P(n+1)\ \iff\ 9\ | \ P(n+1)-P(n)\ =\ (n+3)^3 - n^3$

REMARK $\$ This reduction can be viewed as arising from rewriting $\rm\: P(n)\:$ as a telescoping series

$$\rm P(n) = (P(n)-P(n-1)) + (P(n-1)-P(n-2)) +\: \cdots\: + (P(1)-P(0))+\ P(0)$$

Thus $\ 9\$ divides $\rm\ P(n)\$ if it divides all RHS terms,$\$ i.e.$\$ all the differences $\rm \ P(i+1)-P(i)\$ and $\rm\ P(0)$. Since $\rm\: P\:$ is a polynomial, its difference has lower degree than $\rm\: P\:$, so the problem reduces to a simpler one.

Such telescopic transformations often simplify inductive proofs. See here for similar multiplicative telescopy.

Note: if you continue to iterate the above reduction then it amounts to showing that the coefficients $\rm \Delta^k P(0)$ in Newton's forward difference formula are all divisible by 9. Indeed one has

$$\rm P(n)\ =\ 9 + 27\ n + 36\ \binom{n}2 + 18\ \binom{n}3$$

Equivalently, one could simply check that four consecutive values of $\rm\:P\:$ are multiples of 9. Analogous remarks hold true for any $\rm\:P(n)\:$ that satisfies a monic linear recurrence with polynomial coefficients (or, much more generally, for proving identities of multivariate holonomic functions). While this viewpoint is overkill here, it is essential when working with nontrivial examples.

-

It's clearer if you write it instead in a symmetric fashion: $(n-1)^3+n^3+(n+1)^3$, which simplifies to $3n(n^2+2)$. If $n$ is a multiple of $3$ then this is a multiple of $9$. Otherwise, $n$ leaves a remainder of $\pm1$ when divided by $3$ and so $n^2+2$ is multiple of $3$, which implies that $3n(n^2+2)$ is a multiple of $9$. It's not a proof by induction, though.

-
The expression you start with is not the same as the OP's expression, although it is congruent mod 3. It's easy to give a modular proof, e.g. (3n-1)^3 + (3n)^3 + (3n+1)^3 = -1 + 0 + 1 (mod 9), but the OP seeks an inductive proof. – Bill Dubuque Oct 16 '10 at 19:58
lhf's expression is got by replacing $n$ by $n-1$ so it gives rise to an equivalent problem. – Robin Chapman Oct 16 '10 at 20:08

$P(k)+Q(k) = P(k+1)$. You need to find Q(k), and show that $9\mid Q(k)$

-