Mathematical Induction
Mathematical induction is a valid method in mathematics, which can be used to derive
generalizations from examples of certain relationship patterns. Thus, mathematical induction is a
deductive method that is acceptable for proving the truth of a statement in mathematics.
The steps for proof using mathematical induction are as follows: Let p(n) be a
statement that will be proven to be true for all natural numbers n.
Step 1 : It is shown that p(1) is true.
Step 2: Assume that p(k) is true for a natural number k > 1, then by using the truth of p(k) it is
shown that p(k+1) is true.
Note that if step 1 and step 2 have been shown, a series of correct statements will be obtained,
namely p(1)⟹p(2) is correct, p(2)⟹p(3) is correct, p(3)⟹p( 4) correct and so on. So p(n) is
true for every natural number n.
Example 1
Prove that 1+3+5+ …+ ( 2 n−1 )=n2 always holds for every natural number n.
Solution:
For example p(n) : 1+3+5+ …+ ( 2 n−1 )=n2.
( i ) p ( 1 ) : 1=12. It is clear that p(1) is true.
(ii) Assume p(k) is true for any natural number k>1.
Meaning 1+3+5+ …+ ( 2 k−1 ) =k 2 is true ………….(*).
It is shown that p(k+1) : 1+3+5+ …+ ( 2 k−1 ) + ( 2 ( k +1 ) −1 )=( k+ 1 )2is true.
Based on (*) we get:
1+3+5+ …+ ( 2 k−1 ) + ( 2 ( k +1 ) −1 )=k + ( 2 ( k +1 )−1 )
2
2
¿ k +2 k +1
¿ ( k +1 )2
So it is proven that p(k+1) is true. So based on mathematical induction it can be concluded that
p ( n ) :1+ 3+5+…+ ( 2 n−1 )=n2 always applies (true) for every natural number n.
Mathematical induction is a valid method in mathematics, which can be used to derive
generalizations from examples of certain relationship patterns. Thus, mathematical induction is a
deductive method that is acceptable for proving the truth of a statement in mathematics.
The steps for proof using mathematical induction are as follows: Let p(n) be a
statement that will be proven to be true for all natural numbers n.
Step 1 : It is shown that p(1) is true.
Step 2: Assume that p(k) is true for a natural number k > 1, then by using the truth of p(k) it is
shown that p(k+1) is true.
Note that if step 1 and step 2 have been shown, a series of correct statements will be obtained,
namely p(1)⟹p(2) is correct, p(2)⟹p(3) is correct, p(3)⟹p( 4) correct and so on. So p(n) is
true for every natural number n.
Example 1
Prove that 1+3+5+ …+ ( 2 n−1 )=n2 always holds for every natural number n.
Solution:
For example p(n) : 1+3+5+ …+ ( 2 n−1 )=n2.
( i ) p ( 1 ) : 1=12. It is clear that p(1) is true.
(ii) Assume p(k) is true for any natural number k>1.
Meaning 1+3+5+ …+ ( 2 k−1 ) =k 2 is true ………….(*).
It is shown that p(k+1) : 1+3+5+ …+ ( 2 k−1 ) + ( 2 ( k +1 ) −1 )=( k+ 1 )2is true.
Based on (*) we get:
1+3+5+ …+ ( 2 k−1 ) + ( 2 ( k +1 ) −1 )=k + ( 2 ( k +1 )−1 )
2
2
¿ k +2 k +1
¿ ( k +1 )2
So it is proven that p(k+1) is true. So based on mathematical induction it can be concluded that
p ( n ) :1+ 3+5+…+ ( 2 n−1 )=n2 always applies (true) for every natural number n.
