# proofs

• Mar 1st 2010, 05:38 PM
mathh18
proofs
!!
• Mar 1st 2010, 07:05 PM
Drexel28
Quote:

Originally Posted by mathh18
I'm working on proof by induction and am not quite understanding it. It seems simple but its not clicking.
Here are two i'm stuck on:
Prove that for each integer n is greater than or equal to 1, (n^3)-n is divisible by 3

Prove that all integers for n greater than or equal to 2, 2^(3n)-1 is not prime.
for this i'm guessing i would need "Case 1" and "Case 2" for odd and evens?

I'm completely lost and frustrated and the books examples aren't helping. Any tips on either of these proofs would help so much! thanks!!

What kind of math do you know?

Easy way, merely note that if $\displaystyle n\equiv 0\text{ mod }3$ this is trivial since $\displaystyle n^3-n^\equiv 0-0=0\text{ mod }3\implies n^3\equiv n\text{ mod }3$. Otherwise, $\displaystyle (n,3)=1\implies n^3\equiv n\text{ mod }3$ since $\displaystyle \phi(3)=2$
• Mar 2nd 2010, 03:54 AM
Quote:

Originally Posted by mathh18
I'm working on proof by induction and am not quite understanding it. It seems simple but its not clicking.
Here are two i'm stuck on:
Prove that for each integer n is greater than or equal to 1, (n^3)-n is divisible by 3

I'm completely lost and frustrated and the books examples aren't helping. Any tips on either of these proofs would help so much! thanks!!

Hi mathh18,

to use proof by induction for the 1st one,

F(k)

$\displaystyle k^3-k$

is divisible by 3 ?

F(k+1)

$\displaystyle (k+1)^3-(k+1)$

is divisible by 3 ?

$\displaystyle (k+1)^3-(k+1)=(k+1)[(k+1)^2-1]=(k+1)(k^2+2k)$

$\displaystyle =k^3+2k^2+k^2+2k$

Express this using F(k)

$\displaystyle k^3+2k^2+k^2+2k=\left(k^3-k\right)+3k^2+3k=\left(k^3-k\right)+3\left(k^2+k\right)$

If F(k) is true, then F(k+1) is certainly true as the 2nd term is divisible by 3.

Therefore F(1) true causes F(2) to be true, causing F(3) to be true, causing ......

Hence you now only need test n=1.

$\displaystyle 1^3-1=0,\ 0(3)=0\ \Rightarrow\ 0=\frac{0}{3}$

true