Induction
Mathematical Induction Example 5 --- Divisible by 3
Problem: For any natural number n ,
n3 + 2n is divisible by 3.
Proof:
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.
( n + 1 )3 + 2( n + 1 )
= ( n3 + 3n2 + 3n + 1 ) + ( 2n + 2 )
= ( n3 + 2n ) + ( 3n2 + 3n + 3 )
= ( n3 + 2n ) + 3( n2 + n + 1 )
which is divisible by 3, because ( n3 + 2n )
is divisible by 3 by the induction hypothesis.
End of Proof.