4

My class and I were introduced to recurrences last week, and we took up this example (see link) in class. Unfortunately I find it really tricky still, and I apologize in advance if this question is...pathetic(?)

Here it is:

From the steps shown class, solving it starts with finding a pattern:

T(n) = 2T(n-1) + 1

=2[2T(n-2) + 1] + 1

=4[2T(n-3) + 1] + 3

=8[2T(n-4) + 1] + 7

I (believe I) understand why 2T(n-1) + 1 is in the square brackets. But I have no idea where the 2, 4, 8 (in the beginning of each) comes from, as with the 1, 3, 7 and the ends.

Anyone would be a life saver to shed some light on this, so I can continue on with practicing and solving other recurrences.

user3428
  • 43

3 Answers3

3

What's happening here is that the recurrence relation is being applied, repeatedly.

We start off, for some $n$, with the fact that $$\tag{1} T(n)=2T(n-1)+1. $$ But, we know that $T(n-1)=2T(n-2)+1$; plugging this in to $(1)$ yields $$\tag{2} T(n)=2(2T(n-2)+1)+1=2^2T(n-2)+2+1. $$ But, we know that $T(n-2)=2T(n-3)+1$; plugging this in to $(2)$ yields $$\tag{3} T(n)=2^2(2T(n-3)+1)+2+1=2^3T(n-3)+2^2+2+1. $$ Let's do one more: we know that $T(n-3)=2T(n-4)+1$, so that $$ T(n)=2^3(2T(n-4)+1)+2^2+2+1=2^4T(n-4)+2^3+2^2+2+1. $$ Do you see a pattern? It certainly looks like for any $k<n$, we have $$ T(n)=2^kT(n-k)+(2^{k-1}+2^{k-2}+\cdots+2+1). $$ IF this expression is true, then in particular taking $k=n-1$ yields $$ \begin{align*} T(n)&=2^{n-1}T(n-(n-1))+(2^{n-2}+2^{n-3}+\cdots+2+1)\\ &=2^{n-1}T(1)+(2^{n-2}+2^{n-3}+\cdots+2+1)\\ &=2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2+1, \end{align*} $$ because $T(1)=1$ by definition. Now, this is a geometric sum and can be simplified to give a nice, closed-form formula for $T(n)$.

Nick Peterson
  • 32,430
2

$$T(n)=2T(n-1)+1\iff T(n)+1=2[T(n-1)+1]$$

Set $\displaystyle T(n)+1=U(n)\implies U(n)=2U(n-1)$ and $U(1)=\cdots$

$\displaystyle\implies U(n)=2^rU(n-r) $ for $1\le r<n$

lab bhattacharjee
  • 274,582
1

It might have helped if they had shown some intermediate steps:

$$\begin{align} T(n)&=2T(n-1)+1\\ &=2[2T(n-2)+1]+1\\ &=4T(n-2)+3\quad\text{(intermediate step)}\\ &=4[2T(n-3)+1]+3\\ &=8T(n-3)+7\quad\text{(intermediate step)}\\ &=8[2T(n-4)+1]+7\\ &=16T(n-4)+15\quad\text{(intermediate step)}\\ &\vdots \end{align}$$

Each intermediate step just expands and collects what's on the line above it.

Barry Cipra
  • 79,832