Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hello and thanks for taking the time to answer my question.

The question is really the title itself. We're studying about solving recurrences using the method of substitution and induction. How can I prove that this is correct?

I would really appreciate your reasoning behind the concepts as opposed to just churning out a solution.

Thank you very much!

share|cite|improve this question
Are you seeking to merely prove the claim, or are you asking how you would discover it if it weren't given to you? What happens, incidentally, when you try the method of substitution or induction? – Hurkyl Jan 15 '13 at 16:35
up vote 3 down vote accepted

The most basic method is to expand the formula. It rarely works, but it is simple enough that is worth checking before proceeding to more complicated stuff.

\begin{align} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &\vdots \\ &= T(0) + 1 + 2 + \ldots + (n-2) + (n-1) + n \\ &= T(0) + \frac{n(n+1)}{2} = O(n^2) \end{align}


EDIT: Added missing $T(0) = O(1)$ term (thanks to Hurkyl).

share|cite|improve this answer
You mean $T(0) + n(n+1)/2$ – Hurkyl Jan 15 '13 at 16:36
This is great thanks dtldarek! I will accept your answer as correct as soon as the minimum required time elapses! How would you determine the lower bound for the same equation? – Peter Jan 15 '13 at 16:40
@Peter This is actually set of equalities, so those work both ways. In fact $T(0) + \frac{n(n+1)}{2} = \Theta(n^2)$. – dtldarek Jan 15 '13 at 16:42
oh okay.. I asked the second question in the comment because as far as I understand it O denotes the upper bound which means that T(n) <= O(n^2) and for Omega it is the opposite. Does this mean that for T(n) = (n-1) + n Big O and Omega are n^2 aswell? – Peter Jan 15 '13 at 16:46
@evinda That depends on the starting conditions, which in the original post were not given. On the other hand, it doesn't matter, as both $T(0)$ and $T(1)$ are constant. In other words, pick the one that is more convenient for you. – dtldarek Mar 7 '15 at 23:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.