Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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)$.

share|improve this answer

$$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$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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