What is Induction in math?
Mathematical induction is a special method or technique to prove the statements given in consideration. Generally, it is used to prove the statements of the set of natural numbers.
Principle of Mathematical Induction:
Mathematical induction is used to prove that the given statement is true or not. It uses 2 steps to prove it.
First Principle of Mathematical Induction:
Base Case: The given statement is correct for first natural number that is, for n = 1, p (1) is true.
Inductive Step: If the given statement is true for any natural number like n = k then it will be correct for n = k + 1 also that is, if p (k) is true then p (k + 1) will also be true.
The first principle of mathematical induction says that if both the above steps are proven then p (n) is true for all natural numbers.
Second Principle of Mathematical Induction: It is more powerful than the first principle. It is sometimes called as strong induction. It doesn’t need a base case in special case otherwise it may require to show with more than one base case. In the recursive step to prove that k + 1 is true, first we need to prove that the statement is correct for all the numbers less than k + 1 also.
First Principle of Mathematical Induction:
The mathematical induction can be proved in four steps:
1.Step: Show p (1) is true. Let n = 1 and solve.
2.Step: (Induction Hypothesis) Assume p (k) is true. Let n = k and solve.
3.step: (Induction) Show if p (k) is true then p (k + 1) is also true. Let n = k + 1 and solve.
Write the proof that p (n) is true.
Example: Prove that for any natural number n, the sum of n natural numbers is \(\frac{n(n+1)}{2}\)
Solution: Given the statement which we need to prove
\(1+2+3+……………..+n=\frac{n(n+1)}{2}\)Step 1: Base Step
Show the statement holds for n = 1
\(1=\frac{1(1+1)}{2}=\frac{2}{2}=1\)As the LHS = RHS
This shows that p (1) is true.
Step 2: Inductive Step
Show if p (k) is right then p (k + 1) is also right.
Assume p (k) is right
Let n = k
\(1+2+3+……………+k=\frac{k(k+1)}{2}\)Now we have to prove that it is true for the next number also i.e. k + 1
Let n = k + 1
\(1+2+3+……………+k=\frac{((k+1)(k+1+1))}{2}\)Using the induction hypothesis which assumes that p (k) is true, we can rewrite it as:
\(1+2+3+………………+k+k+1=k\frac{(k+1)}{2}+k+1\) (by adding k + 1 two sides)
= \(\frac{(k(k+1)+2(k+1))}{2}\)
= \(\frac{((k+1)(k+2))}{2}\)
= \(\frac{((k+1)(k+1+1))}{2}\)
This shows that p (k + 1) is true.
The principle of mathematical induction shows that if both the above steps are true then p (n) is true for all n natural numbers.