I am studying for an exam, and one practice problem I attempted asks me to prove that:
$T(n) = T(n - 2) + n^2 = O(n^3)$
I need to use the induction/substitution method for this problem. My proof attempt is below. Is this correct? If so, is there a more concise way to do this?
We claim that $T(n) = O(n^3)$. To prove this, we need to show that $T(n) \leq Cn^3$ $\forall n > n_0$ (for any positive constants $C$ and $N_0$). We prove this as follows:
\begin{align} T(n) &= T(n - 2) + n^2 &&\\ &\leq C(n - 2)^3 + n^2 \text{ (by inductive hypothesis)} &&\\ &= Cn^3 - 6Cn^2 + 12Cn - 8C + n^2 &&\\ &= X \end{align}
In order for our proof to hold, we must show that $X < Cn^3$:
\begin{align} X &\leq Cn^3 &&\\ Cn^3 - 6Cn^2 + 12Cn - 8C + n^2 &\leq Cn^3 &&\\ -6Cn^2 + 12Cn - 8C + n^2 &\leq 0 &&\\ -6Cn^2 + 12Cn - 8C &\leq -n^2 &&\\ C(-6n^2 + 12n - 8) &\leq -n^2 &&\\ C(6n^2 - 12n + 8) &\geq n^2 \text{ (multiply by -1)} &&\\ C &\geq \frac{n^2}{6n^2 - 12n + 8} \text{ (assumes $n \geq 2$)} \end{align}
The right-hand-side of this equation is always less than or equal to one if $n \geq 2$. Thus, if we simply choose $C = 1$ and $n_0 = 3$, $T(n) \leq Cn^3$, which is what we set out to prove. It follows by the principle of induction that $T(n) \leq 1 * n^3$ $\forall n > 3$, and thus that $T(n) = O(n^3)$.
The calculation you did looks fine, but there are some technical issues with how you infer the $O(n^3)$ from it and they involve the base cases.
For instance, you claim at the end that $T(n) \leq n^3$ for $n \geq n_0$. However, I would tell you that this is not true. For instance, if you start out with $T(1) = T(2) = 100^3$, then define $T$ recursively, then $T(n) \leq n^3$ false for all $n \geq 2$. It is true eventually because $1^2 + 2^2 + \cdots + n^2 = \frac{1}{3}n^3 + \mbox{lower order terms}$, but the bound for $n_0$ is incorrect.
In particular, I would ask you to look at where you got $C$ from: you cannot pick it arbitrarily. This was a subtlety that I did not see in the first question that you asked, but is actually very important.
Also, if you were to tell me that $n_0 \geq 2$, then I would have agreed before doing the calculation, because $T(n - 2)$ does not make sense unless $n -2$ is at least the minimum value that $T$ is defined on. This is also another subtlety that is important.
The second problem with the induction is that you are inducting on the even numbers and odd numbers separately (which is why I defined $T$ above on $1$ and on $2$), because we are looking at $T(n-2)$ and not $T(n)$. In particular, the $C$ that you pick should rely on both the base cases.