only minor difference from a mathematical Induction is that it allows us to assume more than just P(n), whereas, in a mathematical induction, we only assume that P(n) is true and try to prove that P(n+1) is also true. In the inductive step of our complete induction proof, we may assume P(0),P(1),....,P(n) are all true and based on our assumption, we prove that P(n+1) is also true.
A Template for Induction Proofs:
1. State that our proof is by complete induction to convey the overall structure of the proof of our upcoming arguments and statements.
2. Define an appropriate predicate P(n)
assume that P(0),P(1),...P(n) is all true. The eventual conclusion of the induction proof will be that P(n) is true for all positive n. Thus, we should produce the predicate P(n) so that follows from the conclusion. Often, it can be derived from the proposition that we are trying to prove.
The predicate P(n) is called the Induction Hypothesis.
3. Prove that P(n) is true. This step of the proof is called the Base-Case(or Basis); showing that the statement holds when n is equal to the lowest value that n is given in the question.
4. Prove that P(n) implies P(n+1) for every positive natural integers, n. This step of the proof is called the Inductive Step.
by assuming the induction hypothesis, then use this assumption to prove the statement for n + 1; this step requires some ingenuity and appropriate mathematical approach.
5. Based on the facts that have been made in the previous steps, we may conclude that P(n) is true for all non-negative integers, n.
think the induction as the domino effect:
1. the first domino will fall
2. whenever a domino falls, its next neighbor will also fall
- P(0) -> P(1) -> P(2) -> P(3) -> ... -> P(n)
then conclude that all of the dominoes will fall; P(n) is true for all positive natural integers, n
No comments:
Post a Comment