Recurrence - finding asymptotic bounds for $T(n) = T(n-2) + n^2$ I've been working on a problem set for a bit now and I seem to have gotten the master method down for recurrence examples. However, I find myself having difficulties with other methods (recurrence trees, substitution). here is the question I am stuck on:
$$T(n) = T(n-2) + n^2$$
Is there a pattern as follows?
$$n^2 + T(n-2) + T(n-4) +...$$ 
where it goes until there is no more n left. so around n/2 times
and would that mean that 
$$n^2 + (n-2)^2 + (n-i) ^2$$ so the asymptotic bound would be $\theta(n^2)$?

I am honestly taking a shot in the dark here, so I was hoping someone could help guide me in how to approach these questions.

Thank you,

Tyler
$$T(n) = T(n-2) + n^2 = T(n-4) + (n-2)^2 + n^2 = T(n-2k) + \sum\limits_{i = 0}^{k - 1}(n - 2i)^2$$

This goes down while $n - 2k \ge 0$. Assuming even $n$ (for asymptotic complexity, it does not really matter, and you can do similar calculations for odd $n$ also, with the same asymptotic results), we have $k = \frac{n}{2}$ at the end.

$$T(n) = T(0) + \sum\limits_{i = 0}^{\frac{n}{2} - 1}(n - 2i)^2 = \sum\limits_{i = 0}^{\frac{n}{2} - 1}(n^2 - 4ni + 4i^2) + C$$
$$T(n) = n^2\cdot\left(\frac{n}{2}-1\right) - 4n\cdot\frac{1}{2}\cdot\frac{n}{2}\cdot\left(\frac{n}{2} - 1\right) + 4\cdot\frac{1}{6}\cdot\left(\frac{n}{2} - 1\right)\cdot\frac{n}{2}\cdot(n-1) + C$$
$$\therefore \ T(n) = \Theta(n^3)$$
let $n=log m$
$$T(\log m)=T(\log m-\log4)+(\log m)^2$$
$$T(\log m)=T(\log m/4)+(\log m)^2$$
$$s(m)=s(m/4)+m^2$$
here $a=1,b=4$ and $f(n)=m^2$
$$m^{\log a}=1$$
$$f(m)&gt;m^{\log a}$$ (base 4)

case (iii) of masters theorem follows
hence $s(m)=\Theta(m^2)$
after comouting $c$ through $af(m/b)=cf(n)$
$$c=1/16&lt;1$$
hence case (iii) totally followed
and $s(m)=\Theta(m^2)$
and $T(m)=\Theta(2^2n)$
m not confirm about the answer but the procedure will be the same