Solving a recurrence with an alternating pattern e.g. do $\mathrm X$, then do $\mathrm Y$; repeat

Question

Here's an example sequence:

$$a_n=\{1, 2, 4, 8, 10, 20, 22, 44, 46, \ldots\}$$

The sequence is constructed by an alternating pattern of doubling and adding $2$. Recursively, this can be written as

$$\begin{cases}a_0=1\\[1ex]a_{2n-1}=2a_{2n-2}&\text{for }n\ge1\\[1ex]a_{2n}=a_{2n-1}+2&\text{for }n\ge1\end{cases}$$

One method I've considered is to split up $a_n$ into two subsequences $b_n$ and $c_n$ to handle the even- and odd-indexed terms individually. Recursively,

$$\begin{cases}b_0=1\\[1ex]b_n=2b_{n-1}+2&\text{for }n\ge1\end{cases}\quad\quad\text{and}\quad\quad\begin{cases}c_0=2\\[1ex]c_n=2(c_{n-1}+2)&\text{for }n\ge1\end{cases}$$

which have solutions $b_n=3\times2^n-2$ and $c_n=3\times2^{n+1}-4$. Therefore one closed form for $a_n$ might be written as $$a_n=\begin{cases}b_k&\text{for }n=2k,\,k\in\mathbb{N}\cup\{0\}\\[1ex]c_k&\text{for }n=2k-1,\,k\in\mathbb{N}\end{cases}$$ Is there some way I can consolidate these two solutions to get a closed form for $a_n$ that's independent of $b_n$ and $c_n$?

More generally, is it possible to find a solution to a recurrence relation for a sequence that's constructed by a periodic pattern without splitting into cases? i.e. do $\mathrm X_1$, then do $\mathrm X_2$, ..., then do $\mathrm X_i$; repeat. To make things easy, suppose $\mathrm X_i$ is a pattern that, in order to get the next term in the sequence, either adds a real number to the preceding term or scales the preceding term by a real number.

Answer 1

Since we can write for $n\geq 0$

\begin{align*} a_{n}&=3\cdot 2^\frac{n}{2}-2\qquad\qquad &n\equiv 0(2)\\ a_{n}&=3\cdot 2^\frac{n+1}{2}-4\qquad\qquad &n\equiv 1(2) \end{align*}

we can put them together via

\begin{align*} a_n=\left(3\cdot 2^\frac{n}{2}-2\right)\cdot\frac{1+(-1)^n}{2} +\left(3\cdot 2^\frac{n+1}{2}-4\right)\cdot\frac{1-(-1)^n}{2}\qquad\qquad n\geq 0 \end{align*}

and simplify the expression.

Answer 2

Note that, $\forall n\ge 0$ $$a_{2n}=2a_{2n-2}+2=2^2a_{2n-4}+2(1+2)=\cdots=2^{n}a_0+2(2^n-1)=3\cdot2^n-2,\\a_{2n+1}=2a_{2n-1}+2^2=2^2a_{2n-3}+2^2(1+2)=\cdots=2^na_1+2^2(2^n-1)=6\cdot 2^n-4$$

This signifies that there is no closed form solution to $a_n$, and indeed the sequence $\{a_n/2^n\}$ has two limit points, $ 3,6$.

In general, let $\{a_n\}$ is evolved by repeating the operations $X_1,\cdots, X_i$ periodically, then, for $n\ge i$. Let the operations $X_1,\cdots,\ X_n$ be a set of linear operations, i.e. scaling or translating the previous, say, $m$ $a_n$'s. Let us define the vector $u_n$ as $u_n=[a_n\ a_{n-1}\ \cdots\ a_{n-m+1}]^T$ Then, each of the $X_l,\ 1\le l\le i$ can be represented by a $m$ dimensional vector and a scalar, which, abusing the notation a little bit, we call $X_l$ and $x_l$ respectively. Let $$A=\begin{pmatrix} X_1^T\\ X_2^T\\ \vdots\\ X_i^T \end{pmatrix}$$ and let $b=[x_1\ x_2\ \cdots\ x_i]^T$. Then the evolution of $u_n$ can be written as $$u_{n}=Au_{n-1}+b$$ where $A$ is a $i\times m$ dimensional matrix. So, we find $$u_n=A^{n-m} u_{i}+(I+A+A^2+\cdots+A^{n-m-1})b$$ Also, if the Singular Value Decomposition of $A$ can be written as $A=U\Sigma V^T$, then, $$u_n=U\Lambda_n V^Tu_i+UD_nV^T b$$ where $$\Lambda_n=\Sigma^{n-m},\ D_n=I+\Sigma+\cdots+\Sigma^{m-n-1}$$This pertains to saying that the sequences $u_{n}, u_{n+1},\cdots, u_{ n+m-1}$ are in general different sequences, and, depending upon the singular values of the $A$ matrix, if they converge, may lead to $m$ different limit points.