Formal mathematical resolution for Recurrence Relations

Question

let's suppose we've got a simple Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases} $$

At lesson we've resolved it, but I tried two other ways of resolution, and I would like to ask you if they're right and which, among all, is the most formal way to resolve it.

Method 1

Drawing the recurrence tree (whose each node has only one child), we see that its height is $n$ and each node receives as input $n-i$, where $i$ is its level. So each node costs $\Theta(n-i)$. Hence the total cost is $$T(n) = \sum_{i=0}^{n-1}\Theta(n-i)$$

Method 2

We see that the cost of each node is $\Theta(n-i)$ which is a $\Theta(n)$, so the total cost is $$T(n) = \sum_{i=0}^{n-1}\Theta(n)$$

Is what I did mathematically right? Even if in this example it looks trivial that it is right, then why when we have an algorithm that equally divides a problem in two equal-size subproblems (e.g. mergesort), the CLRS Book writes that each subproblem costs $\Theta(\frac{n}{2^i})$ but does not "simplify" it into $\Theta(n)$? So their final sum would be $\sum_{i=0}^{h}\frac{n}{2^i}$ and not $\sum_{i=0}^{h}\Theta(n)$ like I would do, since $\Theta(\frac{n}{2^i}) \in \Theta(n)$.

In this case it'd look like each node costs the same as its parent, which obviously can't be, but it is mathematically right.

Method 3

In Method 2 we said that each node costs locally $\Theta(n)$, and $n$ is the value we call the first recursive call with. But when $n=1$, its cost is $1$, so we should write $$T(n) = 1+\sum_{i=0}^{n-2}\Theta(n)$$

When $n=2$, its cost is $\Theta(2) = \Theta(1)$ and not $\Theta(n)$ (remember that this $n$ is the value of the first rec. call when we resolve the summation). But this would apply even when $n=3, n=4, ...$ So I'd write it as $$T(n) = \sum_{i=0}^{k}\Theta(1) + \sum_{i=1}^{n-k}\Theta(n)$$ meaning that there are a constant number of nodes that cost $\Theta(1)$ and the others cost depending on the value of $n$.

I do not know which one is the most formal way of resolving these relations. In all of these methods seem that there's something off, something not formal.

Answer 1

Let me make the following suggestion: get rid of asymptotic notation.

Here is how to do that. Your recurrence relation is really the following: $$ T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(n-1) + f(n) & \text{otherwise}, \end{cases} $$ where $f(n) = \Theta(n)$. Since $f(n) = \Theta(n)$, there are $c,C,N > 0$ such that $cn \leq f(n) \leq Cn$ for all $n \geq N$. If we assume that $f(n) > 0$ for all $n$, then we can assume that $N = 1$ (otherwise, the following needs to be slightly modified). Now define a new recurrence relation, depending on a parameter $\gamma$: $$ T_{\gamma}(n) = \begin{cases} 1 & \text{if } n = 1, \\ T_\gamma(n-1) + \gamma n & \text{otherwise}. \end{cases} $$ A simple proof by induction shows that $$ T_c(n) \leq T(n) \leq T_C(n) $$ for all $n$. Hence it suffices to analyze $T_\gamma(n)$. In fact, we can calculate $T_\gamma(n)$ exactly: $$ T_\gamma(n) = 1 + \sum_{m=2}^n \gamma m = 1 + \gamma \frac{(n-1)(n+2)}{2}. $$ From here it is easy to deduce that $T(n) = \Theta(n^2)$.

I suggest now repeating your various methods, applying them directly to $T_\gamma$. Check which of them still works in this more concrete setting. Of course, if a method doesn't seem to work for $T_\gamma$, then in fact it didn't work already for the original recurrence $T$.

Answer 2

Formaly, for all $n>N$,

$$T(n-1)+c_0n\le T(n)\le T(n-1)+c_1n$$

If we expand the right inequality, $$T(n)\le T(n-1)+c_1n\le T(n-2)+c_1n+c_1(n-1)\le\cdots \le T(N)+c_1\sum_{i={N+1}}^ni\\ =T(N)+c_1\frac{n^2+n-N^2-N}2.$$

We can repeat the reasoning with the left inequality. In the end, $T(n)=\Theta(n^2-n-N^2-N)=\Theta(n^2)$.