Let's consider an arithmetico-geometric sequence, that is, defined by a recurrence relation of the form $u_{n+1}=a u_{n}+b$. Express $u_{n}$ as a function of $n$.
First method. Let's try to reduce to a simpler recurrence relation by setting $v_{n}=u_{n}+c$, where $c$ is a complex number to be determined later. The sequence $v_{n}$ satisfies the recurrence relation $v_{n+1}-c=a\left(v_{n}-c\right)+b$, that is, $v_{n+1}=a v_{n}+(1-a) c+b$. By taking $c=\frac{b}{a-1}$, $(v_{n})$ is a geometric sequence with ratio $a$. Therefore, $v_{n}=a^{n} v_{0}$, and $u_{n}=$ $a^{n} u_{0}+\frac{a^{n}-1}{a-1} \cdot b$

Second method. By formally calculating the first few terms of the sequence, we can conjecture that $u_{n}=a^{n} u_{0}+a^{n-1} b+\ldots+a b+b=a^{n} u_{0}+\frac{a^{n}-1}{a-1} \cdot b$. It remains to show by induction that this formula is true for all $n$.

## - 2. Linear Recurrences of Order 2 -

A linear recurrence of order 2 is a recurrence relation of the form $\mathfrak{u}_{n+2}=$ $a u_{n+1}+b u_{n}$. Its characteristic polynomial is the polynomial $\chi(x)=x^{2}-a x-b$.

Theorem 50. - If the polynomial $\chi(x)$ has two distinct complex roots $r_{1}$ and $r_{2}$, then there exist $(\lambda, \mu) \in \mathbb{C}^{2}$ such that for all $n \in \mathbb{N}$, we have $u_{n}=\lambda r_{1}^{n}+\mu r_{2}^{n}$.

- If the polynomial $\chi(x)$ has a double root $r$, then there exist $(\lambda, \mu) \in \mathbb{C}^{2}$ such that for all $n \in \mathbb{N}$, we have $u_{n}=(\lambda+\mu n) r^{n}$

We calculate $\lambda$ and $\mu$ from the first two terms $\mathfrak{u}_{0}$ and $\mathfrak{u}_{1}$.