# 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>0$$ for all $$n>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)$$.
• You can think of it that way, but I think if you don't use the Master Theorem, then the best way is to unfold the recurrence or look at how it grows with each step. If you know that some recursive equation is $O(f)$, then you can try proving it the way you tried, but make sure that constants are actually constants. Dec 7, 2020 at 13:12
• Well, if we are talking Computer Science, then usually recursive relations describe the running time of an algorithm, and so they should be positive. Saying that something can be a function in $n$ but be $O(1)$ is kinda pointless, because if something is $O(1)$, then it is a constant, like $3$, but the number $3$ can be called a function in any argument. Dec 7, 2020 at 16:44