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
...
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]
