I am having great difficulties in solving (and more generally understanding) the process of solving recurrence relations.
I will only consider the linear first-order and second-order recurrences.
There are different methods and some are mentioned throughout my lectures:
- Solving by iteration (repeatedly plugging and chugging the recurrence formula until a pattern suddenly appears). The closed formula is then verified using induction.
- Solving by finding characteristic roots.
- Solving using generating functions.
I will focus on the first and second methods, namely iteration and characteristic roots.
Iteration is basically guessing the closed formula, it can be very simple for simple recurrence.
Characteristic roots is used for second-order recurrences which can be harder to guess.
There is now a method called telescoping, basically first-order linear recurrences telescope to a simple sum. However, I cannot understand how to use it.
Taking the example $\begin{cases}u_0&=1\\u_{n+1}&=1.5u_n + 1\end{cases}$
How can I telescope this sequence in order to find the closed formula?
Best Answer
To find $u_n$, apply $u_{k}=1.5u_{k-1}+1$ for all $k$ from $n$ to $1$, multiplied by appropriate powers of $1.5$:
$u_n-1.5u_{n-1}=1$
$1.5u_{n-1}-1.5^2u_{n-2}=1.5$
$1.5^2u_{n-2}-1.5^3u_{n-3}=1.5^2$
. . . (these dots mean do the same thing for $k$ from $n-3$ to $3$ ) ...
$1.5^{n-2}u_2-1.5^{n-1}u_1=1.5^{n-2}$
$1.5^{n-1}u_1-1.5^nu_0=1.5^{n-1}$.
Adding these up (telescoping),
$u_n-1.5^nu_0=1+1.5+1.5^2+\dots+1.5^{n-2}+1.5^{n-1} .$
$u_n=1+1.5+1.5^2+\cdots+1.5^{n-2}+1.5^{n-1}+1.5^n=\dfrac{1.5^{n+1}-1}{1.5-1}.$