If $T(n) = 1 + \sum_{k=0}^{n-1} T(k),$ then $T(n) = 2^n.$

Question

Question: Let $T(n)$ be a running time that satisfies the recurrence $$T(n) = 1 + \sum_{k=0}^{n-1} T(k) \quad \text{and}\quad T(0) = 1.$$ Show that $T(n) = 2^n.$

The recurrence above can be obtained in CLRS's Introduction to Algorithms, $3$rd edition, page $364,$ where the authors discuss rod-cutting problem using Recursive top-down implementation.

Does anyone how to obtain the solution for the recurrence of $T(n)$ above?

Answer 1

Hint:

Set $n=m,m-1$ in $$T(n) = 1 + \sum_{k=0}^{n-1} T(k).$$

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

$$T(m)-T(m-1)=?$$

$$\implies T(n)=2^{n-r}T(r)$$

Set $r=0,1$ based on the initial case

Answer 2

There are two common methods to solve these kinds of problems; backward substitution method and forward substitution method. Most of the time the backward is more helpful. This one easy with forward.

$$T(n) = 1 + \sum_{k=0}^{n-1} T(k) \quad \text{and}\quad T(0) = 1.$$ Let us expand it;

$T(n) = T(n-1)+ T(n-2) + \cdots + T(1) + 1$ and if you look at from bottom

\begin{align} T(0) & = 1 & &=1 & & =1\\ T(1) & = T(0) +1 & &= 1 + 1 & &= 2\\ T(2) & = T(1) + T(0) +1 & &= 2 + 1 + 1 & &= 4 \\ T(3) & = T(2) + T(1) + T(0) +1& &= 4 + 2 + 1 + 1 & &= 8 \\ T(4) & = T(3) + T(2) + T(1) + T(0) +1 & &= 8 + 4 + 2 + 1 + 1 & &= 16\\ \end{align}

After some initial values if you see a pattern then you can set up your claim, here $T(n) = 2^{n}$, and the next step is proving this claim by induction...

Note that CLRS' Introduction to Algorithms mostly uses backward substitution even for the proof of Master Theorem of the analysis of algorithms.