9
$\begingroup$

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

  • 0
    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.2012-02-05
  • 0
    thanks, keeping it in mind as i go along reading right now2012-02-05

3 Answers 3