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.

I am trying to prove the recurrence $2T(n-1) + 1$ has the bound $\theta(2^{n})$. $T(1) = \theta (1)$

My attempted solution:

\begin{align*} T(n) &= 2T(n-1) + 1 \\ &= 2 \{ 2T(n-2) + 1 \} + 1 \\ &= 2 \{ 2 \{ 2T( n - 3 ) + 1 \} + 1 \} + 1 \\ & \ldots \\ &= 2^{i}T(n-i)+\sum_{i=0}^{k} 2^{i} + 1. \end{align*}

I then proceed to substitute $n-1$ for $i$ which gives me

\begin{align*} & 2^{n-1}T(n-(n-1)) + \sum_{i=0}^{n-1} 2^{i} + 1 \\ &= 2^{n-1}T(n-n+1) + \sum_{i=0}^{n-1} 2^{i} + \sum_{i=0}^{n-1} 1 \\ &= 2^{n-1}T(1) + 2^{n-1+1} + n - 1 \\ &= 2^{n-1}\theta(1) + 2^{n} + n - 1\\ \end{align*}

At this point I can see that $2^{n}$ is the dominating factor, however in the solution hints of my book it states that I should use $i = n$. However when I do that I get $T(0)$.

I suspect there is something wrong with my substitution/unraveling step, however I can't seem to figure it out. Any help would be appreciated

share|improve this question
    
Your fourth step should be $T(n) = 2^k T(n-k) + \sum_{i=1}^k 2^{i-1}$ –  user17762 Mar 3 '11 at 0:26

2 Answers 2

Maybe here?

$$\begin{align*} T(n) &= 2T(n-1) + 1 \\ &= 2 \{ 2T(n-2) + 1 \} + 1 \\ &= 2 \{ 2 \{ 2T( n - 3 ) + 1 \} + 1 \} + 1 \\ & \ldots \\ &= 2^{i}T(n-i)+\sum_{k=1}^{i-1} 2^{k} + 1. \end{align*}$$

Also, $$ \begin{align*} & 2^{n-1}T(n-(n-1)) + \sum_{i=1}^{n-2} 2^{i} + 1 \\ &= 2^{n-1}T(n-n+1) + \sum_{i=1}^{n-2} 2^{i} + 1 \\ &= 2^{n-1}T(1) + 2^{n-1} -1 \\ &= 2^{n-1}\theta(1) + 2^{n-1} - 1\\ \end{align*}$$

share|improve this answer

Your fourth step should be $T(n) = 2^k T(n-k) + \displaystyle \sum_{i=1}^k 2^{i-1}$ and there are a few errors in your manipulation.

A simpler way to go about would be to let $T(n) = f(n) - 1$. Plugging this in the recurrence, we get $$f(n)-1 = 2(f(n-1)-1) + 1$$ i.e. $$f(n) = 2f(n-1)$$ Solving this recurrence is child's play and we get $$f(n) = f(1) 2^{n-1}$$ and hence $$T(n) = f(1) 2^{n-1} - 1 = T(1) 2^{n-1} + 2^{n-1} - 1 $$ since $f(1) = T(1) + 1$

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.