Thread: Modulus problem View Single Post
P: 418

## Modulus problem

I'd use the induction hypothesis to prove it.

Basically the induction hypothesis shows that if something works for n then it will work for n + 1, which then shows it will work for all values of n.

http://en.wikipedia.org/wiki/Mathematical_induction

That should explain it in more detail.

First of all you need a basis, to do this show that your hypothesis (that its divisible by 3 for all values of n) works for a small value of n - you can use either n = 0 or n = 1.

Then you substitute in n+1 for n in your first expression.

So in full your proof should look a bit like:

For any natural number n, n3 + 2n is divisible by 3.

Proof:

Basis: If n = 0, n3 + 2n = 03 + 2×0 = 0.
0 mod 3 = 0, therefore it is divisible by 3.

Induction: Assume that for an arbitrary natural number n, n3 + 2n is divisible by 3.

Induction Hypothesis: To prove this for n+1, first try to express ( n + 1 )3 + 2( n + 1 ) in terms of n3 + 2n and use the induction hypothesis.

( n + 1 )3 + 2( n + 1 ) = ( n3 + 3n2 + 3n + 1 ) + ( 2n + 2 )
= ( n3 + 2n ) + ( 3n2 + 3n + 3 )
= ( n3 + 2n ) + 3( n2 + n + 1 )

Therefore n3 + 2n is divisible by 3 by the induction hypothesis.

I'm not great with proofs so prehaps someone else could just check that.