Show that equation (15.4) follows from equation (15.3) and the initial condition \(T(0) = 1\).

For reference, equation 15.3 states:

\[T(n) = 1 + \sum^{n-1}_{j=0} T(j)\]

and we want to prove the claim of equation 15.4 that \(T(n) = 2^n\). Suppose \(n \ge 1\) and consider \(T(n-1)\):

\[T(n-1) = 1 + \sum^{n-2}_{j=0} T(j)\]

If we subtract \(T(n-1)\) from \(T(n)\), everything cancels out except for the final term of the summation which is present in \(T(n)\) but not in \(T(n-1)\):

\[\begin{align*} T(n) - T(n-1) &= T(n - 1) \\ T(n) &= 2T(n-1) \end{align*}\]

The pattern is easy to observe:

\[T(1) = 2T(0) = 2 \cdot 1 = 2\] \[T(2) = 2T(1) = 2 \cdot 2 = 4\] \[T(3) = 2T(2) = 2 \cdot 4 = 8\] \[\vdots\] \[T(n) = 2^n\]

From another angle, let’s assume \(T(j) = 2^j\) for all \(0 \le j \le n-1\). Then by (A.5) we have:

\[\sum^{n-1}_{j=0} T(j) = \sum^{n-1}_{j=0} 2^j = \frac{2^{n+1-1} - 1}{2-1} = 2^n - 1\]

And so:

\[T(n) = 1 + \sum^{n-1}\_{j=0} T(j) = 1 + (2^n - 1) = 2^n\]

Since \(2^0 = 1\) the base case of T(0) = 1 holds and therefore this claim is also proved by induction.