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 freshen up for school in another month, and I'm struggling with the simplest of proofs!

Problem:

For any natural number n , n3 + 2n is divisible by 3. This makes sense

Proof:

Basis Step: If n = 0, then n3 + 2n = 03 + 2×0 = 0. So it is divisible by 3.

Induction: Assume that for an arbitrary natural number n, n3 + 2n is divisible by 3.

Induction Hypothesis: To prove this for n+1, first try to express ( n + 1 )3 + 2( n + 1 ) in terms of n3 + 2n and use the induction hypothesis. Got it

  • ( n + 1 )3 + 2( n + 1 ) = ( n3 + 3n2 + 3n + 1 ) + ( 2n + 2 ) Just some simplifying
  • = ( n3 + 2n ) + ( 3n2 + 3n + 3 ) simplifying and regrouping
  • = ( n3 + 2n ) + 3( n2 + n + 1 ) factored out the 3

which is divisible by 3, because ( n3 + 2n ) is divisible by 3 by the induction hypothesis. What?

Can someone explain that last part? I don't see how you can claim ( n3 + 2n ) + 3( n2 + n + 1 ) is divisible by 3.

share|improve this question
    
Let n^3+2n = P(n). We know that P(0) is divisible by 3. The inductive step shows that P(n+1) = P(n) + (something divisible by 3). So if P(0) is divisible by 3, then P(1) is divisible by 3, and then... –  Qiaochu Yuan Jul 30 '10 at 2:12
4  
I think part of the confusion to beginners with induction proofs arises from using the same letter n both in the statement and the induction step... it may be clearer if it said that P(k) => P(k+1), so that it doesn't seem we're trying to prove P(n) by assuming P(n) (in the induction step). –  ShreevatsaR Jul 30 '10 at 2:18
1  
@Tom Stephens There's nothing degenerate about 0. If you don't pick 0 you do more work (base case 1 is harder to prove) and prove less (you haven't proved it for 0). –  starblue Jul 30 '10 at 5:40
1  
@starblue: I agree with you, but can also rephrase it as: 0 is degenerate, which is great! It lets the proof involve less work. –  ShreevatsaR Jul 30 '10 at 6:29
3  
The following is not an answer to "do it my induction." But $n^2+2$ has the same remainder on division by $3$ as $n^2-1$. So $n(n^2+2)$ has the same remainder on division by $3$ as $(n-1)(n)(n+1)$. But this is the product of $3$ consecutive numbers, so, as mentioned by @Fëanor, it is divisible by $3$. –  André Nicolas Feb 21 '12 at 0:37

11 Answers 11

up vote 11 down vote accepted

In the inductive hypothesis, you assumed that $n^3 + 2n$ was divisible by 3 for some $n$, and now you're proving the same for $n+1$. It's like knocking down dominoes: if you can prove that the first domino falls over (base case) and each domino knocks over the next (inductive step), then that means that all of the dominoes get knocked down eventually.

You know that $(n^3 + 2n) + 3(n^2 + n + 1)$ is divisible by 3 because $n^3 + 2n$ is (because of the inductive hypothesis) and $3(n^2 + n + 1)$ is (because it's 3 times an integer). So, their sum is as well.

share|improve this answer
1  
That last paragraph cleared it up for me. Thank you! –  Matt Jul 30 '10 at 2:37

In a proof by induction, we try to prove that a statement is true for all integers n. To do this, we first check the base case, which is the "Basic Step" above. Then, we have the induction hypothesis, where we assume that the statement is true for an integer k. Using this fact, we prove that the statement is also true for the next integer k+1. This produces a bootstrapping ladder where we use the base case (n=1) to show that the statement is true for n=2 via the inductive hypothesis, and then for n=3, etc, off to infinity; this shows that the statement is true for all integers n.

Here, we claimed that ( n3 + 2n ) + 3( n2 + n + 1 ) is divisible by 3 because this was the inductive hypothesis; we were using this to show that ( (n+1)3 + 2(n+1) ) + 3( (n+1)2 + (n+1) + 1 ).

share|improve this answer

Why don't you just test the validity of this using modular arithmetic? I.e. take n congruent to 1 mod 3 and we easily get 3=0. If you try n congruent to 2 mod 3, you get 8+4 =12 =0, so you're done. No ugly inductions (although this particular case is not so dirty).

A useful idea when thinking of induction is to think of dominos. If you know something is true for one fixed tile and if you know that it being true for one tile means that it's true for the neighbour on the right, then it's like knocking one over knocks them all over.

share|improve this answer
    
I too would have proved this with modular arithmetic, but maybe the exercise explicitly asked a proof by induction. –  mau Jul 30 '10 at 5:35
1  
The sad thing about learning induction in class is all the examples tend to be horribly contrived, which takes a lot of the fun out of it. –  anon Jul 30 '10 at 8:00
1  
that's probably because good examples are not simple to state. –  mau Jul 30 '10 at 9:29
    
Besides, using modular arithmetic shows that the statement hold for all $n\in{\Bbb Z}$ which requires an extra argument (albeit very easy) when using induction. –  Andrea Mori Feb 28 '11 at 17:59

Presumably you're only looking for a way to understand the induction problem, but you can note that $n^3+2n = n^3 - 3n^2 + 2n - 3n^2 = (n-2)(n-1)(n) + 3n^2$. Since any three consecutive integers has a multiple of three, we're adding two multiples of three and so get another multiple of 3.

share|improve this answer
1  
While this of course works, it is the kind of black magic that makes people think that you need to be Ramanujan reincarnated to do maths... «You can note that» can be a very discouraging way of starting an explanation! :) –  Mariano Suárez-Alvarez Jul 30 '10 at 16:13
    
Indeed. If you do enough problems like this, then at least tricks like this become second nature. –  Ben Alpert Jul 30 '10 at 16:44

Alternatively, $f:{\mathbb N} \rightarrow {\mathbb Z}/3{\mathbb Z} \;$ is constant since $f(n+1) = f(n)$, so $f(n) = f(0) = 0$. This reduces the induction to a trivial lemma: $f(n)$ is constant if $f(n+1) = f(n)$ for all $n\in \mathbb N$, a trivial telescopy.

share|improve this answer

$$ \begin{align} n^3+2n &= n(n^2+2) \\ &= n(n^2−1+3)\\ &= n((n^2−1^2)+3)\\ &= n((n−1)(n+1)+3)\\ &= n(n−1)(n+1)+3n \end{align} $$

The key is to identify the factor $(n^2-1^2)=(n-1)(n+1)$. Looking at the result you can tell that it must be divisable by 3 because one of $n$, $(n-1)$ or $(n+1)$ is a multiple of 3. Ben Albert gives a similar solution but I believe $3n^2$ should be $3n$ instead.

share|improve this answer

$$n^3+2n=n(n^2+2)$$

If $n$ is divisible by $3$, then obviously, so is $n^3+2n$ because you can factor out $n$.

If $n$ is not divisible by $3$, it is sufficient to show that $n^2+2$ is divisible by 3. Now, if $n$ is not divisible by $3$, $n=3k+1$ or $n=3k+2$ for some integer $k$. Plug that into $n^2+2$ and you'll get $9k^2+6k+3$ and $9k^2+6k+6$ respectively. Both of which are divisible by 3.

share|improve this answer

Take base cases 1, 2, and 3, and then deduce case $n+3$ from case $n$.

share|improve this answer
    
Cute. But if someone doesn't know how to do the problem by more pedestrian methods, it's a bit much to expect them to think of things like this. –  Michael Hardy Feb 20 '12 at 23:20
    
If someone can't walk and do math at the same time, then they have more serious issues! –  The Chaz 2.0 Feb 20 '12 at 23:23
    
@Michael, what's your point? The question was, "How can I prove...," not, "What proof would you expect me to think of...," so I gave a way to prove. Of course, now that adil has seen this way to do it, now I would expect adil to think of something like this next time. –  Gerry Myerson Feb 21 '12 at 1:07

Given the $n$th case, you want to consider the $(n+1)$th case, which involves the number $(n+1)^3 + 2(n+1)$. If you know that $n^3+2n$ is divisible by $3$, you can prove $(n+1)^3 + 2(n+1)$ is divisible by $3$ if you can show the difference between the two is divisible by $3$. So find the difference, and then simplify it, and then consider how to prove it's divisible by $3$.

share|improve this answer

The driving force behind induction is that you show that a base case (when $n = 1$, for example). Then you show that the hypothesis being true at some $k$ implies that it holds at $k+1$. Then, since you have verified the hypothesis at $n = 1$, you have it at $n = 2$. Then, since it holds at $n = 2$, it holds at $n = 3$, and so on. Note that the domain over which the hypothesis holds should be defined in the hypothesis itself.

Now, for your specific case, let's see how this works.

First, for the base case ($n = 1$), we see the following:

$$1^3 + 2 \cdot 1 = 3.$$

That is clearly divisible by $3$, so we have our base case.

Now assume that for all $k \geq 1$, $k^3 + 2k$ is divisible by $3$.

Then for $n = k + 1$, we have:

$$(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = k^3 + 3k^2 + 5k + 3$$

The $3k^2 + 3$ portion is clearly divisible by $3$, so we need only show that $k^3 + 5k$ is divisible by $3$. From the assumption above, we know that $k^3 + 2k = 3m$ for some positive integer $m$. Then,

$$k^3 + 5k = k^3 + 2k + 3k = 3m + 3k = 3(m + k),$$

so the hypothesis holds at $n = k+1$.

Thus, we have for all $n \geq 1$, $n^3 + 2n$ is divisible by $3$.

As the others have suggested, there are certainly other ways of showing the $(k+1)$th case, but hopefully this overall form helps you see how mathematical induction works.

share|improve this answer
    
thanks very much –  adil Feb 20 '12 at 23:36

Hint: if $\:f(n+1) = f(n) + 3\: g(n)\:$ for $\:g(n)\in \mathbb Z,\:$ then $\:3$ divides $f(n)\ \Rightarrow\ 3$ divides $f(n+1)$.

See here for how to view this as a special case of the more general method of telescopy.

share|improve this answer

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.