Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.