1
$\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
    $\begingroup$ Generally, you can use $(-1)^n$ to show the differences between odd and even terms. $\endgroup$ – Ross Millikan Sep 19 '16 at 19:06
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$
  • $\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$ – user170231 Sep 19 '16 at 18:22
  • $\begingroup$ I am still writing my solution, please bear with me a few more minutes. $\endgroup$ – Samrat Mukhopadhyay Sep 19 '16 at 18:23
  • $\begingroup$ @SamratMukhopadhyay: I've added a closed form solution. Regards, $\endgroup$ – Markus Scheuer Sep 19 '16 at 20:40
  • $\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$ – Samrat Mukhopadhyay Sep 20 '16 at 10:28
  • $\begingroup$ @SamratMukhopadhyay: Ok, I see. $\endgroup$ – Markus Scheuer Sep 20 '16 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.