# How to find the sum of the number series written recursively?

I have the following number series, written in next way:
$$x_1 = 2$$
$$x_{n+1} = x_n^2 - x_n + 1$$, $$n \geq 1$$

and it needs to find sum of:
$$\sum_{n=1}^{\infty} \frac{1}{x_n}$$

At the moment, I haven't had much of progress, namely:
I know, that in the end of solving this task I'll have next type of situation:
$$(x_1+x_2) - (x_2 +x_3) - (x_3 + x_4) ... (x_{n-1} + x_n)$$
so elements mutually cancel out inside the sum and we get desired result

But every action requires mathematical proof unless it is obviously true

$$x_n$$ is growing, thus $$\frac{1}{x_n}$$ decreases, power of decreasing $$\gt 1$$ thus the number series is convergent, but yet again, I don't have strictly math proof of this fact, but it requires

I'll be very grateful for any help

• Everything you have done is correct. Just notice that $x_n \to \infty$ doesn't prove that $\sum \frac{1}{x_n}$ converges, as $x_n := n$ shows. Jan 17, 2020 at 20:48
• Your sequence is OEIS sequence A000058 "Sylvester's sequence" which has much information. Check it out. Jan 17, 2020 at 21:37

Duplicate of this question, found on approach0.xyz. But this question doesn't have any answer, so I'll just share the important hint given in the comments by @Kelenner: $$\frac{1}{x_n -1} - \frac{1}{x_{n + 1} -1} = \frac{1}{x_n}$$ As you detailed in the comments, you have used the hint to show the sum is equal to $$\frac{1}{x_1 - 1}$$. For the sake of completeness, I'll write it down here.

First, we have \begin{align} \frac{1}{x_n -1} - \frac{1}{x_{n + 1} -1} & = \frac{1}{x_n -1} - \frac{1}{x_n^2 - x_n + 1 -1} \\ & = \frac{x_n}{x_n^2 -x_n} - \frac{1}{x_n^2 - x_n} \\ & = \frac{x_n - 1}{x_n^2 -x_n} = \frac{1}{x_n}. \end{align} Therefore, we obtain by a telescoping argument \begin{align} \sum_{n = 1}^{\infty} \frac{1}{x_{n}} & = \sum_{n = 1}^{\infty} \frac{1}{x_n -1} - \frac{1}{x_{n + 1} -1} = \lim_{m \to \infty} \left(\sum_{n = 1}^{m} \frac{1}{x_n - 1} - \frac{1}{x_{n + 1} - 1}\right) \\ & = \lim_{m \to \infty}\left( \frac{1}{x_1 - 1} - \frac{1}{x_{m + 1} - 1}\right) = \frac{1}{x_1 - 1} + \lim_{n \to \infty} \frac{-1}{x_{n + 1} -1} = \frac{1}{x_1 - 1} \end{align} As we have $$x_n \to \infty$$.

This can be seen by showing $$x_n \ge n$$ by induction. For $$n = 1$$ its clear, so we begin at $$n = 2$$.

Base step: $$x_2 = 3 \ge 2$$.

Induction hypothesis: $$x_n \ge n$$ holds for some $$n \in \mathbb{N}_{\ge 2}$$.

Induction step: $$n \to n + 1$$. Since $$x_n \ge 2$$ for all $$n$$ we have $$x_{n + 1} = x_n(x_n - 1) + 1 \overset{\text{IH}}{\ge} (n)(n - 1) + 1 = n^2 - n + 1 \ge n + 1.$$ The last inequality rearranges to $$n^2 \ge 2n \iff n \ge 2$$. So the statement is true for $$n \ge 2$$ but we know its also true for $$n = 1$$, so we are done.

• @Denis Define $y_n:=x_n-1$ so $y_{n+1}=y_n(y_n+1)>y_n^2$. Since $y_2=2$, $n\ge3\implies y_n>2^{2^{n-2}}$.
– J.G.
Jan 17, 2020 at 21:19
• $x_n \ge 1$ is true since $x_1 = 2$ and $(x_n)_n$ is monotonically increasing. Therefore $x_n$ and $x_n - 1$ are positive. This ensures we can conclude $x_n(x_n - 1) \ge n(n-1)$ from $x_n \ge n$. Therefore we have $x_{n + 1} \ge n^2 - n - 1$, but we want $x_{n + 1} \ge (n + 1)$. If we show $n^2 - n - 1 \ge n + 1$ we are finished. This can be rearranged to $n^2 \ge 2n$. As $n$ is positive you can divide by it to obtain $n \ge 2$. So we have $x_n \ge n$ for $n \ge 2$. We know it folds for $n = 1$, so the statement is proven. Jan 17, 2020 at 23:01
• I've corrected. Since $x_1 = 2$ and $(x_n)$ is monotonically increasing, $x_n \ge$ 2 for all $n$. Therefore, $x_n - 1 \ge 1$. This ensures that $x_n(x_n -1) \ge n(n-1)$ works. We are using the following statement: If $a,b \ge 1$ we have: $a \ge b$ implies $a(a - 1) \ge b(b - 1)$. Can you come up with a counterexample to this statement if $a$ and $b$ are not $\ge 1$? Jan 17, 2020 at 23:15
• @Denis It is correct that $x_n \ge 2$ also follows from the induction hypothesis. Jan 17, 2020 at 23:21

To prove the limit is $$1$$, prove two results by induction, firstly that $$x_{n+1}=1+\prod_{j=1}^nx_j$$, and secondly that $$\sum_{j=1}^n\frac{1}{x_j}=1-\frac{1}{\prod_{j=1}^nx_j}=1-\frac{1}{x_{n+1}-1}$$. The first proof's inductive step is$$x_{k+1}=1+\prod_{j=1}^kx_j\implies x_{k+2}=1+(x_{k+1}-1)x_{k+1}=1+\prod_{j=1}^{k+1}x_j,$$while the second's is$$\sum_{j=1}^k\frac{1}{x_j}=1-\frac{1}{x_{k+1}-1}\implies\sum_{j=1}^{k+1}\frac{1}{x_j}=1-\frac{1}{x_{k+1}(x_{k+1}-1)}=1-\frac{1}{x_{k+2}-1}.$$