1) Solve the recurrence relation

$$T(n)=\begin{cases} 2T(n-1)+1,&\text{if }n>1\\ 1,&\text{if }n=1\;. \end{cases}$$

2) Name a problem that also has such a recurrence relation.

The answer I got somewhere is here:

Here $T_0=0,T_n-2T_{n-1}=1$ for $n=1,2,\dots$

Multiply by $z^n$ and sum over $n\ge 1$, we get $(A(z)-T_0)-2zA(z)=\dfrac{z}{1-z}$

$\therefore\qquad A(z)=\dfrac{z}{(1-2z)(1-z)}=\dfrac1{1-2z}-\dfrac1{1-z}=\sum\limits_{n\ge 0}2^nz^n-\sum\limits_{n\ge 0}z^n$.

Thus $T_n=2^n-1$.

I'm still in the process of understanding how to solve recurrence relations.. and I'm seeing that there's multiple methods to solving recurrence relations in general. So my question is, is there multiple ways to solve this? If so, can someone state the answer? Also, how do I know what method to use when solving these recurrence relations? thanks

EDIT: did some reading, the first method i'm reading about is mathematical induction.. i'm getting the impression that i can prove that the equation is 2N-1.. so can I solve it this way too?

Also, for the 2nd question, I have Towers of Hanoi, are there any other examples someone can maybe list? thanks

  • $\begingroup$ For example noticing that $T(n)=2T(n-1)+2-1\ \ $ so that $T(n)+1=2(T(n-1)+1)\ \ $. Use the change of variable $U(n)=T(n)+1\ \ $ to conclude... (promised, I didn't see the answer at least consciously !). The change of variable trick is often useful for recurrences. $\endgroup$ – Raymond Manzoni Feb 5 '12 at 19:07
  • $\begingroup$ thanks, keeping it in mind as i go along reading right now $\endgroup$ – user1189352 Feb 5 '12 at 19:37

Yes, there are many ways to solve this recurrence. The method that you found uses generating functions and is towards the sophisticated end. Here are three others.

(1) Guess and prove. Calculate the first few terms of the sequence:

$$\begin{array}{r|rr}n&1&2&3&4&5&6\\ T(n)&1&3&7&15&31&63 \end{array}$$

The numbers in the bottom row should look familiar: they’re one less than consecutive powers of $2$. Thus, you might at this point guess that in general $T(n)=2^n-1$. Of course, now you have to prove your guess. This typically requires a proof by induction. Getting the induction off the ground (i.e., checking the base case) is easy: $T(1)=1=2^1-1$. Now you need to show that if $T(n)=2^n-1$ is true when $n=k$, it’s also true when $n=k+1$.

Assume as your induction hypothesis that $T(k)=2^k-1$ for some $k\ge 1$. By the definition of $T$ you know that $T(k+1)=2T(k)+1$. Your induction hypothesis tells you that $T(k)=2^k-1$, so $T(k+1)=2(2^k-1)-1=2\cdot2^k-2+1=2^{k+1}-1$, which is exactly what we wanted. It follows by induction that $T(n)=2^n-1$ for all $n\ge 1$.

Added: It isn’t always so easy to guess the right formula. As Gadi A reminds me, there is a wonderful tool available to help with this, the On-Line Encyclopedia of Integer Sequences, known as OEIS. If you search it for a sequence containing $\langle 1,3,7,15,31,63\rangle$, you’ll get 29 matches, of which the first, A000225, turns out to be the right one for this problem. From the COMMENTS section of the entry:

Also solutions (with minimum number of moves) for the problem of Benares Temple, i.e. three diamond needles with n discs ordered by decreasing size on the first needle to place in the same order on the third one, without ever moving more than one disc at a time and without ever placing one disc at the top of a smaller one.

(2) Unwind the recurrence. Imagine that $n$ is a fairly large number, and start calculating $T(n)$ in terms of earlier and earlier terms of the sequence until you spot a pattern:

$$\begin{align*} T(n)&=2T(n-1)+1\\ &=2\big(2T(n-2)+1\big)+1\\ &=2^2T(n-2)+2+1\\ &=2^2\big(2T(n-3)+1\big)+2+1\\ &=2^3T(n-3)+2^2+2+1\\ &\qquad\qquad\qquad\vdots\\ &=2^kT(n-k)+2^{k-1}+2^{k-2}+\dots+2+1\tag{1}\\ &=2^kT(n-k)+\sum_{i=0}^{k-1}2^k\;.\tag{2} \end{align*}$$

Now plug $k=n-1$ into $(2)$ to get $$\begin{align*}T(n)&=2^{n-1}T(1)+\sum_{i=0}^{n-2}2^i\\ &=2^{n-1}+\big(2^{n-1}-1\big)\\ &=2^n-1\;, \end{align*}$$

where I used the formula for the sum of a geometric series to evaluate the summation.

If you use this approach, you should then go on to prove the formula by induction, just as in the previous method, because the formula in $(1)$ was a guess $-$ a very solid guess, but still a guess requiring proof.

Another point to notice here is that the last step would have been very slightly easier if we’d backtracked the sequence by calculating $T(0)$ from $T(1)$: $T(0)=\frac12\big(T(1)-1\big)=0$. Then we could have substituted $k=n$ into $(2)$ to get the desired result directly.

(3) Turning the non-homogeneous recurrence into a homogeneous one by a change of variable. Let $S(n)=T(n)+d$ for some as yet unknown $d$. Then $T(n)=S(n)-d$, and the recurrence can be rewritten as

$$\begin{align*} S(n)-d&=\begin{cases}2\big(S(n-1)-d\big)+1,&\text{if }n>1\\ 1-d,&\text{if }n=1 \end{cases}\\\\ &=\begin{cases} 2S(n-1)-2d+1,&\text{if }n>1\\ 1-d,&\text{if }n=1\;. \end{cases} \end{align*}$$

Move the constants to the righthand side in the recurrence: $$S(n)=2S(n-1)-d+1\;.$$ Thus, if we set $d=1$, we get rid of the constant term: $$S(n)=2S(n-1)\;.$$ This is just exponential growth: $S(n)$ doubles with each increase of $1$ in $n$. And $$S(1)=T(1)+d=1+1=2=2^1\;,$$ so it’s very easy to see that $S(n)=2^n$ for every $n\ge 1$. Finally, $T(n)=S(n)-d=2^n-1$.

For your second question, I could cook up other examples, but the Tower of Hanoi problem is by far the best known satisfying this recurrence.

  • 1
    $\begingroup$ wow thank you so much for the indepth answer. going to be studying this one for a while, i appreciate the extra examples to help me make sure i grasp this too. tyvm!!! $\endgroup$ – user1189352 Feb 5 '12 at 19:39
  • 1
    $\begingroup$ You can show your appreciation by upvoting ... +1 $\endgroup$ – ldog Feb 5 '12 at 19:49
  • $\begingroup$ A wonderful answer. It might be worthwhile to mention the OEIS as an effective "real life" tool for the "guess and prove" method. $\endgroup$ – Gadi A Feb 5 '12 at 19:50
  • $\begingroup$ @Gadi: Thanks; I can’t believe that I didn’t think of that, considering how often I’ve used it! $\endgroup$ – Brian M. Scott Feb 5 '12 at 20:05
  • $\begingroup$ "If you search it for a sequence containing $\{1,3,7,15,31,64\}$": I bet you meant $63$. $\endgroup$ – robjohn Feb 5 '12 at 21:29

Add $1$ to both sides of the recurrence to get $$ T(n)+1 = 2(T(n-1)+1)\tag{1} $$ Thus, $T(n)+1$ simply doubles with each increase in $n$. Thus, $$ T(n)+1=c\cdot2^n\tag{2} $$ Plugging $T(1)=1$ into $(2)$, we get that $c=1$. Therefore, we get the solution $$ T(n)=2^n-1\tag{3} $$

I see that the method I am describing is simply a rewording of $(3)$ from Brian M. Scott's answer, but I will leave it as it might prove simpler to read before jumping into Brian's rather extensive answer.

  • $\begingroup$ the simplicity is much much appreciated, as this is still all kinda complicated to me ;D $\endgroup$ – user1189352 Feb 5 '12 at 20:13

The method you gave is a standard way to solve such relations using generating functions. You can also use a somewhat brute-force (but effective) method: "Open up" the relation until you see the pattern:

$$T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=4T(n-2)+(1+2)$$ $$=8T(n-3)+(1+2+4)=16T(n-4)+(1+2+4+8)=\dots=$$ $$2^kT(n-k)+(1+2+\dots+2^{k-1})=\dots=1+2+\dots+2^{n-1}=2^n-1$$

The last transition is from the standard formula for geometric sums.

However, in general generating functions are much more effective.

  • $\begingroup$ thank you! still studying it right now but i think i like this technique, tyvm $\endgroup$ – user1189352 Feb 5 '12 at 19:37

Yet another technique (definite overkill here) is what Knuth calls the repertoire method: Write your recurrence as:

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

Look for functions that give something reasonable when applying $T(n + 1) - 2 T(n)$. I.e., try $T_1(n) = 2^n$, that gives $T_1(n + 1) - 2 T_1(n) = 2^{n + 1} - 2 \cdot 2^n = 0$. Another try might be $T_2(n) = 1$, which gives $T_2(n + 1) - 2 T_2(n) = 1 - 2 \cdot 1 = -1$.

Once you have a wide enough range of options, look at linear combinations of your attempts (the equation is linear!) that solve the equation and satisfy initial conditions. Here look at $c_1 T_1(n) + c_2 T_2(n)$, thus $c_1 \cdot 2 + c_2 \cdot 1 = 1$ for initial conditions, from the equation $c_1$ is arbitrary, $c_2 = -1$. You get $c_1 = 1$, and the solution is $T(n) = 2^n - 1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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