$a_n-a_{n-1}+\frac{2}{n}a_{n-2}=0$. Is $\{a_n\}$ eventually positive/negative, or $a_n=O(n^{-2})$?

Question

So there is a recusive sequence $\{a_n\}$ with

\begin{equation}a_n-a_{n-1}+\frac{2}{n}a_{n-2}=0, \quad (n\geq 2)\tag1 \end{equation}

values of $a_0$ and $a_1$ being arbitrary. Is it true that:

Conjecture 1. $\{a_n\}$ is eventually positive or eventually negative, or

Conjecture 2. $\{a_n\}=O(n^{-2}\,)$?

Notes

Conjecture 1 implies Conjecture 2 since if $\{a_n\}$ is eventually of the same sign, then $b_n:=n(n-1)a_n$ satisfies $$b_{n}=b_{n-1}-4a_{n-3}$$ and hence $\{b_n\}$ is bounded, so $a_n=O(n^{-2}\,)$ follows.

So the problem boils down to:

• Prove/Disprove Conjecture 1, or

• Prove/Disprove Conjecture 2 in a separated way.

Supporting Conjecture 1 are the first 21 terms of the sequence with $a_0=0, a_1=1$: \begin{multline*}0,1, 1,{{1}\over{3}}, -{{1}\over{6}}, -{{3}\over{10}}, -{{11}\over{45}}, -{{10}\over{63}}, -{{41}\over{420}}, -{{101}\over{1620}}, -{{607}\over{14175}}, -{{1091}\over{34650}},\\ -{{2278}\over{93555}}, -{{10783}\over{552825}}, -{{227407}\over{14189175}}, -{{659441}\over{49116375}}, -{{8335507}\over{729729000}},\\ -{{56984107}\over{5789183400}}, -{{837616139}\over{97692469875}}, -{{3292116007}\over{436742806500}}, -{{27555605257}\over{4124793172500}}\end{multline*} and $a_0=1,a_1=0$: \begin{multline*}1, 0, -1, -1, -{{1}\over{2}}, -{{1}\over{10}}, {{1}\over{15}}, {{2}\over{21}}, {{11}\over{140}}, {{31}\over{540}}, {{197}\over{4725}}, {{361}\over{11550}}, {{758}\over{31185}},\\ {{3593}\over{184275}}, {{75797}\over{4729725}}, {{219811}\over{16372125}}, {{2778497}\over{243243000}}, {{18994697}\over{1929727800}},\\ {{279205369}\over{32564156625}}, {{1097371997}\over{145580935500}}, {{9185201747}\over{1374931057500}}\end{multline*}

Finally, I also want to know where to find more material on non-autonomous recurrence relations like $(1)$.

Answer 1

I made some computations a couple of years ago:

---

Claim. Let $a \in \mathbb{R}$. Suppose that $a_{n} \in \mathbb{C}$ satisfies the recurrence relation $$ a_{n} = a_{n-1} + \frac{a}{n} a_{n-2}, \quad n \geq 2. $$ Then $(a_n)$ satisfies the bound $ a_{n} = \mathcal{O}\left( n^{a} \right) $.

Proof. Let $A_{n}$ and $B_{n}$ be sequences of $2\times 2$ matrices defined by

\begin{align*} A_{n} = \begin{pmatrix} 1 & \tfrac{a}{n} \\ 1 & 0 \end{pmatrix}, \quad B_{n} = \begin{pmatrix} -\tfrac{a}{n} & 1+\tfrac{a}{n} \\ 1 & 1 \end{pmatrix}. \end{align*}

Note that $A_n$ are designed to realize the recurrence relation of $(a_n)$, which means that the following identity holds.

\begin{align*} \begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix} = A_{n} \cdots A_{2} \begin{pmatrix} a_{1} \\ a_{0} \end{pmatrix}, \quad n \geq 2. \end{align*}

Now we introduce $\tilde{A}_{n} = B_{n+1}^{-1} A_{n} B_{n}$. After some tedious calculation, we check that

\begin{align*} \tilde{A}_{n} &= \frac{1}{n (n+2a+1)} \begin{pmatrix} -a n - a(a+1) & (a-1) a \\ -a^{2} & n^{2} + (3a+1) n + (a^{2} + 2 a) \end{pmatrix} \\ &= \begin{pmatrix} -\tfrac{a}{n} & 0 \\ 0 & 1 + \tfrac{a}{n} \end{pmatrix} + \mathcal{O}\left( \frac{1}{n^{2}} \right). \end{align*}

Thus for sufficiently large $n$, the operator norm $\| \tilde{A}_{n} \|$ of $\tilde{A}_{n}$ satisfies the following bound

\begin{align*} \| \tilde{A}_{n} \| \leq 1 + \frac{a}{n} + \mathcal{O}\left( \frac{1}{n^{2}} \right). \end{align*}

Applying this to $A_{n} \cdots A_{2}$, we have

\begin{align*} \| A_{n} \cdots A_{2} \| &= \| B_{n+1} \tilde{A}_{n} \cdots \tilde{A}_{2} B_{2} \| \lesssim \exp \left\{ \sum_{k=2}^{n} \frac{a}{k} + \mathcal{O}\left( \frac{1}{k^{2}} \right) \right\} \lesssim n^{a}. \end{align*}

This proves our bound as desired. ////

Intuitions behind the proof are as follows:

1. Write the recurrence equation as $a_{n} - a_{n-1} = (a/n)a_{n-2}$. Heuristically, its continuous analogue is $y' = (a/x) y$. Then it is easy to check that the solution is of the form $y = c x^{a}$. So we can expect a similar asymptotic behavior for $a_{n}$.

2. The column vectors of $B_{n}$ are very close (up to $\mathcal{O}(n^{-2})$) to eigenvectors of $A_{n}$. Thus $\tilde{A}_{n}$ is essentially the matrix representation of $A_{n}$ with respect to eigenvectors of $A_{n}$ and $A_{n+1}$.

Answer 2

I'll demonstrate that

\begin{equation} \tag{1} a_{n+1}=-\alpha \frac{2^{n}(n-1)}{(n+1)!} + f(\beta,n+1) \end{equation}

with $a_0=\alpha$ and $a_1=\alpha+\beta$, for some $f$. I'll doing so because, at the end of the demonstration, we get a simpler problem to be solved (when $a_0=\alpha=0$ and $a_1=\beta$).

Suppose $(1)$ holds for $n$ and $n-1$. We want to show that holds for $n+1$. Then: $$a_{n+1}=a_{n}-\frac{2}{n+1}a_{n-1}=-\alpha \frac{2^{n-1}(n-2)}{n!}+f(\beta,n)-\frac{2}{n+1}\left( -\alpha\frac{2^{n-2}(n-3)}{(n-1)!} +f(\beta,n-1) \right) = $$

$$= -\alpha \frac{2^{n-1}(n-2)}{n!}+\frac{2}{n+1}\alpha\frac{2^{n-2}(n-3)}{(n-1)!} -\frac{2}{n+1}f(\beta,n-1) +f(\beta,n) = $$

$$= -\alpha \frac{2^{n-1}(n-2)(n+1)}{n!(n+1)} +\alpha\frac{2^{n-1}n(n-3)}{(n+1)n!} -\frac{2}{n+1}f(\beta,n-1) +f(\beta,n) = $$

$$= -\alpha \frac{2^{n-1}}{(n+1)!} \left( (n-2)(n+1)-n(n-3) \right) -\frac{2}{n+1}f(\beta,n-1) +f(\beta,n) = $$

$$= -\alpha \frac{2^{n-1}}{(n+1)!} \left( 2n-2 \right) -\frac{2}{n+1}f(\beta,n-1) +f(\beta,n) = $$ Finally for some unknow $f$: $$=-\alpha \frac{2^{n}(n-1)}{(n+1)!} +f(\beta,n+1)$$

Now we check that $(1)$ holds for the first step of the sequence:

\begin{array}{|c|c|} \hline n& a_n \\ \hline 0& \alpha \\ \hline 1& \alpha + \beta \\ \hline 2& \beta \\ \hline 3& -\frac{2}{3}\alpha + \frac{1}{3}\beta \\ \hline 4& -\frac{2}{3}\alpha - \frac{1}{6}\beta \\ \hline 5& -\frac{2}{5}\alpha - \frac{3}{10}\beta \\ \hline \end{array}

It's easy to check that the coefficients of $\alpha$ at the step $n$ are $\frac{2^n(n-1)}{(n+1)!}$ So by induction, (1) holds for every $n$

But the list line of the demonstration imposes an aditional constraint to $f$: $$f(\beta,n+1) = f(\beta,n)-\frac{2}{n}f(\beta,n-1)$$ that can be rewritten as: $$b_{n} = b_{n-1} - \frac{2}{n}b_{n-2}$$ With $b_0=0$ and $b_1=\beta$.

Answer 3

I have found an alternative way to prove $a_n=O(n^{-2}~)$ using generating functions.

Letting $A(t)=\sum a_n t^n$ we get an Initial Value Problem \begin{equation}\begin{cases}(1-t)A'(t)+(2t-1)A(t)=a_1-a_0 \\A(0)=a_0\end{cases} \tag1\end{equation} and it solves to $$A(t)=a_0(1-t)e^{2t}+(a_1-a_0)(1-t)e^{2t}\int_{0}^{t} \frac{e^{-2s}}{(1-s)^2}ds$$ After integration by parts and some rearrangement, it can be written that \begin{equation}A(t)=F(t)+2(a_1-a_0)(1-t)e^{2t-2}\int_0^t\frac{ds}{1-s}\end{equation} where $$F(t)=a_1-a_0-(a_1-2a_0)(1-t)e^{2t}+2(a_1-a_0)(1-t)e^{2t}\int_0^t\frac{e^{-2s}-e^{-2}}{1-s}ds$$ is an entire function.

So \begin{equation}A(t)=F(t)+c(1-t)e^{2t}\log(1-t) \tag2\end{equation} with some entire function $F$ and constant $c$.

The entireness of $F$ implies that its Taylor coefficients tend to $0$ more rapidly than any geometric sequence, and of course, it is $O(n^{-2}~)$. We only need to show if $$(1-t)e^{2t}\log(1-t)=\sum\eta_n t^n$$ then $\eta_n=O(n^{-2}~)$. Denote $$(1-t)\log(1-t)=\sum \beta_n t^n,\quad e^{2t}=\sum \gamma_n t^n$$ It is easy to know $$|\beta_n|\leq Kn^{-2},\quad |\gamma_n|\leq Le^{-2n} \quad(\forall n\geq 1)$$ For some positive constant $K$ and $L$. So \begin{eqnarray}|\eta_n| =\left|\sum_{j=0}^n\beta_{n-j}~\gamma_{j}\right|&\leq& \sum_{j=0}^{h(n)}|\beta_{n-j}~\gamma_{j}|+ \sum_{j=h(n)+1}^{n} |\beta_{n-j}~\gamma_{j}|\\ & \leq & K(n-h(n))^{-2}~\sum_{j=0}^{\infty}|\gamma_j|+K_0\sum_{j=h(n)+1}^{\infty}|\gamma_j|\\ &\leq & K_1(n-h(n))^{-2}+K_2 e^{-2(h(n)+1)}\end{eqnarray} for positive constants $K_0,K_1,K_2$ and positive integer $h(n)$. Now let $h(n):= [\log n]$ We get $$|\eta_n|\leq K_1(n-\log n)^{-2} +K_2 e^{-2\log n}\leq M n^{-2}$$ for large $n$, as desired.