Solving a simple recurrence. This isn't a homework question, but it is a problem in my textbook. 
Given $T(n) = T(n-1) + n$, show that $T(n) = O(n^2)$
My approach:
Given $T(n) = T(n-1)$
Need to show $T(n) = cn^2$, where $c > 0$
Substitute:
$\begin{eqnarray*}
T(n) & \le & c(n^2 - 1) + n^2\\
& \le & cn^2 - c + n^2\\
& \le & cn^2 + n^2 - c\\
& \le & n^2(c+1) - c\\
& \le & O(n^2)
\end{eqnarray*}$
Is this the correct approach? Assuming there will be some constant that provides an upper bound.
 A: My approach would be simply to solve the recurrence: it’s not hard to see and to prove by induction that $$T(n)=T(0)+\sum_{k=1}^nk=T(0)+\frac{n(n+1)}2=\frac12n^2+\frac12n+T(0)\;,$$ and one can then appeal to the standard result that a polynomial of degree $k$ is $O(n^k)$. If you don’t have that result available, let $C=\max\left\{\frac12,|T(0)|\right\}$, and note that
$$|T(n)|=\left|\frac12n^2+\frac12n+T(0)\right|\le C(n^2+n+1)\le 3Cn^2$$
for $n\ge 1$.
I don’t follow your approach. If I were to do something along those lines, I’d assume that $T(k)\le ck^2$ for $k<n$. Then 
$$\begin{align*}
T(n)&=T(n-1)+n\\
&\le c(n-1)^2+n\\
&=cn^2-2cn+1+n\\
&=cn^2-(2cn-n-1)\\
&=cn^2-\big((2c-1)n-1\big)\;.
\end{align*}$$
You want to be sure that $T(n)\le cn^2$, so you want to be sure that $(2c-1)n-1\ge 0$. This will be the case provided that $$c\ge\frac12\left(\frac1n+1\right)\;.\tag{1}$$
The righthand side of $(1)$ is a decreasing function of $n$, so its maximum value is $1$, when $n=1$. Thus, there are two constraints on $c$: it must be at least $1$ to ensure that $(2c-1)n-1\ge 0$ for all $n\ge 0$, and it must be big enough so that $T(1)\le c$. Taking $c=\max\{1,|T(1)|\}$ does the job.
A: To prove that $T(n) = T(n-1) + n$ is $O(n^2)$ we just need to show that there's some scaling constant $c$ and some point $N$ such that for all $n>N,$ $T(n) < c n^2$.
We could do this by induction: If $T(n-1) < c n^2$ then $T(n) = T(n-1) + n < c n^2 + 2 c n + c$ as long as $c \ge 1/2$, and this happens for every $n > 0$ (given that $c > T(0)$) so we've proved that $T(n)$ is $O(n^2)$ by the pair $c=1/2+|T(0)|,N=0$.
A: Let's suppose we're starting with $n=0$. I claim that for all $n\ge 0$ we have $$T(n)=T(0)+\frac{n^2+n}2.$$
For $n=0$, this holds trivially by substitution. Suppose that it holds for some $n$. Then by our recurrence relation and the hypothesis, $$T(n+1)=T(n)+n+1=T(0)+\frac{n^2+n}2+\frac{2n+2}2=T(0)+\frac{n^2+2n+1}2+\frac{n+1}2=T(0)+\frac{(n+1)^2}2+\frac{n+1}2=T(0)+\frac{(n+1)^2+(n+1)}2,$$ so the claim holds by induction. Can you get the rest of the way from there?
A: Let us think of our sequence as $T(1), T(2), T(3), \dots$. I think you are trying to prove by induction that there is a $c$ such that $T(n)\lt cn^2$ for all $n$. There certainly is a $d$ such that $T(1)\lt d(1^2)$. Let $c=\max(d,1)$. 
Assume by way of induction hypothesis that $T(n-1)\lt c(n-1)^2$. Then
$$T(n)=T(n-1)+n\lt c(n-1)^2+n =cn^2-2cn+n+1.$$
 But $c\ge 1$, and therefore
$-2cn+n+1\le -2n+n+1=1-n\le 0$, and therefore 
$$T(n)\lt cn^2.$$  
