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.

What do you think about my first induction proof? Please mark/grade.


Theorem

The sum of the cubes of three consecutive natural numbers is a multiple of 9.

Proof

First, introducing a predicate $P$ over $\mathbb{N}$, we rephrase the theorem as follows. $$\forall n \in \mathbb{N}, P(n) \quad \text{where} \quad P(n) \, := \, n^3 + (n + 1)^3 + (n + 2)^3 \text{ is a multiple of 9}$$ We prove the theorem by induction on $n$.

Basis

Below, we show that we have $P(n)$ for $n = 0$. $$0^3 + 1^3 + 2^3 = 0 + 1 + 8 = 9 = 9 \cdot 1$$

Inductive step

Below, we show that for all $n \in \mathbb{N}$, $P(n) \Rightarrow P(n + 1)$.

Let $k \in \mathbb{N}$. We assume that $P(k)$ holds. In the following, we use this assumption to show that $P(k + 1)$ holds.

By the assumption, there is a $i \in \mathbb{N}$ such that $i \cdot 9 = k^3 + (k + 1)^3 + (k + 2)^3$. We use this fact in the following equivalent transformation. The transformation turns the sum of cubes in the first line, for which we need to show that it is a multiple of 9, into a product of 9 and another natural number.

$(k + 1)^3 + (k + 2)^3 + (k + 3)^3 \\ = (k + 1)^3 + (k + 2)^3 + k^3 + 9k^2 + 27k + 27 \\ = k^3 + (k + 1)^3 + (k + 2)^3 + 9k^2 + 27k + 27 \quad | \text{ using the induction hypothesis} \\ = 9i + 9k^2 + 27k + 27 \\ = 9 \cdot i + 9 \cdot k^2 + 9 \cdot 3k + 9 \cdot 3 \\ = 9 \cdot (i + k^2 + 3k + 3)$

We see that the above product has precisely two factors: 9 and another natural number. Thus the product is a multiple of 9. This completes the induction.

share|improve this question
6  
Looks fine to me! –  Braindead Mar 30 at 13:02
1  
someone should make something along the lines of markExchange instead of stackExchange. Marking instead of answering sounds fresh and good to me –  Nicholas Kyriakides Mar 31 at 3:59
1  
Looks good. You could maybe add a Halmos to the end, to be extra if not overly formal, $\square$. Check out math.stackexchange.com/questions/56606/… –  guydudebro Mar 31 at 4:42

3 Answers 3

I do not think that this is a real question but if you were my student i would give you an A.
It is all fine to me.

share|improve this answer

It's fine, here's a simpler proof without induction:

$n^3\equiv n\ (\text{mod }3)$, because it obviously holds for $n=-1,0,1$.

Therefore $3n^3\equiv3n\ (\text{mod 9})$ and $$(n-1)^3+n^3+(n+1)^3\equiv3n^3+6n\equiv0\ (\text{mod }9)$$

share|improve this answer
1  
i.e. $\ {\rm mod}\ 9\!:\ 3n^3\!+6n\equiv 3(n^3\!-n)\equiv 0\ $ by little Fermat. –  Bill Dubuque Mar 30 at 13:16

Formulation, base case, inductive hypothesis, inductive step, it all looks good. :)

One might also conclude with a clarifying statement about what has been done - that the hypothesis is true for all $n \in \Bbb N$.

share|improve this answer
1  
What do you think about the following statement? "By the basis, the inductive step, and the principle of induction; $P(n)$ is true for all $n \in \mathbb{N}$." –  DracoMalfoy Mar 30 at 13:51

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.