Sequence Inequality question from RMO 2018

Question

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?

Answer 1

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.

Answer 2

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.