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:


*

*Base case: $P(1) = (1) + (8) + (27) = 36, 36$ can be divided by $9$ so the base case is valid

*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!

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.
