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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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|cite|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|cite|improve this answer

Your Answer


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.