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?
 A: 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. 
A: 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.
