# Solving recurrence T(n) = T(n - 1) + n^2 using substitution method.

I am trying to solve a recurrence using substitution method (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 guess that $$T(n) = O(n^3)$$, so:
$$T(n) = T(n \space - \space 1) + n^2 \le c(n - 1)^3 + n^2\\ c(n - 1)^3 + n^2 = cn^3 - 3cn^2 + 3cn - c + n^2$$

then I continued like this:
$$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)$$, but I want to know if my proof 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.

EDIT: Let's notice that: $$3cn^2 - 3cn + c - n^2 = n^2(3c - 1) - 3cn + c \ge 0$$ so, all I need to do is to solve this quadratic inequality in order to find for which c values is verified.
Now, I have to calculate the discriminant to check if this inequality has solutions, so: $$(-3c)^2 - 4(3c - 1)(c) = 9c^2 - 12c^2 - 4c = -3c^2 - 4c = c(3c + 4)$$

Only when the discriminant is greater than zero, the inequality has solutions, and in this case: $$3c + 4 > 0\\ 3c > -4\\ c > -\frac{4}{3}$$

From this result, it's proven that $$T(n) = O(n^3), \space \forall c > -\frac{4}{3}$$

• One question, what is substitution method? I can't help you if I don't know what method are you using. Commented Jun 6, 2022 at 16:46
• Substitution method is a solving recurrences method that relies on the induction principle. This method is used to prove upper/lower bounds by induction, just we said in the comments in your answer. For further information, I guess it would be better if you google it. Commented Jun 6, 2022 at 16:56

To solve the recurrence exactly, you need to assume a more general ansatz: $$T(n) = An^3+Bn^2+Cn.$$ Substitution yields: $$An^3+Bn^2+Cn = A(n-1)^3+B(n-1)^2+C(n-1) + n^2.$$ If we let $$n = 1,2,3$$, we get the system of equations $$A+B+C = 1,$$ $$7A+3B+C = 4,$$ $$19A+5B+C = 9.$$
• you are introducing another constant $k$ into your solution. I'm not sure what this represents.
• In the second line of you inequalities, you should have a negative: $-c/n$ on the right side.