Proof Question: Mathematical Induction

[Lococard]

Homework Statement

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

$n^3 - n$ is divisible by 3

Homework Equations

Found equations with addition but no subtract involved.

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)

 

[CompuChip]

I don't know what you mean by

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

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.

 

[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

 

[CompuChip]

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

OK.

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

= n^3 - n - 1 +1

= n^3 - n

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

 

[tiny-tim]

Welcome to PF!

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

= n^3 - n - 1 +1

= n^3 - n

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) = ?

 

[Lococard]

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

How can i make this any smaller?

 

[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?)

 

[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)?

 

[tiny-tim]

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

How can i make this any smaller?

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.

 

[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?

 

[CompuChip]

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