1

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.

Alessio Del Vigna
  • 1,767
  • Are you sure that you have made no typo? – Dr. Sonnhard Graubner Jun 26 '19 at 09:28
  • Yes, I checked again: that is the recurrence I have. Am I missing something? – Alessio Del Vigna Jun 26 '19 at 09:36
  • I checked it and no solution was found. – Dr. Sonnhard Graubner Jun 26 '19 at 09:37
  • What are you referring to? The sequence $(a_n)_{n\geq 1}$ is well-defined in the above way. – Alessio Del Vigna Jun 26 '19 at 09:46
  • @AlessioDV I am afraid that there is no easy "closed formula" . May I ask why you need an explicit formula? Are you interested in its asymptotics? – Robert Z Jun 26 '19 at 10:07
  • This is also my worry... My original problem is the following. Let $(a_n){n\geq 1}$ the sequence above and let $(b_n){n\geq 1}$ be the sequence satisfying the same recurrence but with initial conditions $b_1=0$, $b_2=0$ and $b_3=1$. The sequence $\left(\frac{a_n}{b_n}\right)_{n\geq 3}$ does not have limit and I also know that the sub-sequence with odd indices and the one with even indices converge to two different limits. My final aim is to find explicitly these two limits. – Alessio Del Vigna Jun 26 '19 at 10:12

2 Answers2

2

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.

doraemonpaul
  • 16,178
  • 3
  • 31
  • 75
0

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:

enter image description here

1.8058254356604270947

2.1654873668496381087

which is what is desired.

Community
  • 1
πρόσεχε
  • 5,188