Proof Question: Mathematical Induction

1. Mar 22, 2008

Lococard

1. The problem statement, all variables and given/known data

Use mathematical induction to prove, for all integers $n >= 1$

$n^3 - n$ is divisible by 3

2. Relevant equations

Found equations with addition but no subtract involved.

3. The attempt at a solution

Another question suggests you expand the brackets, then insert the original theorem which prooves that the whole statement is true? (divisible by 3)

2. Mar 22, 2008

CompuChip

I don't know what you mean by
but that is indeed how induction works.

So, first you need to show that it is true for n = 1 (or if you want, for the slightly less trivial case n = 2). Then you assume you have proven that $n^3 - n$ is divisible by 3, and you try to show that $(n + 1)^3 - (n + 1)$ is divisible by 3 as well.
Then usually one stops writing down the proof, but the reasoning is: it has been shown that if it is true for n = 1, it will be true for n = 2. Also, it has been shown that if it is true for n = 2, it will be true for n = 3; et cetera. We have shown explicitly that it holds for n = 1. Therefore, it is true for n = 2, hence for n = 3, et cetera.

So first, check the statement for some low numbers (in principle, n = 1 would suffice, but you can check it for 2 and 3 if you want). Then assume it is true for n ("induction hypothesis") and try to prove it for n + 1. This can indeed by done by working out the brackets and trying to get $n^3 - n$ which is divisible by 3 by the induction hypothesis, plus something of which you can easily show that it is divisible by 3.

3. Mar 22, 2008

Lococard

Yeah, i did the sum for 1 to 3 and they were all divisible by 3.

I did attempt to break down $(n + 1)^3 - (n + 1)$ but wasnt sure how.

Is that the lowest form it can be displayed it?

Would i expand the brackets to (n+1)(n+1)(n+1) - (n - 1)

= n^3 - n - 1 +1

= n^3 - n

4. Mar 22, 2008

CompuChip

OK.

Not quite. First of all, you want to expand
$$(n + 1)^3 - (n \operatorname{\color{red}+} 1) = (n + 1)(n + 1)(n + 1) - n - 1$$
(note the sign in the first part, and the absence of brackets in the second part: ... - (n - 1) = ... - n + 1 is something different).
Then, you made an error in the expansion of the cubic:
$$(n + 1)^3 = (n + 1)(n + 1)(n + 1) = (n + 1)(n^2 + 2n + 1) = \cdots$$

5. Mar 22, 2008

tiny-tim

Welcome to PF!

Hi Lococard! Welcome to PF!

You must learn these expansions:

(n+1)(n+1) = n^2 + 2n + 1

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

(n+1)(n+1)(n+1)(n+1) = n^4 + 4n^3 + 6n^2 + 4n + 1​

So (n + 1)^3 - (n + 1) = ?

6. Mar 24, 2008

Lococard

n^3 + 3n^2 + 3n + 1 - (n + 1)?

How can i make this any smaller?

7. Mar 24, 2008

CompuChip

Regroup as follows
$$n^3 + 3n^2 + 3n + 1 - (n + 1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + (3n^2 + 3n + 1 - 1)$$
and use the induction hypothesis.

(You want to show that this is divisible by 3. What condition for a and b is sufficient to let a + b be divisible by 3?)

8. Mar 24, 2008

Lococard

That n is being multiplied by 3 on the RHS.

Do i have to have the +1 - 1?

Or can i just leave it as (n^3-n)+(3n^2+3n)?

9. Mar 24, 2008

tiny-tim

Hi Lococard!

This is proof by induction. So you can assume that n^3 - n is divisible by 3.

So … ?

oh, and yes, definitely add the +1 and -1 to get 0.

10. Mar 24, 2008

Lococard

So assuming that n^3-n is divisible by 3.

(n^3-n)+(3n^2+3n)

Knowing the first part is divisible by 3, the second part is divisible by 3 because n is being multiplied by 3, resulting in a number divisible by 3.

Solved?

11. Mar 24, 2008

CompuChip

Yep, now all you have to do is write it out readably

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook