n this problem, we will solve the following recurrence using the substitution method $($i$.$e$.,$ induction$).$

Note that in this problem we are trying to solve for T $($n$)$ exactly, not just for an asymptotically tight bound

on T $($n$).$ Assume T $(1)=0,$ T $(2)=1$ and that the recurrences below define T $($n$)$ for n $>2$:

T $($n$)=$ T

$($ n

$3$

$)$

$+$ T

$(2$n

$3$

$)$

$+1.(1)$

You do not need to worry about the n$/3$ and $2$n$/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