a) Let n be a non-negative integer. Consider the functions f(n) n! 92 (n) 2! (n 2)! i) Can you prove that f(n) = 9 (n) + 92 (n) by using a combinatorial counting approach by showing that LHS and RHS are counting the same object? n! 2! (n 2)! +nxn and gi(n): (2n)! (2n - 2)!2! = ii) Can you prove that f(n) = g(n) + 92(n) by using an algebraic ap- proach? (2+1) b) Using generating functions or otherwise, solve the recurrence relation de- fined by Hk = = 3Hk-1 + 4k-1, for k 1, with the initial condition Ho = 1. Is the solution unique? Justify. (3)