Third-order recurrence with non-constant coefficients

Question

During the study of a problem, I encountered this recurrence: $$ a_n=a_{n-1}+2^{n-3}a_{n-2}+a_{n-3},\ n\geq 4 $$ with $a_1=0$, $a_2=1$ and $a_3=1$. Does anyone know a way to obtain an explicit expression for $a_n$?

I tried in several ways (order reduction, particular solutions), but without success. I also looked it up in OEIS and tried with some numerical simulations, again ended up empty-handed.

Answer 1

Let $a_n=\int_{-\infty}^\infty2^{nt}K(t)~dt$ ,

Then $\int_{-\infty}^\infty2^{nt}K(t)~dt=\int_{-\infty}^\infty2^{(n-1)t}K(t)~dt+2^{n-3}\int_{-\infty}^\infty2^{(n-2)t}K(t)~dt+\int_{-\infty}^\infty2^{(n-3)t}K(t)~dt$

$\int_{-\infty}^\infty2^{nt}K(t)~dt-\int_{-\infty}^\infty2^{nt}2^{-t}K(t)~dt-\int_{-\infty}^\infty2^{n(t+1)}2^{-2t-3}K(t)~dt-\int_{-\infty}^\infty2^{nt}2^{-3t}K(t)~dt=0$

$\int_{-\infty}^\infty2^{nt}K(t)~dt-\int_{-\infty}^\infty2^{nt}2^{-t}K(t)~dt-\int_{-\infty}^\infty2^{nt}2^{-2t-1}K(t-1)~dt-\int_{-\infty}^\infty2^{nt}2^{-3t}K(t)~dt=0$

$\int_{-\infty}^\infty((1-2^{-t}-2^{-3t})K(t)-2^{-2t-1}K(t-1))2^{nt}~dt=0$

$\therefore(1-2^{-t}-2^{-3t})K(t)-2^{-2t-1}K(t-1)=0$

$(1-2^{-t}-2^{-3t})K(t)=2^{-2t-1}K(t-1)$

$K(t)=\dfrac{2^tK(t-1)}{2^{3t+1}-2^{2t+1}-2}$

$K(t)=\theta(t)\prod\limits_{k=0}^\infty\dfrac{2^{k+t}}{2^{3k+3t+1}-2^{2k+2t+1}-2}$ , where $\theta(t)$ is an arbitrary periodic functions with unit period

$\therefore a_n=\Theta(n)\int_{-\infty}^\infty\prod\limits_{k=0}^\infty\dfrac{2^{k+(n+1)t}}{2^{3k+3t+1}-2^{2k+2t+1}-2}~dt$ , where $\Theta(n)$ is an arbitrary periodic functions with unit period

But this is only one of the group of the linear independent solution. I have no idea to find another groups of the linear independent solution, since third order linear recurrence relations unlike third order linear differential equations which have reduction of order.

Answer 2

Numerical experiment

Writing in Wolfram Mathematica 12.0:

nmax = 200;
recurrence = {f[n] == f[n - 1] + 2^(n - 3) f[n - 2] + f[n - 3]};
seqA = RecurrenceTable[{recurrence, f[1] == 0, f[2] == 1, f[3] == 1}, f, {n, 3, nmax}];
seqB = RecurrenceTable[{recurrence, f[1] == 0, f[2] == 0, f[3] == 1}, f, {n, 3, nmax}];

ListPlot[seqA/seqB]
N[seqA[[nmax - 3]]/seqB[[nmax - 3]], 20]
N[seqA[[nmax - 2]]/seqB[[nmax - 2]], 20]

I get:

1.8058254356604270947

2.1654873668496381087

which is what is desired.