I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs!
For any natural number n , n3 + 2n is divisible by 3. This makes sense
Basis Step: If n = 0, then n3 + 2n = 03 + 2×0 = 0. So 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. Got it
- ( n + 1 )3 + 2( n + 1 ) = ( n3 + 3n2 + 3n + 1 ) + ( 2n + 2 ) Just some simplifying
- = ( n3 + 2n ) + ( 3n2 + 3n + 3 ) simplifying and regrouping
- = ( n3 + 2n ) + 3( n2 + n + 1 ) factored out the 3
which is divisible by 3, because ( n3 + 2n ) is divisible by 3 by the induction hypothesis. What?
Can someone explain that last part? I don't see how you can claim ( n3 + 2n ) + 3( n2 + n + 1 ) is divisible by 3.