Solving for Recurrence Function

Question

I was reading the following http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf notes on recurrence relation, page 2.

A recurrence function for the Tower of Hanoi is given by $T(n) = 2T(n-1)+1$ with $T(0)=0$. Steps to find the closed form formula is shown but it is not clear.

Could someone show the steps to find the closed form of some equation, say $T(n) = 2T(n-1)+n$ with $T(0)=1$? The equation could be anything. I just want to learn the steps for it. Or any link to any article with such problem would also be much appreciated.

Answer 1

Dividing the equation by $2^n$ and letting $S_n=T_n/2^n$ we have $$ S_n=S_{n-1}+n/2^n $$ for all $n=1,2,3,...$. Putting $n=0,1,2, 3,... n$ and summing the result and using $T(0)=1$ we get the close form. (It is easy to find the sum $\sum_{k=0}^n k/2^k$).

Answer 2

Generally, for $T(n) = a *T(n-1)+b$

$\begin{align*} T(0) &= T(0)\\ T(1) &= a * T(0) + b\\ T(2) &= a^2 * T(0) + b * (a+ 1)\\ T(3) &= a^3 * T(0) + b * (a^2+a+ 1)\\ &...\\ T(n) &= a^n * T(0) + b * (a^{n-1}+\ldots+a+ 1)\\ &= a^n * T(0) + b \left( \dfrac{a^n-1}{a-1} \right)\\ &= a^n \left( T(0) + \dfrac{b}{a-1}\right)- \left(\dfrac{b}{a-1}\right) \end{align*}$

Which we can prove by induction:

$\begin{align*} a^0 \left( T(0) + \dfrac{b}{a-1}\right)- \left(\dfrac{b}{a-1}\right) &= T(0) + \dfrac{b}{a-1}- \dfrac{b}{a-1}\\ &=T(0)\;\checkmark \end{align*}$

Now suppose

$T(n) = a^n \left( T(0) + \dfrac{b}{a-1}\right)- \left(\dfrac{b}{a-1}\right)$

then

$\begin{align*} T(n+1) &= a *T(n)+b\\ &= a * \left(a^n \left( T(0) + \dfrac{b}{a-1}\right)- \left(\dfrac{b}{a-1}\right)\right)+b\\ &= a^{n+1} \left( T(0) + \dfrac{b}{a-1}\right)- a *\left(\dfrac{b}{a-1}\right)+b\\ &= a^{n+1} \left( T(0) + \dfrac{b}{a-1}\right)- b *\left(\dfrac{a}{a-1}-1\right)\\ &= a^{n+1} \left( T(0) + \dfrac{b}{a-1}\right)- \left(\dfrac{b}{a-1}\right)\;\checkmark \end{align*}$