Mathematics > QUESTION PAPER (QP) > ch5-homework-solutions (All)

ch5-homework-solutions

Document Content and Description Below

5.1 #46 [10pts] Use mathematical induction to prove that a set with n elements, where n is an integer greater than or equal to three, has n(n−1)(n−2) subsets containing exactly three elements. You may use without proof the fact that a set with n elements, n ≥ 2, has n(n−1) subsets with exactly two elements. Basis step: n = 3. For a set with three elements, there is only one subset containing exactly three elements, which is the set itself. Clearly 3(3−1)(3−2) = 1. Inductive hypothesis: Assume that a set with n elements has n(n−1)(n−2) subsets with exactly three elements, where n ≥ 3. Inductive step: Let S be a set with n + 1 elements, let a be an element of S, and let T = S a . Subsets of S that contain exactly three elements either contain a or do not contain a. The subsets that do not contain a are the three-element subsets of T , and by the inductive hypothesis, there are n(n−1)(n−2) such subsets. The subsets that do contain a are the two-element subsets of T , plus the element a, and we are given that there are n(n−1) . such subsets. So the total number of subsets is n(n − 1)(n − 2) + n(n − 1) = (n + 1)n(n − 1) 6 2 6 Grading: 1 point each for basis step and inductive hypothesis, 8 points for the inductive step. This one is tricky, so give students the benefit of the doubt when it comes to partial credit: 2 point for the statement that subsets either contain a or not, 3 points for each of the two groups of subsets. 2. 5.1 # 66 [5pts] Use the well-ordering property to show that the following form of mathematical induction is a valid method to prove that P (n) is true for all positive integers n Basis step: P (1) and P (2) are true. Inductive step: For each positive integer k, if P (k) and P (k + 1) are both true, then P (k + 2) is true. By contradiction. Assume there is a nonempty set S of all positive integers n such that P (n) is false. By the well-ordering property, S must have a smallest element m. We know that m = 1 and m = 2 because of the basis step, so m 3, which means that m 1 and m 2 are positive integers. m is the smallest element in S, so we know that m 1 and m 2 are not in S, since they are smaller than m. This means that P (m 1) and P (m 2) are true, which by the inductive step means P (m) is true, which is a contradiction. Grading: 5 points. This is almost exactly the same as the proof of the validity of normal induction. Deduct 1 point if the well-ordering property isn’t cited. 3. 5.3 # 14 [8pts] Use structural induction to show that fn+1fn−1 − f 2 = (−1)n when n is a positive integer and fi is the ith Fibonacci number. Basis step: n = 1. f2f0 − f 2 = 1 • 0 − 12 = (−1)1. Inductive hypothesis: Assume that fn+1fn−1 − f 2 = (−1)n for n ≥ 1.

[Show More]

Last updated: 3 years ago

Preview 1 out of 6 pages

Get Access

Instant download after payment

Card Payments

₿ Crypto Accepted

Instant download