I am trying to use induction. Have I applied it correctly / rigorously enough?

Prove that the sum of three consecutive cubes are divisible by $9$.

Base case: Let $n=0$. Then $0^3 + 1^3 + 2^3 \equiv 9 \equiv 0 \bmod 9$, and so this is true.

Inductive phase: Suppose $n^3 + (n+1)^3 + (n+2)^3 \equiv 0 \bmod 9$. We want to prove that $(n+1)^3 + (n+2)^3 + (n+3)^3 \equiv 0 \bmod 9$.

Subtracting one from the other, we get $(n+3)^3 - n^3 \equiv 0 \bmod 9$.

This expands to $9 n^2+27 n+27 \equiv 0 \bmod 9$.

Divide both sides and modulus by $9$:

$n^2+3n+3 \equiv 0 \bmod 1$, which is true because $1$ divides all positive integers.

Therefore this completes the proof.

Did I miss anything? Is my proof complete? What could I do better?

  • 3
    $\begingroup$ The main part of your proof is backwards. After stating the inductive hypothesis, you should start with $n^2+3n+3\equiv 0\pmod{1}$, and continue from there. You need to end with $(n+1)^3+(n+2)^3+(n+3)^3\equiv 0$, not start with it. $\endgroup$
    – vadim123
    Dec 29 '15 at 0:55
  • $\begingroup$ @vadim123 Does this ordering matter? I assumed that the goal was to state some sort of link from one case to the next (since the next three consecutive cubes are created by increasing $n$ by one), and then just show that this new assumption is true, too. $\endgroup$
    – AJJ
    Dec 29 '15 at 1:03
  • $\begingroup$ Using the idea "we want to prove this so we manipulate it and now we want to prove this" is awkward and misleading. Simply say "we need to show ($n + 3)^3 - n^3$ is divisble by three" and leave out "= mod 9" from your statements $\endgroup$
    – fleablood
    Dec 29 '15 at 1:05
  • $\begingroup$ There is another proof. For three consecutive numbers, one is $-1 \pmod 3$, another is $0 \pmod 3$, and finally one is $+1 \pmod 3$. These can come in any cyclic permutation order, but that is not important. So the sum of their cubes is congruent to $(-1)^3 + 0^3 + (+1)^3 = 0$ modulo $3$ as wanted. $\endgroup$ Dec 29 '15 at 1:39
  • $\begingroup$ @JeppeStigNielsen: The OP wanted modulo 9. If the OP believes the "Freshman's Dream" (i.e., that the Frobenius map is a homomorphism), then your suggestion leads directly to a proof. $\endgroup$
    – Snow
    Dec 29 '15 at 1:54

Yes, your proof is right in principle, but as @vadiim123 points out, it's backwards. To rigorously show something is true, you need to work forwards, but to get a sense for how to prove something, we often work backwards, which is what you have done.

First note that $9 \equiv 0 \pmod 9$ and $27 \equiv 0 \pmod 9$, so $9n^2+27n+27 \equiv 0 \pmod 9$. Using your work, $$(n+1)^3+(n+2)^3+(n+3)^3 = n^3 + (n+1)^3+(n+2)^3 + (9n^2+27n+27).$$ But $n^3 + (n+1)^3+(n+2)^3 \equiv 0 \pmod 9$ and $9n^2+27n+27 \equiv 0 \pmod 9$, so $$(n+1)^3+(n+2)^3+(n+3)^3 \equiv 0 \pmod 9.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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