NOTES
PROOF BY INDUCTION
Proof by induction is used to proof that p(n)∀n ∈ Z +
Mathematical Induction:
The two steps of the Proof by Induction:
1) Basis step: verify that p(1) is true
2) Inductive step: show that p(k) → p(k + 1) is true for ∀n ∈ Z+
a - Assume that p(k) is true for an arbitrary (not all) positive integer k.
b - This assumption is called the inductive hypothesis.
c - Show that p(k+1) must be true.
i.e: (p(1) ∧ ∀k (p(k) → p(k + 1)) → ∀n p(n)
Strong Induction:
1) Basis step: verify that p(1) is true
2) Inductive hypothesis: Assume P(j) is true for all integers j, 2 ≤ j ≤ k
3) Inductive step: show that (p(1) ∧ p(1) ∧ ....p(k)) → p(k + 1) is true for
all positive integer k
MATHEMATICAL VS STRONG INDUCTION:
The only difference: Inductive step makes use of stronger hypothesis
Note: Strong induction is known as the second principle of mathematical
induction.
RECURSION
Recursion is the general term for the practice of defining an object in terms
of itself.
An inductive proof establishes the truth of p(n+1) recursively in terms of
p(n).
Base step: Define p(0) or the first term
Recursive step: define p(n) with respect of p(n-1)
1
PROOF BY INDUCTION
Proof by induction is used to proof that p(n)∀n ∈ Z +
Mathematical Induction:
The two steps of the Proof by Induction:
1) Basis step: verify that p(1) is true
2) Inductive step: show that p(k) → p(k + 1) is true for ∀n ∈ Z+
a - Assume that p(k) is true for an arbitrary (not all) positive integer k.
b - This assumption is called the inductive hypothesis.
c - Show that p(k+1) must be true.
i.e: (p(1) ∧ ∀k (p(k) → p(k + 1)) → ∀n p(n)
Strong Induction:
1) Basis step: verify that p(1) is true
2) Inductive hypothesis: Assume P(j) is true for all integers j, 2 ≤ j ≤ k
3) Inductive step: show that (p(1) ∧ p(1) ∧ ....p(k)) → p(k + 1) is true for
all positive integer k
MATHEMATICAL VS STRONG INDUCTION:
The only difference: Inductive step makes use of stronger hypothesis
Note: Strong induction is known as the second principle of mathematical
induction.
RECURSION
Recursion is the general term for the practice of defining an object in terms
of itself.
An inductive proof establishes the truth of p(n+1) recursively in terms of
p(n).
Base step: Define p(0) or the first term
Recursive step: define p(n) with respect of p(n-1)
1
