# Asymptotic upper bound in Big-O for $T(n)=T(n-1)+3n-5$. Proof using induction

I need to prove using induction Asymptotic upper bound in Big-O for

$$T(n)=T(n-1)+3n-5$$

So I tried expanding

\begin{align} T(n) &= T(n-1) + 3n - 5 \\ &= T(n-2)+ 2(3n-5) \\ &= T(1) + (n-1)(3n-5) \\ &= 3n^2-8n+6 \end{align}

Then I tried proving:

For $n=1$, $T(1)=3-8+6=1$
Assume solution correct for $n \le k-1$, we want to show its correct for $n=k$.

\begin{align} T(k) &= T(k-1)+3k-5 \\ &= 3(k-1)^2-8(k-1)+6+3k-5 \\ &= 3(k^2-2k+1)-8k+8+6+3k-5 \\ &= 3k^2-11k+12 \end{align}

Seems wrong?

-

There's a mistake at $T(n-2)+2(3n-5)$; that has to be $T(n-2)+(3n-5)+(3(n-1)-5)$. Do you want to see a better way to solve the recurrence? Or would you rather work on it a little longer?

EDIT: OP has asked for a better way, so here goes:

We have $$T(k)=T(k-1)+3k-5$$ for all $k$. Summing for $k$ from $1$ to $n$, that's $$\sum_{k=1}^nT(k)=\sum_{k=1}^nT(k-1)+\sum_{k=1}^n(3k-5)$$ Now $T(1),T(2),\dots,T(n-1)$ appear on both sides of the equation, so we cancel them, leaving $$T(n)=T(0)+\sum_{k=1}^n(3k-5)$$ So the question now is, do you know how to evaluate $\sum_{k=1}^n(3k-5)$?

-
I seem to intuitively think of expanding, and if I see any pattern, I could generalize. But I think you are suggesting theres a better way? I am always open to learning it :) ... expanding seems tedious tho ... –  Jiew Meng Feb 5 '13 at 13:21
@JiewMeng Expanding a little bit helps: $$3\sum_{k=1}^n k-\sum_{k=1}^n 5$$ –  Robert Mastragostino Feb 5 '13 at 23:03

If really the question is the one you described in your question, you might try to prove recursively that, for every $n\geqslant1$, $$T(n)\leqslant2n^2+T(1).$$

-