For each of the following, we give a recursive definition of the function described. You need to carefully explain both the base cases and why the recursion is true using counting rules and case analysis. (1 point explanation of base cases, 4 points explanation of recursion.) You do not need to unravel the recursion or give a closed form for the function. 5 Points Let A(n) be the number of strings of decimal digits of length n that are palindromes i.e., the same forwards and backwards. Then A(1)=10,A(2)=10 and A(n)=10A(n2) for n3. Q2.2 5 Points Let B(n) be the number of sequences of integers in the set {1,4} that sum to n. Then B(1)=1,B(2)=1,B(3)=1,B(4)=2 and B(n)=B(n1)+B(n4) for n5. Q2.3 5 Points Let C(n) be the number of triangles in a complete undirected graph with n vertices. Then C(1)=0,C(2)=0,C(3)=1, and C(n)=C(n1)+(n12) for n4. Let T(n) be the time for mergesort on an array of size n. Then T(1)=c,T(n)=2T(n/2)+c for some c,c>0