# Sequence Inequality question from RMO 2018

Define a sequence {$$a_n$$} of real numbers by $$a_1 = 2$$ and $$a_{n+1} = \dfrac{a_n^2+1}{2}$$, for $$n\ge 1$$,

Prove that for every natural number $$N, \sum_{j=1}^{N} \frac{1}{1+a_j} \lt 1$$

I tried mathematical induction after coming to the step where

$$Sum_n = \frac{1}{2}\left(\frac{a_1-1}{a_2-1} + \frac{a_2-1}{a_3-1} +\cdots \frac{a_n-1}{a_{n+1}-1}\right)$$.

Having gotten this how would go about proving it using induction?

To get $$\dfrac{1}{a_n+1}$$, Firse subtract $$1$$ from both sides $$a_{n+1}-1=\frac{a_{n}^2-1}{2}=\frac{(a_n+1)(a_n-1)}{2}.$$ Then take the multiplicative inverse ( assume $$a_n\neq \pm1$$, as we'll see later) $$\frac{1}{a_{n+1}-1}=\frac{2}{(a_n+1)(a_n-1)}$$ where the right side can be written as $$\frac{1}{a_n-1}-\frac{1}{a_n+1}.$$ Thus $$\frac{1}{a_n+1} = \frac{1}{a_n-1}-\frac{1}{a_{n+1}-1}$$ Sum up both sides from $$1$$ to $$N$$ we get $$\sum_{k=1}^{N}\frac{1}{a_k+1}=\frac{1}{a_1-1}-\frac{1}{a_{N+1}-1}=1-\frac{1}{a_{N+1}-1}.$$ Now we just need to prove $$a_n>1$$ for all $$n\geqslant2$$. Notice that $$a_{n+1}-a_{n}=\frac{a_{n}^2+1}{2}-a_n=\frac{(a_n-1)^2}{2}>0.$$ Then $$\{a_n\}$$ is incresing with $$a_1=2$$. Hence the proof is done.

• Awesome!!. This only is doable by a high school student – Satish Ramanathan Oct 30 '18 at 17:22

By computing $$1-\sum_{k=1}^{N}\frac{1}{a_k+1}$$ with the help of Mathematica it is not difficult to conjecture that $$1-\sum_{k=1}^{N}\frac{1}{a_k+1} = \frac{2^{2^N-1}}{\prod_{k=1}^{N}b_k}\tag{1}$$ with $$\{b_n\}_{n\geq 1}=\{3,7,37,1033,868177,701129422753,\ldots\}$$.
It looks like $$b_n = (a_n+1) 2^{2^{n-1}-1}$$, hence if we manage to prove

$$\frac{1}{a_N+1} = \frac{2^{2^{N-1}-1}}{\prod_{k=1}^{N-1}(a_k+1)2^{2^{k-1}-1}}-\frac{2^{2^N-1}}{\prod_{k=1}^{N}(a_k+1)2^{2^{k-1}-1}},\tag{2}$$ which is equivalent to $$\frac{1}{a_N+1} = \frac{1}{2^{N}\prod_{k=1}^{N-1}(a_k+1)}\left(1-\frac{2}{a_N+1}\right)\tag{3}$$ or to $$1 = \frac{a_N-1}{2^{N}\prod_{k=1}^{N-1}(a_k+1)}\tag{4}$$ we are done. On the other hand $$(4)$$ is exactly what we get by "unpacking"

$$a_N-1 = \frac{a_{N-1}+1}{2}(a_{N-1}-1) \tag{5}$$ through induction. Now we may remove the conjectural part. $$(5)\mapsto(4)\mapsto(3)\mapsto(2)$$ and from $$(2)$$ it follows that

$$\sum_{k=1}^{N}\frac{1}{a_k+1}= 1-\frac{2^N}{\prod_{k=1}^{N}(a_k+1)}.\tag{6}$$

The given exercise is equivalent to the following claim: if $$k_1=2$$ and $$k_{n+1}=k_n^2-k_n+1$$, then $$1 = \sum_{n\geq 1}\frac{1}{k_n} = \frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\frac{1}{1807}+\ldots$$ which is pretty reminiscent of some Machin-like formulas.
Expert problem solvers may easily recognize the Sylvester sequence A000058.

• I could get only the unpacking part. Even to formulate the conjecture, you may have to be extremely knowledgeable and this problem is for high school students and wonder how they are expected to solve this? – Satish Ramanathan Oct 30 '18 at 15:39
• @SatishRamanathan: that is an issue afflicting the majority of mathematical competitions for young students. In order to solve a problem like this, one actually does not need to know anything, just to formulate some version of $(6)$, then to prove it by induction. On the other hand knowledge and/or computational resources help a lot. – Jack D'Aurizio Oct 30 '18 at 15:43