I am trying to solve a recurrence using the induction principle (I am asking for help/confirmation about this solving method, so don't answer with a solution developed by iteration method or something else).
I want to precise that I have just started studying recurrence relations, so I am asking for confirmation of my work.
Given:
$$
T(n) = \begin{cases}
1 & n = 1
\\
T(n - 1) + n^2 & n \gt 1
\end{cases}
$$
I want to prove by induction, that $T(n) = O(n^3)$.
I have to check if the inequality is verified for T(1):
$$T(1) = (1 - 1)^3 + 1^2 = 1$$
then I assume that $\forall m < n, \space \exists c > 0, n_0 \ni \forall n > 0,\space T(n) \le cn^3$ and I have to prove that it holds for n:
$$
T(n) = T(n \space - \space 1) + n^2 \space \le \space c(n - 1)^3 + n^2 \space = \space cn^3 - 3cn^2 + 3cn - c + n^2 \space \le \space cn^3
$$
Now, I have to check for what values of c, the inequality is verified.
$$
cn^3 - 3cn^2 + 3cn - c + n^2 \le cn^3\\
3cn^2 - 3cn + c - n^2 \ge 0\\
$$
from now on, this is the part about I am not sure if I did it right:
$$
n(3cn - 3c - n) \ge -c\\
3cn - 3c - n \ge -\frac{c}{n}\\
n - 3c \ge -\frac{3c^2 - c}{n}\\
n \ge\ -\frac{3c^2 - c}{n} + 3c
$$
Now, I am not sure if i did that right.
I know that this recurrence is a $O(n^3)$ and it can be proven by expand it, but I want to know if my proof, using the induction principle, is true.
I want to say that this isn't a homework or something like that, it's a simple exercise that came up to my mind.
Why don't you do the following? $$\frac{T(n)}{n^{3}}\leq 2$$ by induction. $\frac{T(1)}{1}=1\leq 2$. Assume now $$\frac{T(n-1)}{(n-1)^{3}}\leq 2.$$ Then $$\frac{T(n)}{n^{3}}=\frac{T(n-1)+n^{2}}{n^3}=\frac{T(n-1)}{(n-1)^3}.\frac{(n-1)^3}{n^3}+\frac{n^2}{n^3}\leq \frac{2(n-1)^3+n^2}{n^3}.$$ The latter is $\le 2$ since $2(n-1)^3+n^2\, \leq 2n^3$ is equivalent to $5n^2-6n+2 \geq 0$, which is obvious!