0

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?

Jiew Meng
  • 4,593

2 Answers2

1

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)$?

Gerry Myerson
  • 179,216
  • 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 05 '13 at 13:21
  • @JiewMeng Expanding a little bit helps:

    $$3\sum_{k=1}^n k-\sum_{k=1}^n 5$$

     – Robert Mastragostino Feb 05 '13 at 23:03
1

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). $$

Did
  • 279,727