# Two Sequences Defined by Recurrence

Leo Giugiuc posted Dorin Marghidanu's problem with a proof (Proof 2 below) at the CutTheKnotMath facebook page:

Let $\{a_n\},\;\{b_n\},$ $n=0,1,2,\ldots$ such that $a_0,b_0\gt 0,$ $\displaystyle a_{n+1}=a_{n}+\frac{1}{2b_n}$ and $\displaystyle b_{n+1}=b_{n}+\frac{1}{2a_n},$ $n\ge 0.$ Prove that $\max\{a_{2014},\; b_{2014}\}\gt 2015.$

### Proof 1

Multiply the two recurrences:

$\displaystyle a_{n+1}b_{n+1}=a_{n}b_{n}+\frac{1}{4a_{n}b_{n}}+1.$

For $x_{n}=a_{n}b_{n}$ the recurrence becomes:

(1)

$\displaystyle x_{n+1}=x_{n}+\frac{1}{4x_{n}}+1.$

Using the Arithmetic Mean - Geometric Mean inequality this leads, for $n=1$ to

$\displaystyle x_1=x_0+\frac{1}{4x_0}+1\ge 2\sqrt{\frac{1}{4}}+1=2.$

For $n\gt 1,$ from (1), $x_{n+1}\gt x_{n}+1,$ so that $x_{2}\gt 3,$ and, in general, $x_{n}\gt n+1$ which causes at least one of $a_n$ and $b_n$ to exceed $\sqrt{n+1}.$ In particular, $\max\{a_{2014},\; b_{2014}\}\gt 2015.$

### Proof 2

With $x_{n}=a_{n}+b_{n},$ for all $n\ge 0,$

\displaystyle\begin{align} x_{n+1}&= a_{n+1}+b_{n+1}\\ &=a_{n}+b_{n}+\frac{1}{2}\left(\frac{1}{a_n}+\frac{1}{b_n}\right)\\ &\ge a_{n}+b_{n}+\frac{2}{a_{n}+b_{n}}\\ &=x_{n}+\frac{2}{x_n}. \end{align}

By the AM-GM inequality, $x_1\ge 2\sqrt{2}.$ We'll prove by induction that $x_{n}\gt 2\sqrt{n+1},$ for $n\gt 1.$

Consider function $f:\;[2\sqrt{2},\infty )\rightarrow\mathbb{R},$ $\displaystyle f(x)=x+\frac{2}{x}.$ Obviously, $f$ is strictly increasing, implying

$\displaystyle x_{2}\ge f(x_{1})\ge f(2\sqrt{2})=\frac{5}{\sqrt{2}}\gt 2\sqrt{3}.$

Assume, for a $k\ge 3,$ $x_{k-1}\gt 2\sqrt{k}.$ From this,

$\displaystyle x_{k}\ge f(x_{k-1})\gt f(2\sqrt{k})=\frac{2k+1}{\sqrt{k}}\gt 2\sqrt{k+1}.$

In particular, $a_{2014}+b_{2014}\gt 2\sqrt{2015}$ so that at least one of them exceeds $\sqrt{2015}.$