Doing induction on recurrences correctly I have $$T(n)=T(n-1)+n^{2}$$
And I know, by drawing the recursion tree that this is $\Theta (n^{3})$
However, if I try claiming that it's $O(n^{2})$ through induction:
$$T(n)\le c(n-1)^{2}+n^{2}\le cn^{2}$$
which evaluates to
$$c\ge \frac{n^2}{2n-1}$$
Which makes $c&gt;0$ for all $n&gt;1$ and concludes that the recurrence is $O(n^{2})$ which is not correct.
So what am I missing?
The error is that $c(n-1)^2 + n^2 = cn^2 - 2cn + c +n^2 \leq (c+1)n^2$, so the constant $c$ is in fact no constant, since it grows with every step.
So you get that when $n$ increases by 1, $c$ also does, so you have $O(n) \cdot n^2$, so $O(n^3)$.