Recurrence equation for $T(n)=T(n-1)+cn$ by substitution (induction)

Question

I was able to solve this relation as described here Solving the recurrence relation $T(n)=T(n-1)+cn$

By the way, my exercises asks also to demostrate by "substitution" and "induction" why the result shall be $T(n) = O(n^2)$

This is what I tried:

$Goal$ We shall demostrate that T(n)<=$O(n^2)$
Where

• T(1) = c' if n=1 (c' is a constant greater than zero)
• T(n) = T(n-1) + cn if n>1 (c is a constant greater than zero)

Thesis: Exists some d>0 such as $T(n) <= dn^2$. d is a positive constant.

Base case (with n=1)
$T(1) = c' <= d(1^2)$ Hence true dor any d>=c'.

Induction hypotesis: the thesis is still true for any m<n.

Equation	Applied hypotesis	Our constraint
$T(n) = T(n-1) + cn $	$<= d(n-1)^2+cn$ $= dn^2-2dn-d+cn$	<= dn^2

Now, solving the equation
$dn^2-2dn-d+cn <= dn^2 $
$-2dn-d+cn <= 0 $
$cn <= 2dn+d $

Then I stuck, I cannot demostrate for d because n is still there, normally I will get some kind of semplification where can I get something like true for all c greater than ...

What am I doing wrong?

Answer 1

You can solve the recurrence like this. We have $$T(1) = T(0) + c.$$ Then $$T(2) = T(1) + 2c = T(0) + c(1 + 2).$$ Then $$T(3) = T(2) + 3c = T(0) + c(1+2+3).$$ When you do this repeatedly, you get that $$T(n) = T(0) + c(1 + 2 + 3 + \dots + n).$$ Can you finish the problem from here?

Answer 2

First, you need to guess one possible value for $d$. To that end, check for the first values of $n$:

• $n=1$: we have $T(1) = c + T(0)$. Therefore, $|T(1)| \leqslant |c| + |T(0)|$.
• $n=2$: we have $|T(2)| = 2c + T(1) = 3c + T(0)$. Therefore, $T(2) \leqslant 2|c| + |T(0)|$.
• $n=3$: we have $T(3) = 3c + T(2) = 5c + T(0)$. Therefore, we have $|T(3)| \leqslant 3|c| + |T(0)|$.

One remarks that, defining $d= 2\max\{|c|,|T(0)|\}$ for instance, we have: $$ \forall n \in \{1,2,3\},\quad |T(n)| \leqslant d n^2. $$

So, now, can you go on from there and show the result by induction with $d=2\max\{|c|,|T(0)|\}$?

(Note that this is just one possible value for $d$, which need not be optimal)