Question 3: (2+2+2+4=10 points ) In this problem, we will solve the following recurrence using the substitution method (i.e., induction). Assume T(1)=0,T(2)=1 and that the recurrences below define T(n) for n>2 : T(n)=T(3n)+T(32n)+1. You do not need to worry about the n/3 and 2n/3 terms in (1) being fractions. 1. Try T(n)=n. Does the recurrence hold? You may ignore the base cases (n=1 and 2) and only look at whether T(n) satisfies Eq. (1)). Is the RHS bigger than the LHS? Show your calculations. 2. Try T(n)=n. Does the recurrence hold? You may ignore the base cases ( n=1 and 2) and only look at whether T(n) satisfies Eq. (1). Is the RHS bigger than the LHS? Show your calculations. 3. Try T(n)=n2. Does the recurrence hold? You may ignore the base cases (n=1 and 2) and only look at whether T(n) satisfies Eq. (1). Is the RHS bigger than the LHS? Show your calculations. Among parts 1 to 3, which choice of T(n) "almost" satisfied recurrence (11)? That is, for which choice of T(n) was the left-hand side almost equal to the right-hand side of (1)? Reflect on this question because it would help solve the next part. 4. Let T(n)=np+c for some cR, and p>0 and solve for p and c. Based on the p and c you obtained, prove your result formally using the substitution method. (Note that parts 1-3 correspond to c=0 and p=1/2,p=1,p=2, respectively.)