# algorithm analysis – 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?