Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
k does not equal k+1. –  anon Oct 14 '10 at 18:11
1  
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
    
@muad: Why do you say that? Because it has a trivial proof mod 9? –  Bill Dubuque Oct 14 '10 at 20:00
1  
@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
show 2 more comments

4 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
To the person who downvoted: if something is not clear then please ask questions and I'll be happy to explain. This technique is very useful for such problems so it is worth spending a little effort to understand it. –  Bill Dubuque Oct 14 '10 at 19:52
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.