Use Newton's Binomial Theorem to prove that for every integer n 2 2 k=0 In the rest of this exercise, you will give a combinatorial proof of this identity. ,n). We have seen in class that the number of functions Consider the set S = {1, 2, f:'S s is equal to n". Consider a fixed integer k with 0 S k s n and a fixed subset A of S having size k. Determine the number of functions f : S S having the property that f(x)-x for all x A, and f(x) for all x S \ A. Explain why the above part implies the identity in (1). Hint: Divide the functions f into groups based on the number of r for which f(x)