2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Generally, you can use $(-1)^n$ to show the differences between odd and even terms. $\endgroup$ Commented Sep 19, 2016 at 19:06

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I'm afraid this doesn't answer my question. I know how to find the solutions for the even and odd parts separately. I'm wondering how to find the solution for both simultaneously (if it's even possible). I even include the solutions you provide in my post. $\endgroup$ Commented Sep 19, 2016 at 18:22
  • 1
    $\begingroup$ I am still writing my solution, please bear with me a few more minutes. $\endgroup$ Commented Sep 19, 2016 at 18:23
  • 1
    $\begingroup$ @SamratMukhopadhyay: I've added a closed form solution. Regards, $\endgroup$ Commented Sep 19, 2016 at 20:40
  • 2
    $\begingroup$ @MarkusScheuer, yes of course that can be done to obtain a closed form solution, but what I meant to say that really the sequences $a_{2n}$ and $a_{2n+1}$ are independent sequences. $\endgroup$ Commented Sep 20, 2016 at 10:28
  • 1
    $\begingroup$ @SamratMukhopadhyay: Ok, I see. $\endgroup$ Commented Sep 20, 2016 at 10:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.