What is Principle of Mathematical Induction ? Explain on following points :
1. Introduction
2. All the key points
3. Give one example for verification .
Answers
Mathematical induction can be used to prove that an identity is valid for all integers n≥1 . Here is a typical example of such an identity:
1+2+3+⋯+n=n(n+1)2.(3.4.1)
More generally, we can use mathematical induction to prove that a propositional function P(n) is true for all integers n≥1 .
Definition: Mathematical Induction
To show that a propositional function P(n) is true for all integers n≥1 , follow these steps:
Basis Step: Verify that P(1) is true.
Inductive Step: Show that if P(k) is true for some integer k≥1 , then P(k+1) is also true.
The basis step is also called the anchor step or the initial step. This proof technique is valid because of the next theorem.
Theorem 3.4.1 : Principle of Mathematical Induction
If S⊆N such that
1∈S , and
k∈S⇒k+1∈S ,
then S=N .
Remark
Although we cannot provide a satisfactory proof of the principle of mathematical induction, we can use it to justify the validity of the mathematical induction. Let S be the set of integers n for which a propositional function P(n) is true. The basis step of mathematical induction verifies that 1∈S . The inductive step shows that k∈S implies k+1∈S . Therefore, the principle of mathematical induction proves that S=N . It follows that P(n) is true for all integers n≥1 .
The basis step and the inductive step, together, prove that
P(1)⇒P(2)⇒P(3)⇒⋯.(3.4.2)
Therefore, P(n) is true for all integers n≥1 . Compare induction to falling dominoes. When the first domino falls, it knocks down the next domino. The second domino in turn knocks down the third domino. Eventually, all the dominoes will be knocked down. But it will not happen unless these conditions are met:
The first domino must fall to start the motion. If it does not fall, no chain reaction will occur. This is the basis step.
The distance between adjacent dominoes must be set up correctly. Otherwise, a certain domino may fall down without knocking over the next. Then the chain reaction will stop, and will never be completed. Maintaining the right inter-domino distance ensures that P(k)⇒P(k+1) for each integer k≥1 .