Q3 (6 points) Let n 2 1 be a positive integer. Prove combinatorially that n E K2 n = n(n + 1)2"-2. k=1 [Hint 1: Suppose that out of n people, anyone is permitted to register for a race. Everyone who registers may run twice. Gold and Silver medals are to be awarded, and the same person can win both medals. Everyone else gets a participation trophy.] [Hint 2: n(n + 1) = n(n - 1) + 2n]