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
Best Answer
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:
(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.