Explicit formula for crossed recursion

Question

When answering this linked question, I ended up with a formula where two sequences are mutually recurrent :

$$ \begin{cases} u_0=0, ~~v_0=1\\ \forall n \in \mathbb{N}^*, ~~u_{n+1} = \frac{11}{12}u_n+\frac1{12}v_n\\ \forall n \in \mathbb{N}^*, ~~v_{n+1} = \frac56v_n+\frac16u_n\\ \end{cases} $$

How to compute the explicit formula for this?

---

Here is what I have found yet (not much):

Let $f$ a function such as

$$ \forall x, y \in \left[0, 1\right], \forall M \in \mathbb{R}^+, ~~f_M(x, y) = \frac1M\left(\left(M-1\right)x+y\right) $$

And we can rewrite our formula as:

$$ \begin{cases} u_{n+1} = f_{12}(u_n, v_n)\\ v_{n+1} = f_6(v_n, u_n)\\ \end{cases} $$

We have similar functions describing how $(u_n)$ and $(v_n)$ behave, but I don't know what to do next. Am I even on the good path? What should I try?

Answer 1

One approach is to rewrite your recurrences in matrix form as

$$\begin{bmatrix}u_{n+1}\\v_{n+1}\end{bmatrix}=\begin{bmatrix}11/12&1/12\\1/6&5/6\end{bmatrix}\begin{bmatrix}u_n\\v_n\end{bmatrix}\;,$$

so that

$$\begin{bmatrix}u_n\\v_n\end{bmatrix}=\begin{bmatrix}11/12&1/12\\1/6&5/6\end{bmatrix}^n\begin{bmatrix}u_0\\v_0\end{bmatrix}=\begin{bmatrix}11/12&1/12\\1/6&5/6\end{bmatrix}^n\begin{bmatrix}0\\1\end{bmatrix}\;.$$

Diagonalize the matrix $$\begin{bmatrix}11/12&1/12\\1/6&5/6\end{bmatrix}\;,$$ and you can calculate the powers very easily to get closed forms for $u_n$ and $v_n$.

Another approach is to add your recurrences to get

$$u_{n+1}+v_{n+1}=\frac{13}{12}u_n+\frac{11}{12}v_n=u_n+v_n+\frac1{12}(u_n-v_n)$$

and subtract them to get

$$u_{n+1}-v_{n+1}=\frac9{12}u_n-\frac9{12}v_n=\frac34(u_n-v_n)\;.$$

Now let $x_n=u_n+v_n$ and $y_n=u_n-v_n$; then

$$x_{n+1}=x_n+\frac1{12}y_n\tag{1}$$

and

$$y_{n+1}=\frac34y_n\;.\tag{2}$$

The recurrence $(2)$ is easily solved: $y_0=-1$, so $y_n=-\left(\frac34\right)^n$. We can substitute this into $(1)$ to find that

$$x_{n+1}=x_n-\frac1{12}\left(\frac34\right)^n\;;$$

this is first-order recurrence whose solution involves only summing a finite geometric series. (I’ve left the result of that calculation in the spoiler-protected block below.)

$x_n=\frac23+\frac13\left(\frac34\right)^n$

Finally, it’s easy to solve the system

$$\left\{\begin{align*} &u_n+v_n=x_n\\ &u_n-v_n=y_n \end{align*}\right.$$

for $u_n$ and $v_n$ once you have $x_n$ and $y_n$.