Induction
Related Words
Definition of Induction
Mathematical Induction is a method generally used to prove or establish that a given statement is true for all natural numbers.
More About Induction

It is a method to prove a proposition which is valid for infinitely many different
values of a variable.
Video Examples: Mathematical Induction
Example of Induction

Mathematical induction can be used to prove that 1 + 3 + 5 +  + (2n  1) = n^{2}
for all positive integers.
Let P_{n} be the statement 1 + 3 + 5 +  + (2n  1) = n^{2}.
P1 is true because (2(1)  1) = 1^{2}.
Assume that P_{k} is true, so that P_{k}: 1 + 3 + 5 +  + (2k  1) = k^{2}. [The Inductive Hypothesis.]
The next term on the left hand side would be [2(k + 1)  1] = (2k + 1). [Add (2k + 1) on both sides to P_{k}.]
1 + 3 + 5 +  + (2k  1) + (2k + 1) = k^{2} + (2k + 1) = (k + 1)^{2} = P_{k+1}
So, the equation is true for n = k + 1.
Therefore, P_{n} is true for all positive integers, by mathematical induction.
Solved Example on Induction
Ques: Using mathematical induction to prove that 1 + 5 + 9 +  + (4n  3) = n(2n  1) for all positive integers.
Solution:

Step 1: Let P_{n} be the statement 1 + 5 + 9 +  + (4n  3) = n (2n 
1).
Step 2: P1 is true because (4(1)  3) = 1(2(1)  1) [The Anchor.]
Step 3: Assume that P_{k} is true, so that P_{k}: 1 + 5 + 9 +  + (4k  3)
= k (2k  1) [The Inductive Hypothesis.]
Step 4: The next term on the lefthand side would be (4(k + 1)  3).
Step 5: 1 + 5 + 9 +  + (4k  3) + (4(k + 1)  3)
= k (2k  1) + (4(k + 1)  3)
Step 6: = 2k^{2}  k + 4k + 1
Step 7: = 2k^{2} + 3k + 1
Step 8: = (k + 1)^{2} + k (k + 1)
Step 9: = (k + 1) (2k + 1) [Factor.]
Step 10: = (k + 1) (2(k + 1)  1)
Step 11: = P_{k+1}
Step 12: So, the equation is true for n = k + 1.
Step 13: Therefore, Pk is true for all positive integers, by mathematical induction.
Translate :