Can we solve this recurrence relation?

Question

Consider the following recurrence relation $$x_1=1\\ x_2=a\\ x_{n+2}=ad^nx_{n+1}-dx_n$$ where $a,x_n\in\mathbb{C}$ and $d\in\mathbb{R},d>1$.

Is there any $a\in\mathbb{C}$ such that $\lim x_n=0$ ? or at least can we find a formula for $x_n$ depending only on $a$ and $d$?

Answer 1

Let $x_n$ be a complex sequence satisfying $x_0=0$, $x_1=1$ and $$x_{n+2}=ad^nx_{n+1}-dx_n$$ for all $n\in\Bbb N$ with $d>1$ and $a\in\Bbb C\setminus\{0\}$. Then \begin{align} &x_n=O(a^nd^{n^2/2-n/2})& &(n\to\infty)\tag 1 \end{align} Moreover, we have $x_n=o(a^nd^{n^2/2-n/2})$ if and only if $x_n\xrightarrow{n\to\infty}0$.

Proof. First note that the sequence $u_n=a^nd^{n^2/2-n/2-1}$ satisfy $u_{n+2}=ad^nu_{n+1}$, hence if we put $w_n=x_n/u_n$, the we have $$w_{n+2}=w_{n+1}-d\frac{u_n}{u_{n+2}}w_n$$ Since $d\frac{u_n}{u_{n+2}}=\frac{d^2}{a^2d^{2n}}$ we get $$w_{n+2}=w_1-\frac{d^2}{a^2}\sum_{k=0}^n\frac{w_k}{d^{2k}}\tag 3$$

We claim that this sequence converges. For all $n\in\Bbb N$, we have \begin{align} &|w_n|\leq c^n& &\text{where } c=1+\frac{d^4}{|a|^2(d^2-1)}>1 \end{align} This follows by induction on $n$, for \begin{align} |w_{n+2}| &\leq|w_1|+\frac{d^2}{|a|^2}\sum_{k=0}^n\frac{|w_k|}{d^{2k}}\\ &\leq c+\frac{d^2}{|a|^2}c^n\sum_{k=0}^nd^{-2k}\\ &\leq c^{n+1}+\frac{d^2}{|a|^2}c^{n+1}\frac 1{1-d^{-2}}\\ &\leq c^{n+2} \end{align} Consequently, $\sqrt[n]{|w_n|}$ is bounded and let $\ell=\limsup\sqrt[n]{|w_n|}$. If $\ell<d^2$ then the power series in $(3)$ is convergent, hence $w_n$ is convergent as well. Assume $\ell\geq d^2>1$. Then for all $\varepsilon>0$, we have $|w_n|\leq(\ell+\varepsilon)^n$ eventually, hence there exists a constant $C>0$ satisfying \begin{align} \ell &=\limsup\sqrt[n]{|w_n|}\\ &\leq\limsup\sqrt[n]{|w_1|+C\sum_{k=0}^n\left(\frac{\ell+\varepsilon}{d^2}\right)^k}\\ &\leq\lim \sqrt[n]{|w_1|+C\frac{\left(\frac{\ell+\varepsilon}{d^2}\right)^{n+1}-1}{\frac{\ell+\varepsilon}{d^2}-1}}\\ &=\frac{\ell+\varepsilon}{d^2} \end{align} from which $\ell\leq\frac\ell{d^2}$ which implies $d^2\leq 1$, a contradiction which proves $w_n$ to be convergent and hence proves $(1)$.

Finally, from $(3)$, we get $w_n\xrightarrow{n\to\infty}0$ if and only if $$w_1=\frac{d^2}{a^2}\sum_{k=0}^\infty\frac{w_k}{d^{2k}}$$ from which $$w_{n+2}=\frac{d^2}{a^2}\sum_{k=n+1}^\infty\frac{w_k}{d^{2k}}$$ Let $$s_n=\sup_{k\geq n}|w_k|$$ Then $s_n\downarrow 0$ and for all $k\geq n$ we have \begin{align} |w_{k+2}| &\leq\frac{d^2}{|a|^2}\frac{s_{k+1}}{d^{2k+2}}\\ &\leq\frac{d^2}{|a|^2}\frac{s_{n+1}}{d^{2n+2}} \end{align} from which $$s_{n+2}\leq\frac{d^2}{|a|^2}\frac{s_{n+1}}{d^{2(n+1)}}$$ Consequently \begin{align} s_n &\leq s_0\prod_{k=0}^{n-1}\frac{d^2}{|a|^2 d^{2k}}\\ &\leq s_0\frac{d^{2n}}{|a|^{2n}d^{n^2-n}} \end{align} Consequently, \begin{align} |x_n| &=|u_n||w_n|\\ &\leq |u_n| s_n\\ &\leq s_0\frac{|u_n|}{|a|^{2n}d^{n^2-n}}\\ &=\frac{|a|^nd^{n^2/2-n/2-1}}{|a|^{2n}d^{n^2-3n}}\\ &\xrightarrow{n\to\infty}0 \end{align} $\square$

Assuming $x_n\neq 0$ eventually, we have $x_n\xrightarrow{n\to\infty}0$ if and only if $|x_{n+1}/x_n|$ is bounded.

Proof. The sequence $z_n=\sqrt d x_{n+1}/x_n$ satisfy $$z_{n+1}+\frac 1{z_n}=\frac a{\sqrt d}d^n$$ If $|z_n|$ is bounded, then $|\frac 1{z_n}|\geq\frac{|a|}{\sqrt d}d^n-|z_{n+1}|\to\infty$. Thus $|z_n|\to 0$. In particular, $|z_n|$ is bounded by $1/2$, hence $|x_n|$ is bounded $2^{-n}$, hence $x_n\to 0$. $\square$

We have $x_n\xrightarrow{n\to\infty}0$ if and only if $\sqrt[n]{|x_n|}$ is bounded.

Proof. Let $\sqrt[n]{|x_n|}$ be bounded and $$\ell=\limsup_{n\to\infty}\sqrt[n]{|x_n|}$$ Then for all $\varepsilon>0$, we have $|x_n|<(\ell+\varepsilon)^n$ eventually, hence \begin{align} \ell &=\limsup_{n\to\infty}\sqrt[n+1]{|x_{n+1}|}\\ &\leq\limsup_{n\to\infty}\sqrt[n+1]{\left|\frac{x_{n+2}}{ad^n}\right|+\left|\frac{dx_n}{ad^n}\right|}\\ &\leq\lim_{n\to\infty}\sqrt[n+1]{\frac{(\ell+\varepsilon)^{n+2}} {|a|d^n}+\frac{d(\ell+\varepsilon)^{n}}{|a|d^n}}\\ &=\lim_{n\to\infty}\sqrt[n+1]{\frac{(\ell+\varepsilon)^{n}}{|a|d^n}((\ell+\varepsilon)^2+d)}\\ &=\frac{\ell+\varepsilon}d \end{align} Thus $\ell\leq\frac{\ell+\varepsilon}d$ for all $\varepsilon>0$, hence $\ell\leq\ell/d$ from which $\ell(d-1)\leq 0$. Since $d>1$ and $\ell\geq 0$, this implies $\ell=0$, hence $x_n\to 0$. $\square$

A generating function.

We have $x_n\xrightarrow{n\to\infty}0$ if and only if there exists an entire function $G:\Bbb C\to\Bbb C$ satisfying the functional equation $$(1+dz^2)G(z)=1+azG(dz)$$

Proof. Let $x_0=0$ and $x_1=1$ and let $F$ be its generating function $$F(z)=\sum_{n=0}^\infty x_n z^n=zG(z)$$ Then $G$ satisfy the functional equation $$(1+dz^2)G(z)=1+azG(dz)$$ In particular, this gives $G(0)=1$ and for $z=\pm i\sqrt d$ $$G(\pm i\sqrt d)=\pm i\frac{\sqrt d}a$$

Answer 2

$$\mathbf{\color{green}{FINAL\ EDITION}}$$ $$\mathbf{\color{brown}{Case\ d=0}}$$ If $d=0,$ then \begin{align} &x_1=1,\quad x_2=a,\quad x_n=0,\quad n=3, 4,\dots. \end{align} Then $\mathbf{x_n\to 0.}$

$$\mathbf{\color{brown}{Case\ d\not=0.\ Sequence\ transformation}}$$

Easily to get \begin{align} &x_1=1,\quad x_2=a,\quad x_{1+2} = ad^1\cdot a-d\cdot1 = d(a^2-1),\\[4pt] &x_{2+2} = ad^2\cdot d(a^2-1)- d\cdot a = ad(d^2(a^2-1)-1),\\[4pt] &x_{3+2} = ad^3\cdot ad(d^2(a^2-1)-1) - d\cdot d(a^2-1) = d^2(a^2d^2(d^2(a^2-1)-1))-(a^2-1))\dots \end{align} Let $$x_n = d^{n/_2\ }y_{n},\quad n=1, 2,\dots,\tag1$$ then \begin{align} &d^{\frac{n+2}2}y_{n+2} = ad^nd^{\frac{n+1}2}y_{n+1} - d^{\frac{n}2}dy_n,\\[4pt] &y_{n+2}=gd^ny_{n+1}-y_n,\quad g=\dfrac a{\sqrt d}, \tag2\\ \end{align} $$\begin{align} &y_1=1,\quad y_2=g,\\ &y_3=dg^2-1=dg^2-S_0,\\ &y_4=d^3g^3-(d^2+1)g=d^3g^3-S_2g,\\ &y_5=d^6g^4-(d^5+d^3+d)g^2+1 = d^6g^4-S_4dg^2+1,\\ &y_6=d^{10}g^5-(d^9+d^7+d^5+d^3)g^3 +(d^4+d^2+1)g=d^{10}g^5-S_6d^3g^3+S_4g,\\ &y_7=d^{15}g^6-S_8d^6g^4+(S_6+d^3)dg^2-1=d^{15}g^6-S_8d^6g^4+(S_6+d^3)dg^2-1,\\ &y_8=d^{21}g^7-S_{10}d^{10}g^5+(S_{12}+d^6)d^3g^3=d^{21}g^7-S_{10}d^{10}g^5+S_6(d^6+1)d^3g^3,\\ &y_9=d^{28}g^8-S_{12}d^{15}g^6+(S_{14}+d^{12}+d^{10}+2d^8+d^6+d^4)d^6g^4\\ &-(S_{12}+d^8+d^6+d^4)dg^2+1\\ &=d^{28}g^8-S_{12}d^{15}g^6+(S_{10}+d^8)(d^4+1)d^6g^4-S_{10}(d^4+1)dg^2+1\dots,\\ \end{align}\tag3$$ wherein simple regularities can be obtained only for the first and last terms.

$$\mathbf{\color{brown}{Using\ recurrence\ relation.}}$$

Let us consider the behavior of the recurrence relation $$y_{n+2}+sy_{n+1}+y_{n}=0,\quad y_1=b_1,\quad y_2=b_2,\quad b\not=0.\tag4$$ The characteristic equation $$t^2+st+1=0\tag5$$ has the roots $$t_{1,2} = -\frac s2 \pm \frac{\sqrt{s^2-4}}2,\tag6$$ so the common solution is $$y_n=C_1t_1^{n}+C_2t_2^{n}.\tag7$$

$\mathbf{Case\ s^2-4<0.}$

Easy to see that $|t_1|=|t_2|=1.$ The sequence $y_n$ is bounded if $\mathbf{|s|<2}.$

$\mathbf{Case\ s^2-4=0.}$

The sequence $y_n$ is bounded if $\mathbf{s=\pm2}.$

$\mathbf{Case\ s^2-4 > 0.}$

Let $|t_1|<1,$ then the sequence $y_n$ converges to $0$ iff $C_2=0,$ or iff $\mathbf{|s|\ge2,\quad b_2=b_1t_1}.$

Therefore, the sequence $y_n$ converges to $0$ if $\mathbf{|s|\ge2,\quad b_2=b_1t_1}.$

$$\mathbf{\color{brown}{Case\ g=0.}}$$ Equation $(2)$ transforms to $$y_{n+2}+y_n=0$$ of the type $(4)$ with $s=0.$ So $\mathbf{z_n\ are\ bounded\ and\ x_n\to 0}.$

$$\mathbf{\color{brown}{Case\ d\not=0,\quad g\not=0}}$$

$\mathbf{\color{green}{Splitting}}$

Let us split the even and the odd subsequences of $y_n,$ \begin{align} &y_{n+2} = d^ngy_{n+1} - y_n = d^ng(d^{n-1}gy_n-y_{n-1})-y_n = (d^{2n-1}g^2-1)y_n-d^ngy_{n-1}\\ &=(d^{2n+1}g^2-1)y_n-d^2(y_n+y_{n-2}),\\ \end{align} $$\boxed{y_{n+2}=(d^{2n-1}g^2-d^2-1)y_n-d^2y_{n-2}}.\tag8$$ Formulas $(8)$ can be easily checked, using $(3)$.

This allow to consider the odd ($n=2k-1$) and the even ($n=2k)$ subsequences such as $$z_{k+2}^{(Odd)} = (d^{4k-3}g^2-d^2-1)z_{k+1}^{(Odd)} - d^2z_{k}^{(Odd)},\quad z_{1}^{(Odd)} = 1,\quad z_{n+2}^{(Odd)} = dg^2 - 1,\tag{8O}$$ $$z_{k+2}^{(Even)} = (d^{4k-1}g^2-d^2-1)z_{k+1}^{(Even)} - d^2z_{k}^{(Even)},\quad z_{1}^{(Even)} = g,\quad z_{n+2}^{(Even)} = d^3g^3 - (d^2+1)g.\tag{8E}$$

$\mathbf{\color{green}{Case\ 0<|d|<1}}$

Easy to see that for arbitrary value of $g$ $$\lim\limits_{n\to\infty}d^{2n-1}g^2 = 0,$$ and the asymptotic behavior both the even and the odd subsequences of $y_n$ is defined by the recurrence relation $$z_{n+2}+(d^2+1)z_{n+1}+d^2y_n=0.\tag9$$ The characteristic equation of $(9)$ is $$t^2+(d^2+1)t+d^2=0,\tag{10},$$ with the roots $t_1=-1$ and $t_2=-d^2.$ This gives the common solution of $(9)$ in the form of $$z_{n+2} = C_1(-1)^n+C_2(-d^2)^n.\tag{11}$$ Easy to show that $\mathbf{z_n\ are\ bounded\ and\ x_n\to 0}.$

$\mathbf{\color{green}{Case\ |d|=1}}$

Equation $(2)$ takes the form of $$z_{n+2}+gz_{n+1}+z_n=0,\tag{12}$$ similar as $(4).$ So $\mathbf{x_n\to 0\ if\ g\in[-2,2]}.$

Attempt to satisfy conditions $t_1b_1=b_2$ in the same time for the both of the subsequences $z_n$ leads to the equation $(g^2-1)g=g^3-2g$, so there are not solutions with another values of $g$.

$\mathbf{\color{green}{Extended\ recurrence\ relation.}}$

All attemps to get the closed form of the solution were not successul.

At the same time, recursive applying of $(8)$ gives for $i=0\dots3:$ \begin{align} &y_{4m+i} = d^{8(m-1)+2i+3}g^2y_{4(m-1)+i+2}-(d^2+1)(y_{4(m-1)+i+2}+y_{4(m-1)+i})\\[4pt] &+ d^{8(m-2)+2i+3}g^2y_{4(m-2)+i+2}-(d^2+1)(y_{4(m-2)+i-2}+y_{4(m-2)+i-4})\\[4pt] &+ d^{8(m-3)+2i+3}g^2y_{4(m-3)+i+2}-(d^2+1)(y_{4(m-3)+i-2}+y_{4(m-3)+i-4})+\dots,\\[4pt] \end{align} $$\color{brown}{y_{4m+i}= \sum\limits_{k=0}^{m-1}\left(d^{8k+2i+3}g^2y_{4k+i+2}-(d^2+1)\left(y_{4k+i+2}+y_{4k+i}\right)\right)}.\tag{13}$$

$\mathbf{\color{green}{Case\ \quad |d|>1}}$

Assume $$y_m=Cp^m,\tag{14}$$ then, using $(13),$ one can get $$p^{4m+i}+(d^2+1)p^i\frac{p^{4m}-1}{p^2-1}=d^{2i+3}p^{i+2}\frac{d^{8m}p^{4m}-1}{d^8p^4-1}g^2,$$ or $$\frac{p^{4m+2}-1}{p^2-1}+d^2\frac{p^{4m}-1}{p^2-1}=d^{2i+3}p^2\frac{d^{8m}p^{4m}-1}{d^8p^4-1}g^2.\tag{15}$$

$$\mathbf{Case\ |p|>1}.$$

$\mathbf{Both\ y_m\ and\ x_m\ are\ not\ bounded\ }.$

$$\mathbf{Case\ |p|\to 1}.$$

$$LHS(15)\sim 2m(d^2+1)+1,\quad RHS(15)\sim d^{2i-1}g^2(d^4p^2)^{2m-1}.$$ $\mathbf{There\ are\ not\ solutions\ in\ the\ form\ (14)}.$

$$\mathbf{Case\ 1>|p|>\frac1{d^2}}.$$

$$LHS(15)\to \dfrac{d^2+1}{1-p^2}\le \dfrac{d^2+1}{1-d^{-4}}=\dfrac{d^4}{d^2-1},$$ $$RHS(15)\sim d^{2i-1}g^2(d^4p^2)^{2m-1}.$$ $\mathbf{There\ are\ not\ solutions\ in\ the\ form\ (14)}.$

$$\mathbf{Case\ |p|\to\frac1{d^2}}.$$

$$LHS(15)\to \dfrac{d^2+1}{1-p^2}\to \dfrac{d^2+1}{1-d^{-4}}=\dfrac{d^4}{d^2-1},$$ $$RHS(15)\sim d^{2i-1}g^2m.$$ $\mathbf{There\ are\ not\ solutions\ in\ the\ form\ (14)}.$

$$\mathbf{Case\ |p|<\frac1{d^2}}.$$

$$LHS(15)\to \dfrac{d^2+1}{1-p^2},\quad RHS(15)\to\frac{d^{2i+3}p^2}{1-p^4d^8}g^2.$$ If $|p|$ changes from $0$ to $\frac1{d^2},$ then $LHS(15)$ increases from $(d^2+1)$ to $\frac{d^4}{d^2-1}.$

On the other hand, $|RHS(15)|$ increases from $0$ to $\infty.$

If $d<-1,\quad i\in\{1,3\}$ then $RHS(15)\le0.$ Otherwise $RHS(15)\ge0.$

So $\mathbf{x_m\to 0\ iff\ d>1}.$

$$\mathbf{\color{brown}{Conclusion.}}$$

Therefore, the given sequence converges to $0$ iff $$\mathbf{\color{brown}{(|d|<1)\ or\ ((|d|=1) \wedge (|g|\ge2)\ or\ (d>1)}}.$$

Answer 3

I am not convinced, yet, that what follows below is right (I'm sure there's a flaw in there somewhere), but I feel it's worth posting so that others can check for errors...

---

Suppose that $y_n=x_{n+1}-A_n x_n$. Now, we can observe that $$\begin{align} y_{n+1}=x_{n+2}-A_{n+1}x_{n+1} &= (ad^n-A_{n+1}) x_{n+1} - dx_n\\ &=(ad^n-A_{n+1})\left(x_{n+1}-\frac{d}{ad^n-A_{n+1}}x_n\right) \end{align}$$ To keep our expression independent of $x_n$, we require that $$ A_n=\frac{d}{ad^n-A_{n+1}} $$ or $$ A_{n+1}=ad^n-\frac{d}{A_n} $$ Note that this expression does not depend on $x_n$ in any way, and we can choose $A_0$ as we please (so long as $A_n$ never takes the value of 0).

Now, if we have an $A_n$ satisfying this expression, then we have $$ y_{n+1}=(ad^n-A_{n+1})y_n = \frac{d}{A_n}y_n $$ Also note that $y_0=a-A_0$. If $|A_n|$ is small, then $y_n$ will grow. If $|A_n|>d$, then $y_n$ will shrink.

If $A_n$ remains bounded, then for $x_n$ to converge to zero, it is necessary and sufficient that $y_n$ converge to zero.

From these two facts, we conclude that, if there exists an $A_0\neq a$ for which $|A_n|$ is bounded above by $d$ for sufficiently large $n$, then $x_n$ cannot converge to zero.

This, however, causes a problem. Returning to the original recurrence, dividing by $x_{n+1}$ and letting $B_n=\frac{x_{n+1}}{x_n}$, we obtain $$ B_{n+1}=ad^n-\frac{d}{B_n} $$ Now, if $x_n\to 0$, then $|B_n|$ is bounded above by 1 for sufficiently large $n$, at least in terms of geometric mean. Of course, B_0=a$, and thus this fact itself does not indicate that convergence cannot be obtained.

However, consider $A_0=a+\epsilon$ for a small value, $\epsilon$. We can easily see that $$ \frac{dA_{n+1}}{d\epsilon} = \frac{d}{A_n^2}\frac{dA_n}{d\epsilon} $$ and therefore, $\frac{dA_n}{d\epsilon}$ will stabilise when $A_n\to \sqrt{d}$, limiting the impact for sufficiently small $\epsilon$. And as $\sqrt{d}<d$ (because $d>1$), we therefore conclude that $\exists\epsilon$ such that $|A_n|$ remains bounded above by $d$.

From this, we can conclude (by contradiction) that there cannot be a value of $a$ for which $x_n$ converges to zero, so long as $d>1$.