5
$\begingroup$

How do I solve the following recurrence relation?

$$ T(n) = 1 + \sum_{j=0}^{n-1} T(j). $$

I thought of solving it by generating its recursion tree. I found that the height of the tree would be equal to $n$ but wasn't able to find the cost of each level.

$\endgroup$
14
$\begingroup$

Here are several ways to solve your recurrence relation.

Guessing

Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this guess, you can verify it by summing the appropriate geometric series: if $T(m) = 2^m$ for $m < n$ then

$$ T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{n-1} 2^m = 1 + (2^n-1) = 2^n. $$

Computing the first few values

Another approach which is very useful is to compute a few values of the sequence: $$ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... $$ If we're lucky, as in this case, we might spot a pattern. If not, it's always a good idea to consult the on-line encyclopedia of integer sequences. A quick search would reveal the sequence A000079.

Creative telescoping

In the method of creative telescoping, we try to find a combination of terms that results in major cancellation. In our case, we can try $T(n+1)-T(n)$:

$$ T(n+1)-T(n) = \sum_{m=0}^n T(m) - \sum_{m=0}^{n-1} T(m) = T(n), $$ and so $T(n+1) = 2T(n)$. Unrolling this rule, we deduce $T(n) = 2^n T(0) = 2^n$.

Back-substitution

Another way to look at the preceding trick is to try to "back-substitute" the recurrence inside itself:

$$ T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{n-2} T(m) + T(n-1) = 2T(n-1), $$

from which we can proceed as before.

Generating series

A very general method is that of generating series. Let $G(x) = \sum_{n=0}^\infty T(n) x^n$. Since $1/(1-x) = \sum_{n=0}^\infty x^i$, multiplying by $1/(1-x)$ is like computing "running sums": $$ \frac{G(x)}{1-x} = \sum_{n=0}^\infty \sum_{m=0}^n T(m) x^n = \sum_{n=0}^\infty (T(n+1)-1) x^n = \\ \frac{G(x)-T(0)}{x} - \sum_{n=0}^\infty x^n = \frac{G(x)-1}{x} - \frac{1}{1-x}. $$ From this it is not hard to deduce $$ G(x) = \frac{-1/x-1/(1-x)}{1/(1-x)-1/x} = \frac{-(1-x)-x}{x-(1-x)} = \frac{1}{1-2x} = \sum_{n=0}^\infty 2^nx^n, $$ and so $T(n) = 2^n$.

Recursion tree

It is also possible to deduce the value of $T(n)$ using a recursion tree. Each path in the recursion tree for $T(n)$ corresponds to a sequence of decreasing numbers $n_0 = n, \ldots, n_\ell$, where $n_\ell \geq 0$ (possibly $\ell = 0$); this is because all leaves are labeled by $1$. The set of possible decreasing sequences is in one-to-one correspondence with subsets of $\{n-1,\ldots,0\}$, because once we know which numbers appear, we also know their order. The number of subsets of $\{n-1,\ldots,0\}$ is exactly $2^n$.

$\endgroup$
  • 2
    $\begingroup$ I really appreciate your experience. $\endgroup$ – Navjot Waraich Mar 28 '18 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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