MATH 2001 Study Guide - Quiz Guide: Equivalence Class, And1
Document Summary
Compute k k=0 (cid:19) (cid:19) (cid:19) ( 1)k (cid:18)n (cid:18)n (cid:18)n (cid:18)n (cid:19) n(cid:88) (cid:1)xkyn k and substitute x = 1 and y = 1. (cid:18)n (cid:19) (cid:18)n (cid:18)n (cid:18)n (cid:19) (cid:19) (cid:19) One way to see this is to remember that (x + y)n = k k=0. The left side is the number of subsets of an n-element set s with an even number of elements. The right side is the number of subsets with an odd number of elements. We can construct a one-to-one correspodence between these two collections. Let"s pick an element of s call it x. If we have a set with an even number of elements, either it contains x or it doesn"t. If it contains x then remove x from it to get a set with an odd number of elements. If it does not contain x then add x to it to get a set with an odd number of elements.
