A limit of a recursion involving the prime number function

Question

Suppose $A_1=1$, $B_1=2$ and

$\left\{ \begin{array}{l} A_{k+1}=A_k\cdot (p_{k+1}-1)+B_k\\ B_{k+1}=B_k\cdot p_{k+1} \end{array} \right. $

where $p_k$ is the $k$-th prime number. I would like a formal proof of that

$\displaystyle\lim_{n\to\infty}\frac{A_n}{B_n}=1$.

I've checked it computationally, but am unsure about the proof.

Answer 1

Why, let's see what happens to that ratio. Say, $r_n={A_n\over B_n}$. Then $$ r_{k+1}={A_{k+1}\over B_{k+1}}={A_k\cdot (p_{k+1}-1)+B_k\over B_k\cdot p_{k+1}}={r_k(p_{k+1}-1)+1\over p_{k+1}}=r_k+{1-r_k\over p_{k+1}} $$ So, since $0<r_1<1$ and $p>0$, all $r_k$ are also strictly between 0 and 1, and $r_{k+1}>r_k$. This is a monotone bounded sequence, hence it must have a limit. Now just what that limit might be? Let's call it $r_\infty$. Then $$r_\infty=r_1+{1-r_1\over p_2}+{1-r_2\over p_3}+\dots\ge {1-r_\infty\over p_2}+{1-r_\infty\over p_3}+\dots=(1-r_\infty)\left({1\over p_2}+{1\over p_3}+\dots\right)$$

But the sum of $1\over p$ diverges, so any $r_\infty<1$ would not do. Therefore $r_\infty=1$.

Upd. I've just realized it would be probably better to go along the lines of $1-r_{k+1}=(1-r_k)(1-{1\over p_{k+1}})$ and to point out that the infinite product $\prod(1-{1\over p_i})$ tends to zero. Whatever.

Answer 2

Let $r_k=\frac{A_k}{B_k}$. We have $B_k=p_1\cdots p_k$ so $$r_{k+1}-1=(r_k-1)\cdot\left(1-\frac1{p_{k+1}}\right).$$

It follows that $$r_n=1+\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_n}\right)$$ and it suffices to note that $\prod_p\left(1-\frac1p\right)=0$.

---

In general, when dealing with a linear recursion (with possibly non-constant coefficients) it is worth homogenizing it, that is, getting rid of the constant term. In this case however I discovered it in the following (deeper) way:

From $$r_{k+1}=r_k\cdot\left(1-\frac1{p_{k+1}}\right)+\frac1{p_{k+1}}$$ one may note that $$r_k=1+\sum_{\substack{p\mid n\implies p\leq p_k\\ n\text{ even}}}\frac{\mu(n)}n.$$ Because $\displaystyle\sum_{\substack{p\mid n\implies p\leq p_k\\ n\text{ odd}}}\!\!\!\tfrac{\mu(n)}n=-2\sum_{\substack{p\mid n\implies p\leq p_k\\ n\text{ even}}}\!\!\!\tfrac{\mu(n)}n$ one sees that $$r_k-1=\sum_{p\mid n\implies p\leq p_k}\frac{\mu(n)}n=\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_k}\right).$$