a) Define the string set S as follows:

Basis step: abc S

Recursive step: If x S, then axa S and bxb S and cxc S

Using structural induction, prove that for each string x S, the length of the string is odd.

b) Use master theorem to find the solution to the recurrence relation f(n) = 4f(n/2) + 2^4, when n = 2^k, where k is a positive integer and f(1) = 1.