Help with this recurrence

Question

$$ T(n) = \begin{cases} 6, & n=0 \\ 9T(n-2)+n, & n>0 \end{cases} $$

I don't know how to resolve this.....Can you tell me how can I solve it?

Answer 1

Simple way is to follow it a couple of terms and see the pattern. So assuming $n = 2m$ is even, $$ \begin{split} T(n) &= 9T(n-2)+n \\ &= 9 (9T(n-4) + (n-2)) + n\\ &= 9^2T(n-4) + 9(n-2) + n \\ &= 9^3 T(n-6) + 9^2 (n-4) + 9(n-2) + n \\ &\ldots \\ &= 9^m T(0) + \sum_{k=0}^{m-1} 9^k (n-2k) \end{split} $$ Can you finish it? (Note: if $n = 2m+1$ is odd, you will end up with $9^mT(1)$ in the last term and some other related changes will be needed.)

A different way is to propose a solution of the form $T(n) = a^n$ for some $a \in \mathbb{R}$, plug it in and see what values of $a$ will fit...