Prove the following identities about Stirling numbers of the second kind combinatorially, i.e., identify a quantity counted by both the left and right sides of the equation, and briefly explain why both sides do count that specific quantity. (a) For any integer k > 1, S(k, k 1) = (). (b) For any non-negative integers k and n, S(k+1, n+1) = {{-o (4) S(k i,n). For example, in the case k = 4 and n = 2: (6) s(4,2) + (4) S(3, 2) + (-) s(2, 2) + (3) s(1,2) + (4) s(0, 2) =1.7+4.3+61+4.0+1:0) = 25 = S(5,3) Prove the following identities about Stirling numbers of the second kind combinatorially, i.e., identify a quantity counted by both the left and right sides of the equation, and briefly explain why both sides do count that specific quantity. (a) For any integer k > 1, S(k, k 1) = (). (b) For any non-negative integers k and n, S(k+1, n+1) = {{-o (4) S(k i,n). For example, in the case k = 4 and n = 2: (6) s(4,2) + (4) S(3, 2) + (-) s(2, 2) + (3) s(1,2) + (4) s(0, 2) =1.7+4.3+61+4.0+1:0) = 25 = S(5,3)