A bijective proof
The key idea of the proof may be understood from a simple example: selecting k children to be rewarded with ice cream cones, out of a group of n children, has exactly the same effect as choosing instead the n − k children to be denied ice cream cones.
More abstractly and generally,[1] the two quantities asserted to be equal count the subsets of size k and n − k, respectively, of any n-element set S. Let A be the set of all k-element subsets of S, the set A has size Let B be the set of all n−k subsets of S, the set B has size . There is a simple bijection between the two sets A and B: it associates every k-element subset (that is, a member of A) with its complement, which contains precisely the remaining n − k elements of S, and hence is a member of B. More formally, this can be written using functional notation as, f : A → B defined by f(X) = Xc for X any k-element subset of S and the complement taken in S. To show that f is a bijection, first assume that f(X1) = f(X2), that is to say, X1c = X2c. Take the complements of each side (in S), using the fact that the complement of a complement of a set is the original set, to obtain X1 = X2. This shows that f is one-to-one. Now take any n−k-element subset of S in B, say Y. Its complement in S, Yc, is a k-element subset, and so, an element of A. Since f(Yc) = (Yc)c = Y, f is also onto and thus a bijection. The result now follows since the existence of a bijection between these finite sets shows that they have the same size, that is, .