Induction and Recursion (Part A)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
March 04, 2021
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 1 / 14
1 Mathematical Induction
2 Strong Induction and Well-Ordering
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 2 / 14
Ladder Climbing
”Induction provides a step-by-step method of achieving a goal”
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 3 / 14
Mathematical Induction
Principle of Mathematical Induction
To prove that P(n) is true for all positive integers n, where P(n) is a
propositional function, we complete two steps: Basis Step: We verify that P(1) is true.
Inductive Step: We show that the conditional statement P(k) → P(k + 1) is true for all positive integers k.
Example: Climbing an infinite ladder
– We can reach the first rung of the ladder. (P(1) is true)
– If we can reach a particular rung (k) of the ladder, then we can reach the next rung (k + 1). (P(k) → P(k + 1) is true for all positive integer k)
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 4 / 14
Mathematical Induction (cont.)
Induction as a Rule of Inference
(P(1) ∧ ∀k(P(k) → P(k + 1))) → ∀nP(n),
when the domain is the set of positive integers.
• In a proof by mathematical induction, it is not assumed that P(k) is true for all positive integers! It is only shown that if it is assumed that P(k) is true, then P(k + 1) must also be true.
• Proofs by mathematical induction do not always start at the integer 1. In such a case, the basis step begins at a starting point b where b is an integer.
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 5 / 14
Why Mathematical Induction is Valid
Mathematical induction is valid because of the well-ordering property, which states that every nonempty subset of the set of positive integers has a least element.
• Suppose that P(1) holds and P(k) → P(k + 1) is true for all positive integers k.
• Assume there is at least one positive integer n for which P(n) is false. Then the set S of positive integers for which P(n) is false is nonempty.
• By the well-ordering property, S has a least element, say m.
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 6 / 14
Why Mathematical Induction is Valid (cont.)
• We know that m can not be 1 since P(1) holds.
• Since m is positive and greater than 1, m − 1 must be a positive integer.
Since m − 1 < m, it is not in S, so P(m − 1) must be true.
• But then, since the conditional P(k) → P(k + 1) for every positive integer k holds, P(m) must also be true. This contradicts P(m) being false.
• Hence, P(n) must be true for every positive integer n.
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 7 / 14
Examples Proved by Mathematical Induction
Prove that 1+2+3+...+n = n(n+1). 2
Provethat1+2+22+...+2n =2n+1−1.
Prove that n3 − n is divisible by 3 whenever n is a positive integer. Prove that nj=1 Aj = nj=1 Aj. (De Morgan’s Law)
(Textbook Section 5.1)
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 8 / 14
Strong Induction
Strong induction is used when it is not easy to prove a result using mathematical induction.
Principle of Strong Induction
To prove that P(n) is true for all positive integers n, where P(n) is a
propositional function, we complete two steps:
Basis Step: We verify that the proposition P(1) is true.
Inductive Step: We show that the conditional statement
[P(1) ∧ P(2) ∧ ... ∧ P(k)] → P(k + 1) is true for all positive integers k.
Strong Induction and the Infinite Ladder • We can reach the first rung, and
• For every positive integer k, if we can reach all the first k rungs, then we can reach the (k + 1) st rung.
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 9 / 14
Strong Induction (cont.)
Show that if n is an integer greater than 1, then n can be written as the
product of primes.
Let P(n) be the proposition that n can be written as the product of primes. Basis step: P(2) is true since 2 can be written as the product of one prime
(itself ).
Inductive step: The inductive hypothesis is the assumption that P(j) is true for all j with 2 ≤ j ≤ k, that is, the assumption that j can be written as the product of primes whenever j is a positive integer at least 2 and not exceeding k. To complete the inductive step, it must be shown that
P(k + 1) is true under this assumption.
(Textbook Section 5.2)
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 10 / 14
Strong Induction (cont.)
Proof (cont.)
There are two cases to consider: (i) k + 1 is prime and (ii) k + 1 is composite. If k + 1 is prime, P(k + 1) is true. If k + 1 is composite, it can be written as the product of two positive integers a and b with
2 ≤ a ≤ b < k + 1. The inductive hypothesis can be used to factorize both a and b as the product of primes. Thus, k + 1 can be written as the product of primes.
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 11 / 14
The Well-Ordering Property
The well-ordering property states that every nonempty set of nonnegative integers has a least element.
The well-ordering property useful in induction relevant proofs. It can be directly used in proofs.
Use the well-ordering property to prove the division algorithm. The division algorithm states that if a is an integer and d is a positive integer, then there are unique integers q and r with 0 ≤ r < d and a = dq + r.
(Textbook Section 5.2)
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 12 / 14
The Well-Ordering Property (cont.)
• Let S be the set of nonegative integers of the form a − dq, where q is an integer. This set is nonempty because −dq can be made as large as desired (taking q to be a negative integer with large absolute value). By the well-ordering property, S has a least element r = a − dq0.
• The integer r is nonegative and r < d. If it were not, then there would be a smaller nonegative element in S, namely, a − d(q0 + 1).
• If r ≥ d, a − d(q0 + 1) = a − dq0 − d = r − d ≥ 0. Consequently, there are integers q and r with 0 ≤ r < d.
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 13 / 14
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 5a MdH W22 March 04, 2021 14 / 14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com