Principle of Mathematical Induction (often abbreviated as PMI) is one of the techniques to prove Results/Conjecture.
What are some other Techniques? Well, we have Proof by Contradiction OR Proof by Construction OR, an equivalent way Strong Induction.
What is Conjecture? Proposition which is suspected to be True on the basis of preliminary supporting evidences, but for which no proof or disproof has yet been found.
STATEMENT
Let `P(n)` be a given statement involving the natural number `n`.
To prove that `P(n)` is TRUE for all integers `n\geqn_{o}`, it is sufficient to prove:
- `P(n_{o})` is TRUE
- For all `k\geqn_{o}`, `P(k) \rightarrow P(k+1)`
AS RULE OF INFERENCE
`( P(n_{o}) \wedge [\forall k {P(k) \rightarrow P(k+1)}] ) \rightarrow \forall n P(n)`
A PROOF using PMI has following steps:
- BASIS OF INDUCTION: Show that `P(n_{o})` is TRUE
- INDUCTION HYPOTHESIS: Assume that `P(k)` is TRUE
- INDUCTIVE STEP: Show that `P(k+1)` is TRUE ON THE BASIS of INDUCTION HYPOTHESIS
THESE can be summed as TWO STEPS:
- BASIS STEP : Show that `P(n_{o})` is TRUE
- INDUCTIVE STEP : Show that `P(k) \rightarrow P(k+1)` is TRUE `\forall k \in \mathbb{N}`
COMMON MISCONCEPTION ⚠
We don't assume that `P(k)` is TRUE `\forall` `k\geqn_{o}`
We show that if
`P(k)` is TRUE, then
`P(k+1)` is True.
HOW IT WORKS?
We have showed that `P(n_{o})` is TRUE Now, we have ASSUMED that `P(k)` is True, and on basis of Assumption we have showed that `P(k+1)` is True.[`P(k+1)` is True WHENEVER `P(k)` is True]
For understanding, let us assume `n_{o}` is 1. Thus, we have proved `P(1)`.
Now, since our assumption was on `k`, therefore,
we can make assumption valid if `k=1`.
Also, we have showed that `P(k)` implies `P(k+1)`. Thus, we can say that
`P(2)` is true, (since we have showed `P(1)` is True)
(In `p\rightarrow q`, `p` is sufficient for `q`)
Again,
we can make assumption valid if
`k=2`. Also, we have showed that `P(k)` implies `P(k+1)`. Thus, we can say
that `P(3)` is true.
Again, we can make assumption valid if `k=3`. Also, we have showed that `P(k)` implies `P(k+1)`. Thus, we
can say that `P(4)` is true.
Thus, we have initiated a never ending linear cycle. Else, we
can say that P(n) is True `\forall n\geqn_{o}`
Correlate with Dominos Effect Example,
When the first tile is pushed in the indicated direction, all the tiles
will fall. To be absolutely sure that all the tiles will fall, it is
sufficient to know that
(a) The first tile falls, and
(b) In the event that any tile falls its successor necessarily falls.
WHY IT WORKS?
WELL ORDERED SET : A set S is "Well-Ordered" if EVERY non-empty subsets of S has a LEAST ELEMENT.
Example : `\mathbb{N}`
- `\mathbb{Z}` is NOT well-ordered, {`x\in\mathbb{Z}` : `x<0`} has no least element
- `\mathbb{R}` is NOT well-ordered, {`x\in\mathbb{R}` : `x>1`} has no least element
`( P(n_{o}) \wedge [\forall k {P(k) \rightarrow P(k+1)}] ) \rightarrow \forall n P(n)`
Now, PROOF BY CONTRADICTION
Let us Assume that even after showing that SUFFICIENT CONDITION (LHS of Arrow) is True, still RHS is not fulfilled.
Assuming there is atleast one positive integer `n` for which `P(n)` is False.
Let `X` be the Set of positive integers for which `P(n)` is False.
Mathematically,
`X = { n : \neg P(n) }`
Because of our assumption, `X` is non-empty.
Since, `X \subset \mathbb{N}` and `\mathbb{N}` is Well-Ordered.
Therefore, by well-ordering property, `X` has a least element. [Definition of Well-Ordered Set!].
Let it be `m`
Now, `m` cannot be 1 since P(1) holds! [We have shown Sufficient Condition is True]
Therefore, `m>1`
Since `m` is Positive, and `m>1`. Thus, `(m-1)` must be a positive integer.
Now,
`m-1 < m`,
but still `(m-1)` is not least element.
Thus, `m-1 \notin X`
This implies, `P(m-1)` must be True. [Otherwise, it would have been in `X`]
Since, `P(k) \rightarrow P(k+1)` [We have shown Sufficient Condition is True]
Therefore, `P(m)` must be TRUE.
This CONTRADICTS `P(m)` being FALSE.
Hence, our assumption was Wrong. If LHS of Arrow Holds, then RHS will definitely hold!
😐 CONFUSED?
Take one page, one pen and Try to visualize everything. It will become crystal clear in one, or perhaps two cycles! 😉
THIS PROOF also solves one of the Common Doubts
Can PMI be applied only to set of Natural Numbers?
No, PMI can be applied to any set which is Well-Ordered! Be it `\mathbb{N}`, `\mathbb{N}` `\cup` `{0}` or `\mathbb{N}` `\cup` `{-5,-4,-3,-2,-1, 0 }`
