Induction
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) = n2 for all positive integers.
Let Pn be the statement 1 + 3 + 5 +  + (2n  1) = n2.
P1 is true because (2(1)  1) = 12.
Assume that Pk is true, so that Pk: 1 + 3 + 5 +  + (2k  1) = k2. [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 Pk.]
1 + 3 + 5 +  + (2k  1) + (2k + 1) = k2 + (2k + 1) = (k + 1)2 = Pk+1
So, the equation is true for n = k + 1.
Therefore, Pn 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 Pn 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 Pk is true, so that Pk: 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: = 2k2  k + 4k + 1
Step 7: = 2k2 + 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: = Pk+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 :