3
$\begingroup$

Starting from a messy differential equation, I arrived at the following simple pair of update rules: $ a(t+1) = a(t) + \frac{1}{b(t)}$ $b(t+1) = b(t) + \frac{b(t)}{a(t)}$ My question is: suppose we initialize it somewhere (say $a(0)=b(0)=1$). How will the answer grow with time?

Intuition: as time goes on, both $a(t),b(t)$ increase, but the increase of each inhibits the rate at which the other can grow. Simulations show that $a(t)$ seems to approach a finite limit while $b(t)$ appears to exponentially in $t$.

1 Answers 1

3

Yes, we can show that $\displaystyle a_n$ is convergent (say with limit $a$) and that $\displaystyle b_n$ is unbounded, with $\displaystyle b_n^{1/n} \to 1 + \frac{1}{a}$

I take the sequence to start with $\displaystyle 1$, so assume $\displaystyle a_1 = b_1 = 1$.

It is easy to prove that $\displaystyle b_n \ge a_n \ge 1$ (by induction) and thus we have that $b_n \ge n$.

Thus we have that $\displaystyle a_{n+1} - a_n \le \frac{1}{n}$

Adding up gives us $\displaystyle a_{n} - 1 \le \sum_{k=1}^{n-1} \frac{1}{k}$

and so $\displaystyle a_n \lt 2 \log (n+1)$

Now $\displaystyle \frac{b_{n+1}}{b_n} = 1 + \frac{1}{a_n}$ and taking the telescoping product gives us

$\displaystyle b_n = \prod_{k=1}^{n-1} (1 + \frac{1}{a_k}) \tag{1}$

Now since $a_n \lt 2 \log(n+1)$ we have that

$\displaystyle b_n \gt \prod_{k=1}^{n-1} \left(1 + \frac{1}{2\log (k+1)}\right)$

Using the inequality $\displaystyle 1 + a \ge 2\sqrt{a}$ we get

$\displaystyle b_n \gt \frac{2^{(n-1)/2}}{\sqrt{\log (n-1)!}}$

Thus $\displaystyle b_n \gt \frac{2^{(n-1)/2}}{n^2}$ for sufficiently large $\displaystyle n$ (Stirling approximation gives us $\displaystyle \log n! \sim n \log n$)

Thus

$\displaystyle a_{n+1} - a_n \lt \frac{n^2}{2^{(n-1)/2}}$

for sufficiently large $n$.

Thus $\displaystyle a_n \lt C + \sum_{k=1}^{\infty} \frac{k^2}{2^{(k-1)/2}}$

Since the latter series converges, $\displaystyle a_n$ is bounded above.

We can also easily see that $a_{n+1} \gt a_n$.

Thus $\displaystyle a_n$ is convergent, to say $\displaystyle a$.

Using (1) we see that

$\displaystyle \frac{\log b_n}{n} = \frac{1}{n}\sum_{k=1}^{n-1} \log (1+\frac{1}{a_k})$

Since $\log (1 + \frac{1}{a_n})$ converges, so does the arithmetic mean (and to the same limit).

Thus

$\displaystyle \frac{\log b_n}{n} \to \log (1 + \frac{1}{a})$

Thus

$\displaystyle b_n^{1/n} \to 1 + \frac{1}{a}$