Finding explicit formula for recursive relation

The characteristic equation $x^2-\frac{2}{3}x-\frac{1}{3}=0$ has two roots: 1 and $-\frac{1}{3}$.

$$ R_{n+1} + \frac 13 R_n = R_n + \frac 13 R_{n-1} = \cdots = R_1 + \frac{1}{3} R_0 = \frac{17}{30} \tag 1 $$

$$ R_{n+1} - R_n = -\frac{1}{3} (R_n-R_{n-1}) =\cdots = (-\frac 13)^n (R_1-R_0) = -\frac{(-1)^n}{10 \cdot 3^n}\tag 2 $$

(1)-(2) $$ R_n=\frac{3}{4}\left(\frac{17}{30}+\frac{(-1)^n}{10\cdot 3^n}\right). $$

Please check my post Show that for every positive integer $ f_n=\frac{\left ( \frac{1+\sqrt5}{2} \right )^n-\left ( \frac{1-\sqrt5}{2} \right )^n}{\sqrt5}$

The above method does not come from nowhere. For a homogeneous second order linear difference equation $$a_{n+2}-b a_{n+1} + c a_n=0 \tag 3$$ its characteristic equation is $f(x)=x^2-bx+c=0$. (3) can be written in the following form: $$ f(\mathbb{E})a_n=(\mathbb{E}^2-b\mathbb{E} + c)a_n=0 \tag 4 $$ where $\mathbb{E}$ is the forward shift operator such that $\mathbb{E} a_n=a_{n+1}, \mathbb{E}^2 a_n=a_{n+2}$.

Lemma: The solution to $(\mathbb{E}-\lambda)a_n=0$ is $a_n=\lambda^n a_0.$

This is trivial because $(\mathbb{E}-\lambda)a_n=0 \Rightarrow a_{n+1} = \lambda a_n$ which means $a_n$ is a geometric sequence.

Suppose $f(x)=0$ has two distinct roots $r, s$. Then $b=r+s, c=rs$ via Vieta's formulas. Then (3) and (4) become the following, respectively

$$a_{n+2}-(r+s)a_{n+1}+rs a_n=0,\tag 5$$ $$f(\mathbb{E})a_n=(\mathbb{E}-r)(\mathbb{E} - s)a_n=0. \tag 6$$

In the following table you will see that the "shortcut" method is simply a factorization of the characteristic equation in terms of $\mathbb{E}$.

$$ \begin{array}{lcl} a_{n+1} - s a_n = r(a_n-sa_{n-1}) & | & (\mathbb{E}-r) (\mathbb{E}-s)a_n=0\\ \Rightarrow \color{red}{a_{n+1} - s a_n = r^n (a_1-s a_0)} & | & \Rightarrow \color{red}{(\mathbb{E}-s)a_n = r^n (\mathbb{E}-s)a_0} \text{ via Lemma} \\ a_{n+1} - r a_n = s(a_n-ra_{n-1}) & | & (\mathbb{E}-s) (\mathbb{E}-r)a_n=0\\ \Rightarrow \color{blue}{a_{n+1} - r a_n = s^n (a_1-ra_0)} & | & \Rightarrow \color{blue}{(\mathbb{E}-r)a_n = s^n (\mathbb{E}-r)a_0} \text{ via Lemma} \\ \end{array} $$

Subtracting the blue equation from the red, you get $$ a_n=\frac{a_1-s a_0}{r-s} r^n - \frac{a_1-r a_0}{r-s} s^n $$

Solution with duplicate roots

There is also a shortcut. If $f(x)=(x-\lambda)^2$, or $$a_{n+1} - 2\lambda a_n + \lambda^2 a_{n-1}=0.$$

If $\lambda=0$ it's trivial: $a_n=0$. Otherwise $\lambda \neq 0$, then $$\frac{a_{n+1}}{\lambda^{n+1}} - 2 \frac{a_n}{\lambda^n} + \frac{a_{n-1}}{\lambda^{n-1}}=0 \Rightarrow \frac{a_{n+1}}{\lambda^{n+1}} - \frac{a_n}{\lambda^n} = \frac{a_n}{\lambda^n} - \frac{a_{n-1}}{\lambda^{n-1}} = \cdots =\frac{a_1}{\lambda} - a_0$$

So $\frac{a_n}{\lambda^n}$ is an arithmetic sequence, $$ \frac{a_n}{\lambda^n}=\frac{a_0}{\lambda^0}+n\left( \frac{a_1}{\lambda} - a_0\right) \Rightarrow a_n = \lambda^n(na_1/\lambda-(n-1) a_0). $$

Other examples

Some non-homogeneous linear difference equations can be converted to homogeneous higher order ones.

Example 1: Recurring Sequence with Exponent

Example 2: $a_n=3a_{n-1}+1$.

For this one, although we can convert to $a_{n+1} - 3a_{n} = a_n-3 a_{n-1}$, it's easier to do the following: $a_n + \frac 12 =3a_{n-1}+\frac{3}{2} = 3 (a_{n-1} + \frac 12) \Rightarrow a_n+\frac 12 = 3^n (a_0+\frac{1}{2}).$

Example 3 (a higher order example illustrating the use of forward shift operator): Is it possible to solve this recurrence equation?