Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method I'm trying to solve this recurrence. I applied the iterative method:
$$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum_{i=0}^{k-1}(n-2i)^2$$ So $n-2k=1$ when $n=2k+1$ and we have: $$\sum_{i=0}^{(n-3)/2}(n-2i)^2$$ Now how can I demonstrate that this series is $\Theta(n^3)$?
$$\sum_\limits{i=0}^{(n-3)/2}(n-2i)^2 = \sum_\limits{i=0}^{(n-3)/2}(n^2-4in+4i^2)=\\
=n^2\frac{n-3}{2}-4n\frac{\frac{n-3}{2}\left(\frac{n-3}{2}+1\right)}{2}+4\frac{\frac{n-3}{2}\left(\frac{n-3}{2}+1\right)\left(2\frac{n-3}{2}+1\right)}{6}=n^3\cdot A_n$$
Where is easy to see, that $A_n$ is bounded.