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.