Given a set S, define a pair in S to be a subset of S containing exactly 2 elements. (For example, the set {1, 2, 3} contains the pairs {1, 2}, {1, 3}, and {2, 3}.) Prove by weak induction (without using combinatorics formulas) that: any set with n elements has exactly n(n1) 2 different pairs, when n is an integer greater than or equal to 2. (Hint: if S is a set of size k + 1, label the elements of S as s1, s2, . . . , sk, sk+1. Think about the pairs in S that contain the last element sk+1, and the pairs that don't contain sk+1. Use the fact that set {s1, s2, . . . , sk} is a set of size k. )