# Solving linear recurrence relations

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:

1. Solving by iteration (repeatedly plugging and chugging the recurrence formula until a pattern suddenly appears). The closed formula is then verified using induction.
2. Solving by finding characteristic roots.
3. 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?

• did you mean $1.5u_{n\color{red}-1}$? – J. W. Tanner Jan 3 '20 at 19:59
• @J.W.Tanner yes. I corrected. – explogx Jan 3 '20 at 20:00

## 2 Answers

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}.$$

• Thank you. Can you add some explanation about the different steps? Also, the three dots represent what? You continue expanding the sum until a pattern appears? – explogx Jan 3 '20 at 20:08
• @gatosec: I edited to add explanation – J. W. Tanner Jan 3 '20 at 20:11
• Why do you multiply by powers of 1.5 specifically? – explogx Jan 3 '20 at 21:21
• I do not understand how do you establish $u_n - 1.5u_{n-1} = 1$ – explogx Jan 3 '20 at 21:24
• $u_n=1.5u_{n-1}+1$ – J. W. Tanner Jan 3 '20 at 21:29

Just a small trick for the general problem of linear recurrence relations.

Consider $$u_n=a u_{n-1}+b \qquad \text{with} \qquad u_0=c$$ Let $$u_n=v_n+k$$ and replace $$v_n+k=a v_{n-1}+a k+b$$ Make $$k=ak+b \implies k=-\frac{b}{a-1}$$ and the equation becomes the simple $$v_n=a v_{n-1}\implies v_n=C\, a^{n-1}\implies u_n=C\, a^{n-1}-\frac{b}{a-1}$$ Now, using the condition $$u_0=c \implies c=\frac C a-\frac{b}{a-1} \implies C=a \left(\frac{b}{a-1}+c\right)$$

• This is the method the French people use, it uses the fixed point to construct a translated sequence using the fact that $u_n-\alpha=k\left(u_{n-1}-\alpha\right)$ where $\alpha$ is the fixed point $f(\alpha)=a\alpha+b$ and $k=a$ – explogx Jan 7 '20 at 11:02
• @gatosec. Guess what ? I am French ! – Claude Leibovici Jan 7 '20 at 11:10