IntroductionPreliminariesFormal StatementExamplesStrong InductionMore ExamplesInductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesInductionSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSection 3.3 of [email protected] / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesIntroductionHow can we prove the following quantified statement?∀s ∈ SP (x)For a finite set S = {s1, s2, . . . , sn}, we can prove thatP (x) holds for each element because of the equivalence,P (s1) ∧ P (s2) ∧ · · · ∧ P (sn)We can use universal generalization for infinite sets.Another, more sophisticated way is to use Induction.2 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesIntroductionHow can we prove the following quantified statement?∀s ∈ SP (x)For a finite set S = {s1, s2, . . . , sn}, we can prove thatP (x) holds for each element because of the equivalence,P (s1) ∧ P (s2) ∧ · · · ∧ P (sn)We can use universal generalization for infinite sets.Another, more sophisticated way is to use Induction.3 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesIntroductionHow can we prove the following quantified statement?∀s ∈ SP (x)For a finite set S = {s1, s2, . . . , sn}, we can prove thatP (x) holds for each element because of the equivalence,P (s1) ∧ P (s2) ∧ · · · ∧ P (sn)We can use universal generalization for infinite sets.Another, more sophisticated way is to use Induction.4 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesIntroductionHow can we prove the following quantified statement?∀s ∈ SP (x)For a finite set S = {s1, s2, . . . , sn}, we can prove thatP (x) holds for each element because of the equivalence,P (s1) ∧ P (s2) ∧ · · · ∧ P (sn)We can use universal generalization for infinite sets.Another, more sophisticated way is to use Induction.5 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesWhat is Induction?If a statement P (n0) is true for some nonnegative integer;say n0= 1.Also suppose that we are able to prove that if P (k) is truefor k ≥ n0, then P (k + 1) is also true;P (k) → P (k + 1)It follows from these two statements that P (n) is true forall n ≥ n0. I.e.∀n ≥ n0P (n)This is the basis of the most widely used proof technique:Induction.6 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesWhat is Induction?If a statement P (n0) is true for some nonnegative integer;say n0= 1.Also suppose that we are able to prove that if P (k) is truefor k ≥ n0, then P (k + 1) is also true;P (k) → P (k + 1)It follows from these two statements that P (n) is true forall n ≥ n0. I.e.∀n ≥ n0P (n)This is the basis of the most widely used proof technique:Induction.7 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesWhat is Induction?If a statement P (n0) is true for some nonnegative integer;say n0= 1.Also suppose that we are able to prove that if P (k) is truefor k ≥ n0, then P (k + 1) is also true;P (k) → P (k + 1)It follows from these two statements that P (n) is true forall n ≥ n0. I.e.∀n ≥ n0P (n)This is the basis of the most widely used proof technique:Induction.8 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesWhat is Induction?If a statement P (n0) is true for some nonnegative integer;say n0= 1.Also suppose that we are able to prove that if P (k) is truefor k ≥ n0, then P (k + 1) is also true;P (k) → P (k + 1)It follows from these two statements that P (n) is true forall n ≥ n0. I.e.∀n ≥ n0P (n)This is the basis of the most widely used proof technique:Induction.9 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesThe Well Ordering Principle IWhy is induction a legitimate proof technique?At its heart is the Well Ordering Principle.Theorem (Principle of Well Ordering)Every nonempty set of nonnegative integers has a least element.Since every such set has a least element, we can form a basecase.We can then proceed to establish that the set of integersn ≥ n0such that P (n) is false is actually empty.Thus, induction (both “weak” and “strong” forms) are logicalequivalences of the well-ordering principle.10 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesAnother View ITo look at it another way, assume that the statementsP (n0) (1)P (k) → P (k + 1) (2)are true. We can now use a form of universal generalization asfollows.Say we choose an element from the universe of discourse c. Wewish to establish that P (c) is true. If c = n0then we are done.11 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesAnother View IIOtherwise, we apply (2) above to getP (n0) ⇒ P (n0+ 1)⇒ P (n0+ 2)⇒ P (n0+ 3)· · ·⇒ P (c − 1)⇒ P (c)Via a finite number of steps (c − n0), we get that P (c) is true.Since c was arbitrary, the universal generalization is established.∀n ≥ n0P (n)12 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesInduction IFormal DefinitionTheorem (Principle of Mathematical Induction)Given a statement P concerning the integer n, suppose1P is true for some particular integer n0; P (n0) = 1.2If P is true for some particular integer k ≥ n0then it istrue for k + 1.Then P is true for all integers n ≥ n0; i.e.∀n ≥ n0P (n)is true.13 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesInduction IIFormal DefinitionShowing that P (n0) holds for some initial integer n0iscalled the Basis Step. The statement P (n0) itself is calledthe inductive hypothesis.Showing the implication P (k) → P (k + 1) for everyk ≥ n0is called the Induction Step.Together, induction can be expressed as an inference rule.P (n0) ∧ ∀k ≥ n0P (k) → P (k + 1)→ ∀n ≥ n0P (n)14 / 85InductionCSE235IntroductionPreliminariesFormalStatementExamplesStrongInductionMoreExamplesExample IExampleProve that n2≤ 2nfor all n ≥ 5 using induction.We formalize the statement as P (n) = (n2≤ 2n).Our base case here is for n = 5. We directly
View Full Document
Unlocking...