Analysis of Algorithms: Solving Recursion equations-$T(n)=3T(n-2)+9$ I need your help with solving this recursion equation: $T(n)=3T(n-2)+9$
with the initial condition: $T(1)=T(2)=1.$
I need to find $T(n),$ the complexity of the algorithm which works that way.
I tried to do that with induction.
Edit: The answer should depend on $n.$
Thank you.

Induction is a way to prove things; it's not generally helpful in solving computational problems, except perhaps in proving that a guessed solution is correct.
Note that the values of $T(n)$ for odd $n$ are completely independent of the values for even $n$, so you can look at it as essentially two separate instances of the recursion $f(n+1) = 3f(n) + 9$ with initial condition $f(1) = 1$. There are lots of ways to solve that recurrence. One is to 'unwind' it, which is a bit like doing an induction: $f(n) = 3f(n-1)+9 = 3(3f(n-2)+9)+9$ = $3^2f(n-2)+3$ and so on. If you continue in this fashion, you'll find that after $k$ steps you have $f(n)$ = $3^kf(n-k) + 9 \sum_{i=0}^{k-1}3^i$; in particular, when $k=n-1$ you have $f(n) = 3^{n-1}f(1)+9\sum_{i=0}^{n-2}3^i$ = $3^{n-1} + 9 \cdot \frac{3^{n-1}-1}{2} = \frac{1}{2}\left(11 \cdot 3^{n-1} - 9\right)$.
Now $T(2n) = f(n) = \frac{1}{2}\left(11 \cdot 3^{n-1} - 9\right)$, and $T(2n-1) = f(n) = \frac{1}{2}\left(11 \cdot 3^{n-1} - 9\right)$.
A neater way to solve the $f$ recurrence is to let $g(n) = f(n) - d$ for some constant $d$ yet to be determined. Then $f(n) = g(n) + d$, so the recurrence can be written $g(n+1)+d$ = $3 \left(g(n)+d \right) + 9$ = $3g(n) + 3d + 9$, or $g(n+1)=3g(n) + 2d + 9$. Setting $d=-9/2$ makes this $g(n+1)=3g(n)$ with initial condition $g(1)=f(1)+9/2=11/2$. This is simple exponential growth: $g(n) = 3^{n-1}g(1)= \frac{11}{2} \cdot 3^{n-1}$. Hence $f(n) = g(n)-9/2 = \frac{1}{2}\left(11 \cdot 3^{n-1} - 9\right)$, of course giving the same solution for the original problem.
