Convergence of recurrence relation involving divisors

110 Views Asked by At

I$\let\leq\leqslant\let\geq\geqslant$ thought up a family of sequences, recursively defined by $$a_{n+1}=\frac{d_n^ra_n+a_{d_n}}{d_n^r+1}\quad(n\geq2)$$ where $r,a_1,a_2\in\mathbb R$ are parameters and and $d_n$ denotes the largest proper divisor of $n$. For example, $d_4=2$, $d_5=1$, $d_6=3$. Note that the recurrence relation is invariant under linear transforms of the sequence, meaning that the convergence of $(a_n)$ is equivalent to the convergence of any other sequence satisfying the same recurrence (with the same $r$, as long as $a_1\neq a_2$). So wlog we can assume for example that $a_1=1$ and $a_2=0$.

Question. For which $r\in\mathbb R$ does $a_n\to a_1$?

I have checked the behaviour of the sequence for some values of $r$ close to $0$, and it seems likely that we have convergence for $r>0$. If $r=0$ even after the millionth term the sequence is still somewhere around $0.95a_1+0.05a_2$, so I have some doubts about the convergence.

This question is motivated by the following result:

Theorem. If $r>4$, then $a_n\to a_1$.

The idea behind the proof is that (if $a_2\leq a_1$) the primes pull up the sequence with $\frac{a_1}2$ and that when $r$ is large, the sequence does not decrease too fast after being 'pulled up' by a prime, meaning that approximately we get a total 'pull up' of $\frac{a_1}2+\frac{a_1}4+\frac{a_1}8+\cdots=a_1$ (due to the division by $2$ in the recurrence): $\frac{a_1}2$ coming from the most recent prime, $\frac{a_1}4$ the pull up from an earlier prime, etc.

I'm including my proof here because I hope the weakest estimates can be improved for smaller values of $r$.

Proof.

Suppose wlog that $a_1=1$ and $a_2\leq a_1$, so that $a_n\in[a_2,1]$ for all $n\geq1$. Let $m_N=\min_{n\in[\sqrt N,N]}a_n$. The idea is to use this sequence to control the size of $d_n$, which is at least $\sqrt n$ if $n$ is composite.

1. Some results on the behaviour of $m_n$
Let $N>0$. We'll prove with induction that $a_n\geq m_N$ for $n\geq\sqrt N$. For $n\in[\sqrt N,N]$ this is trivial. Suppose it's true for $\lceil\sqrt N\rceil,\ldots,N,\ldots,n$. If $n$ is composite, $d_n\geq\sqrt n\geq\sqrt N$ and hence $a_{n+1}=\frac{d_n^ra_n+a_{d_n}}{d_n^r+1}\geq m_N$ by the induction hypothesis applied for $n$ and $d_n$. If $n$ is prime, then $a_{n+1}=\frac{a_n+1}2\geq a_n\geq m_N$.

Consequently, $m_{N+1}\geq m_N$, that is, $(m_n)$ is increasing. It suffices to show that $m_n\to1$.

2. Bounding $a_n$ from below when $n$ is not much bigger than a given prime
Let $p$ be prime. We'll prove with induction that $$a_{p+n}\geq\left(1-\frac1{p^{r/2}}\right)^{n-1}\frac{m_p+1}2\quad\text{ for }n\geq1.$$ If $n=1$ this is $a_{p+1}\geq\frac{m_p+1}2$, which is true because $a_{p+1}=\frac{a_p+1}2$ and $a_p\geq m_p$. Suppose it holds for $n$. If $p+n$ is prime, then $a_{p+n+1}=\frac{a_{p+n}+1}2\geq\frac{m_p+1}2$ and the claim follows trivially because $1-\frac1{p^{r/2}}<1$. If $p+n$ is not prime we have $a_{p+n+1}\geq a_{p+n}\left(1-\frac1{d_{p+n}^r+1}\right)$. Because $1-\frac1x$ is increasing and $d_{p+n}\geq\sqrt{p+n}\geq\sqrt p$, it follows that $a_{p+n+1}\geq a_{p+n}\left(1-\frac1{p^{r/2}}\right)$.

3. Exploiting the lower bound
Let $(p_n)$ be a sequence of primes for which $p_n^2< p_{n+1}<2p_n^2$. Note that Bertrand's postulate guarantees that such a sequence exists. Using the lower bound above (which is weakest for $p_n+(p_{n+1}-p_n)$) we have $$m_{p_{n+1}}\geq\left(1-\frac1{p_n^{r/2}}\right)^{p_{n+1}-p_n-1}\frac{m_{p_n}+1}2.$$

It's not hard to see (by induction) that this implies $$m_{p_{n+k}}\geq\sum_{l=1}^k2^{-l}\prod_{j=k-l}^{k-1}\left(1-\frac1{p_{n+j}^{5/2}}\right)^{p_{n+j+1}-p_{n+j}-1}$$ for $k\geq1$.

4. Technical part, finishing the proof
Let $0<\varepsilon<1$. Because $\lim_{x\to\infty}(1-\frac1{x^{r/2}})^{x^2}=1$ and $$\left(1-\frac1{p_n^{r/2}}\right)^{2p_n^2}\leq\left(1-\frac1{p_n^{r/2}}\right)^{p_{n+1}-p_n-1}\leq1$$ we also have $\left(1-\frac1{p_n^{r/2}}\right)^{p_{n+1}-p_n-1}>1-\varepsilon$ for all $n\geq N$ for some $N$. Hence $$m_{p_{N+k}}\geq\sum_{l=1}^k\left(\frac{1-\varepsilon}2\right)^l.$$ The RHS approaches $\frac{1-\varepsilon}{1+\varepsilon}$ if $k\to\infty$. Hence there exists $k\geq1$ with $m_{p_{N+k}}\geq\frac{1-\varepsilon}{1+\varepsilon}-\varepsilon$. Because $\varepsilon$ is arbitrary, we can find an $m_{p_{N+k}}$ arbitrarily close to $1$. Because $(m_n)$ is increasing, we have $m_n\to1$, and hence $a_n\to1$.


As you can see, the only place where the condition $r>4$ shows up is in $\lim_{x\to\infty}(1-\frac1{x^{r/2}})^{x^2}=1$. If $r\leq4$ the proof fails because $\lim_{x\to\infty}(1-\frac1{x^{r/2}})^{x^2}\leq\frac1e$.

Possible improvement. For non-prime indices we used the bound $d_n\geq\sqrt n$. Note that this lower bound for $d_n$ appears in the limit above (raised to the $r$th power), which is more or less the only point where the size of $r$ matters. Perhaps we can adjust the proof for smaller values of $r$ if we have a better bound for $d_n$ (say $d_n\geq n^{2/3}$) and treat the $n$'s which do not satisfy the bound separately (like primes were treated separately in the proof above), in the case of $n^{2/3}$, any number that is not a prime or the square of a prime. Unfortunately, since trying to use $\lim_{x\to\infty}(1-\frac1{x^{r/2}})^{x^s}=1$ (for some $s$) requires choosing the sequence of primes $(p_n)$ in such a way that (for example) $p_n^s<p_{n+1}<2p_n^s$, it becomes necessary to modify $m_n$ too (in order to obtain a generalised lower bound for $m_n$'s as above), possibly taking away the useful inequality $a_{n}\geq m_N$ for $n\geq N$. This may be difficult, but at least the proof above gives us some ideas to start from.