Proof Question: Mathematical Induction

  • Mathematica
  • Thread starter Lococard
  • Start date
25
0

Main Question or Discussion Point

1. Homework Statement

Use mathematical induction to prove, for all integers [itex]n >= 1[/itex]

[itex]n^3 - n[/itex] is divisible by 3

2. Homework 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)
 

Answers and Replies

CompuChip
Science Advisor
Homework Helper
4,284
47
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 [itex]n^3 - n[/itex] is divisible by 3, and you try to show that [itex](n + 1)^3 - (n + 1)[/itex] 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 [itex]n^3 - n[/itex] which is divisible by 3 by the induction hypothesis, plus something of which you can easily show that it is divisible by 3.
 
25
0
Yeah, i did the sum for 1 to 3 and they were all divisible by 3.


I did attempt to break down [itex](n + 1)^3 - (n + 1)[/itex] 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
Science Advisor
Homework Helper
4,284
47
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
[tex](n + 1)^3 - (n \operatorname{\color{red}+} 1) = (n + 1)(n + 1)(n + 1) - n - 1[/tex]
(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:
[tex](n + 1)^3 = (n + 1)(n + 1)(n + 1) = (n + 1)(n^2 + 2n + 1) = \cdots [/tex]
 
tiny-tim
Science Advisor
Homework Helper
25,789
249
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! :smile:

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) = ? :smile:
 
25
0
n^3 + 3n^2 + 3n + 1 - (n + 1)?

How can i make this any smaller?
 
CompuChip
Science Advisor
Homework Helper
4,284
47
Regroup as follows
[tex]n^3 + 3n^2 + 3n + 1 - (n + 1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + (3n^2 + 3n + 1 - 1)[/tex]
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?)
 
25
0
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
Science Advisor
Homework Helper
25,789
249
n^3 + 3n^2 + 3n + 1 - (n + 1)?

How can i make this any smaller?
Hi Lococard! :smile:

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

So … ? :smile:

oh, and yes, definitely add the +1 and -1 to get 0.
 
25
0
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
Science Advisor
Homework Helper
4,284
47
Yep, now all you have to do is write it out readably :smile:
 

Related Threads for: Proof Question: Mathematical Induction

Replies
41
Views
12K
Replies
5
Views
7K
Replies
17
Views
5K
Replies
3
Views
29K
Replies
14
Views
4K
Replies
4
Views
2K
Replies
0
Views
1K
Replies
1
Views
5K
Top