Find the general term of $a_{2k}=pa_k+qa_{k+1},a_{2k+1}=ra_k+sa_{k+1}$

Question

The question

Given that the initial terms $a_1$, $a_2$ and the recursion:

$$ \left\{ \begin{matrix} a_{2k}=pa_k+qa_{k+1}\\ a_{2k+1}=ra_k+sa_{k+1}\\ \end{matrix} \right. $$

Find the general term of $a_n$ in term of $a_1, a_2, p, q, r, s$ and $n$

---

My work:

Let $ A_1= \begin{pmatrix} r&s&0\\ 0&p&q\\ 0&r&s\\ \end{pmatrix} $, $ A_0= \begin{pmatrix} p&q&0\\ r&s&0\\ 0&p&q\\ \end{pmatrix} $, $v_1=\begin{pmatrix} a_1\\ a_2\\ a_3\\ \end{pmatrix}$ and $v_0=\begin{pmatrix} a_2\\ a_3\\ a_4\\ \end{pmatrix}$

Then we have:

$$ \begin{pmatrix} a_{2k}\\ a_{2k+1}\\ a_{2k+2}\\ \end{pmatrix} = A_0\begin{pmatrix} a_{k}\\ a_{k+1}\\ a_{k+2}\\ \end{pmatrix} , \begin{pmatrix} a_{2k+1}\\ a_{2k+2}\\ a_{2k+3}\\ \end{pmatrix} = A_1\begin{pmatrix} a_{k}\\ a_{k+1}\\ a_{k+2}\\ \end{pmatrix} $$

For any integer $n$, $\begin{pmatrix} a_{n}\\ a_{n+1}\\ a_{n+2}\\ \end{pmatrix}$ can be written as a product of some $A_1$ and $A_0$ actting on $v_1$ or $v_0$. Their order depends on the binary form of $n$

For example:

$6=110_{(2)}$，so

$$\begin{pmatrix} a_{6}\\ a_{7}\\ a_{8}\\ \end{pmatrix}=A_0A_1v_1$$

$45=101101_{(2)}$，so

$$\begin{pmatrix} a_{45}\\ a_{46}\\ a_{47}\\ \end{pmatrix}=A_1A_0A_1A_1v_0$$

However, it is difficult to find the closed form of the product as $A_1,A_0$ have different eigenvalues.

Special Case I:

When $p=1+\frac{a}{d},q=1-\frac{a}{d},r=\frac{a}{d},s=2-\frac{a}{d}, a_1=a, a_2=a+d$, then:

$$a_n=a+(n-1)d$$

i.e. ${a_n}$ is an arithmetic sequence.

Answer 1

For the longest path, calling $k=2^m$ we have

$$ \left(\matrix{a_{2^{m+1}+1}\\ a_{2^{m+1}}}\right)= M^j\left(\matrix{a_{2^{m-j+1}+1}\\ a_{2^{m-j+1}}}\right)= M^{m+1}\left(\matrix{a_2\\ a_1}\right) $$

with $M = \left(\matrix{q&p\\ s& r}\right)$. Now if $M = \left(\matrix{1-\lambda&1+\lambda\\ 2-\lambda& \lambda}\right)$ we have

$$ M = T\cdot \Lambda\cdot T^{-1},\ \ T = \left( \begin{array}{cc} 1 & \frac{\lambda +1}{\lambda -2} \\ 1 & 1 \\ \end{array} \right)\ \ \ \Lambda = \left( \begin{array}{cc} 2 & 0 \\ 0 & -1 \\ \end{array} \right) $$

$$ \left(\matrix{a_{2^{m+1}+1}\\ a_{2^{m+1}}}\right)= T\Lambda^{m+1}T^{-1}\left(\matrix{a_2\\ a_1}\right) $$

so for $\lambda = \frac ad,\ \ a_2=a+d, a_1=a$ and $k = 2^m$ we have

$$ \left(\matrix{a_{2k+1}\\ a_{2k}}\right)= \frac 13\left( \begin{array}{c} \left(2^{m+1}+(-1)^m\right) (a+d)\\ \left(2^{m+1}+(-1)^m\right) (a+d)-3d(-1)^m \\ \end{array} \right) $$

For $a_1=a_2=a$ with the same $\lambda,k$ we have

$$ \left(\matrix{a_{2k+1}\\ a_{2k}}\right)=\left( \begin{array}{c} 2^m \\ 2^m \\ \end{array} \right)a $$

Answer 2

(Partial answer)

An alternative approach would be the use of the generating function associated to the sequence, as follows : $$ \begin{array}{rcl} A(x) &=& \displaystyle \sum_{n\ge0} a_nx^n \\ &=& \displaystyle \sum_{k\ge0} a_{2k}x^{2k} + a_{2k+1}x^{2k+1} \\ &=& \displaystyle \sum_{k\ge0} (pa_k + qa_{k+1})x^{2k} + (ra_k + sa_{k+1})x^{2k+1} \\ &=& \displaystyle \sum_{k\ge0} (p+rx)a_kx^{2k} + (q+sx)a_{k+1}x^{2k+1} \\ &=& \displaystyle (p+rx)\sum_{k\ge0}a_kx^{2k} + (q+sx)\sum_{k\ge1}a_kx^{2k-1} \\ &=& \displaystyle (p+rx)A(x^2) + \frac{q+sx}{x}(A(x^2)-a_0) \end{array} $$ hence $$ (q+(p+s)x+rx^2)A(x^2) - xA(x) -a_0(p+rx) = 0 $$ This functional equation can be complicated to solve, but it has the advantage to circumvent the binary considerations.

Answer 3

The question asks

Given that the initial terms $a_1$, $a_2$ and the recursion: $$ \left\{ \begin{matrix} a_{2k}=pa_k+qa_{k+1}\\ a_{2k+1}=ra_k+sa_{k+1}\\ \end{matrix} \right. $$ Find the general term of $a_n$ in term of $a_1, a_2, p, q, r, s$ and $n$

This is essentially a combinatorial problem to determine "generating sequences" (my ad hoc name) for positive integers.

More precisely, a generating sequence is a sequence of moves beginning from $1$ or $2$ such that a move from $k$ to $2k$ is indicated by prepending $p$ to a generating sequence for $k$ or prepending $q$ to a generating sequence for $k+1$. Similarly, a move from $k$ to $2k+1$ is indicated by prepending $r$ to a generating sequence for $k$ or prepending $s$ to a generating sequence for $k+1$.

This is a small table of valid generating sequences

$$ \begin{array}{|c|c|} \hline n & \text{generating sequences} \\ \hline 1 & 1 \\ \hline 2 & 2 \\ \hline 3 & r1, s2 \\ \hline 4 & p2, qr1, qs2 \\ \hline 5 & r2, sr1, ss2 \\ \hline 6 & pr1, ps2, pq2, qqr1, qqs2 \\ \hline 7 & rr1, rs2, sp2, sqr1, sqs2 \\ \hline \end{array} $$

The corresponding table of sequence values is

$$\begin{array}{|c|c|} \hline n & a_n \\ \hline 1 & a_1 \\ \hline 2 & a_2 \\ \hline 3 & ra_1 + sa_2 \\ \hline 4 & pa_2 + qra_1 + qsa_2 \\ \hline 5 & ra_2 + rsa_1 + ssa_2 \\ \hline 6 & pra_1 + psa_2 + pqa_2 + qqra_1 + qqsa_2 \\ \hline 7 & rra_1 + rsa_2 + psa_2 + qrsa_1 + qssa_2 \\ \hline \end{array} $$

The key phrase is "general term of $a_n$ in term of $a_1,a_2,p,q,r,s$ and $n$" which seems to indicate a closed form expression. I don't think that this exists although a proof of this fact would be very difficult.

Notice that for $k>1$ the number of generating sequences for $2k$ and $2k+1$ are both equal to $A_k$ where $A$ is the OEIS sequence A275202. For example, $A_2=3$ and there are $3$ generating sequence for both $4$ and $5$.

Some special cases of $\,a_n\,$ appear in the OEIS.

A notable example with many references to the literature is the Stern-Brocot sequence

$\texttt{ a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).}$

Another example is OEIS sequence A214126

$\texttt{ a(2n)=a(n-1)+a(n) and a(2n+1)=a(n+1) for n>=1, with a(0)=a(1)=1.}$

One more example is OEIS sequence A294044

$\texttt{a(0) = 0, a(1) = a(2) = 1; a(2*n) = 2*a(n) + a(n+1), a(2*n+1) = a(n) + a(n+1).}$

$\texttt{G.f. g(x) satisfies g(x) = (x + 2 + 1/x + 1/x^2)*g(x^2) - 1 - 2*x^2. - Robert Israel, Oct 24 2017}$

Answer 4

I found 2 ways to calculate $a_{n}$ when $q=0$ i.e. $$\left\{ \begin{matrix} a_{2k}&=pa_k&\\ a_{2k+1}&=ra_k&+sa_{k+1}\\ \end{matrix} \right.$$ For convenience, we have the following definetion:
$b_n:=$ number of 1's in binary expansion of n (OEIS sequence A000120).
$l_n:=\lfloor \log_2n\rfloor$ i.e. $l_n$ is one less than the length of the binary form of $n$.
Then, I found that $$ a_n=s^{l_n}\left(a'_n+\frac{p}{s}(s-1)a'_{n-2^{l_n}}\right)$$ where $a'_n$ is defined as $$\left\{ \begin{matrix} a'_{2k}&=\frac{p}{s}a'_k&\\ a'_{2k+1}&=\frac{r}{s}a'_k&+a'_{k+1}\\ \end{matrix} \right.$$ and can be found as follows $$a'_{n+1}=\sum_{i+2j=n}\left(\frac{p}{s}\right)^{b_i}\left(\frac{r}{s}\right)^{b_j}\left[\binom{i+j}{i}\mod{2}\right]$$ There is an alternative formula $$a'_{n+1}=\sum_{k=0}^n \lambda^{b_k} \bar{\lambda}^{b_{n-k}}$$ where $\lambda, \bar{\lambda}$ be the roots of $sx^2-px+r=0$.
Now we know how to find $a'_n$, then we can find $a_n$ through the equation between $a'_n$ and $a_n$. After substitution and simplification, we have $$a_{n+1}=\sum_{i+2j=n}s^{l_{n}-b_j-b_{2^{l_{n}}+i}+1}p^{b_i}r^{b_j}\left[\binom{i+j}{i}\mod{2}\right]$$ or the alternative form $$a_{n+1}=s^{l_n+2}\sum_{i+j=n} s^{b_i+b_j-b_{2^{l_n}+i}-b_{2^{l_n}+j}}\lambda^{b_i} \bar{\lambda}^{b_{j}}$$ I will type the proof when I am available.