Geometric Series Transformation - Introduction to Algorithms 15.1-1

Question

For problem 15.1-1 in the Introduction to Algorithms book, the question asks, "Show that equation (15.4) follows from equation (15.3) and the initial condition T(0) = 1

In one of the many solutions on the internet, it shows the following transformation is a geometric series such that:

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

Could someone explain how you know that T(j) is $2^{j}$ in this partial solution I found?

Answer 1

Several versions of the same hint.

• Look at $1, 1+2, 1+2+4, 1+2+4+8, \ldots$. You should see the pattern.

• Look up or remember the formula for the sum of a finite geometric series.

• Think about the largest number you can represent in binary with $n$ bits.

• Try to write down the straightforward induction argument.

Answer 2

It is true for $n=1$ since $$T(1)=1+ \sum_{i=0}^{0} T(i)=1+1=2=2^1$$ Now suppose it is true for $n$, that is $$T(n) = 1 + \sum_{j=0}^{n-1} 2^j=1+\frac{2^n-1}{2-1}=2^n$$ and let's prove it for $n+1$ $$T(n+1)=1+\sum_{j=0}^{n} 2^j=2^n+2^n=2\cdot 2^n=2^{n+1}$$ so the formula is true for any $n\in\mathbb{N}$.