# Finding a tight bound for a recurrence relation

Problem:
Give tight asymptotic bounds $$( \Theta )$$ for the following function: $$T(n) = T(n-2) + n$$
We are not given the base case. I am going to assume that $$T(0) = 0$$ and $$T(1) = 1$$. Here are some values for the function. $$T(2) = T(0) + 2 = 2$$ $$T(3) = T(1) + 3 = 4$$ $$T(4) = T(2) + 4 = 6$$ $$T(5) = T(3) + 5 = 9$$ $$T(6) = T(4) + 6 = 12$$ $$T(7) = T(5) + 7 = 16$$ $$T(8) = T(6) + 8 = 20$$ $$T(9) = T(7) + 9 = 25$$ $$T(10) = T(8) + 10 = 30$$ It is growing faster than $$O(n)$$ time. I am fairly sure that $$T(n) \in O(n^2)$$. That is, $$O(n^2)$$ is an upper bound. If $$T(n)$$ is $$\theta(n^2)$$ then going from $$n = 5$$ to $$n = 10$$ we would expect, about, a factor of $$4$$ increase. We got an increased by a factor of $$\frac{ 10}{3}$$. I am thinking that the correct answer is: $$T(n) = \Theta(n^2)$$. However, I do not know how to prove that it is correct? or disprove it?
You just need to expant it (suppose $$n$$ is even) and using mathematical induction:
$$T(n) = n + (n-2) + T(n-4) = n + (n-2) + (n-4) + \cdots + 4 + 2 =$$ $$2 ( 1 + 2 + \cdots + \frac{n}{2}) = 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \frac{n(n+2)}{4} = \Theta(n^2)$$