I am asked to prove, using mathematical induction, that \[3 | (n^3 - n) for all positive integers. I am having a difficult time relating the basis step to the induction step when a operator other than equivalence is used. How would I approach this problem most effectively.

Question

anonymous · Answer

Sorry my equation didn't' come out in the wash.

$$3 | (n^3 -n )$$

phi · Answer

what's the basis step?

mr.math · Answer

Write $n^3-n=3k$ for some integer $k$. This would make it easier.

anonymous · Answer

@phi  would assume the basis step is to determine that the formula is true for integer k.

$$3 | (1^3 - 1) \ 3 | ( 1 - 1 ) \ 3 | 0$$

phi · Answer

now assume the statement is true for n.  Show it is true for N+1

n^3-n = n(n^2-1)= (n-1)n(n+1)

replace n with N+1
N(N+1)(N+2)
N(N+1)( (N-1) + 3)
can you finish?

anonymous · Answer

I see your logic @Mr.Math! I understand that finding equivlency is nesscary to proving the formula. I am just unsuring of my footing when making assumptions or introducing forumlas.

mr.math · Answer

Your fist step is right, you found that the statement is valid for $n=1$, Now do as phi said. Assume it's true for $n=m$, then show that this assumption implies that it's also true for $n=m+1$.

mr.math · Answer

The factorization that phi did above is the key to the problem.

anonymous · Answer

I can easily grasp the induction step when I am trying to simplify a Left Hand Side to a Right Hand Side. This question has thrown me for a loop not having that option. I am unsure what I am supposed to make my induction step equivlent to.

phi · Answer

You have to show
3 | (n^3 - n) 

You first prove this is true for a base case, n=1 

You then assume it is true for some n.  Now show it is true for n+1.
plug (n+1) into the formula and rewrite (see previous post) as

n(n+1)( (n-1) + 3)  =  (n-1)n(n+1)  + 3n(n+1)
= (n^3-n)  + 3n(n+1)
3 divides evenly into the first term by hypothesis.  (We assumed the statement is true for n)
The 2nd term is evenly divisible by 3 because it has 3 as a factor
therefore the entire expression is divisible by 3.
We conclude that if the statement is true for n, it will be true for n+1.  But having proved it is true for n=1, we conclude it is true for n=2, and then n=3, and so on.

anonymous · Answer

Alright! I can see the connection now. All of my examples dealt with sumations where I could find an equivlence to prove ideas. Maybe this was a poor way of introducing the idea becuase I felt bound by this idea that I had to find equivlence when you provided a clear example that is any approptriate condition can used. 

I really appreciate your help and clarification.