# 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)$$?

• How many numbers >= n^2/4 are you adding at least? And him many numbers <= n^2 are you adding? That’s gives you a simple lower and upper bound. zkutch’s formula gives you a much better result, but this answers the question with only trivial maths. Oct 16 at 19:53

$$\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.