2
$\begingroup$

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

I've had also next observation:
$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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Ramanujan
    Jan 17, 2020 at 20:48
  • 1
    $\begingroup$ Your sequence is OEIS sequence A000058 "Sylvester's sequence" which has much information. Check it out. $\endgroup$
    – Somos
    Jan 17, 2020 at 21:37

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ @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}}$. $\endgroup$
    – J.G.
    Jan 17, 2020 at 21:19
  • $\begingroup$ $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. $\endgroup$
    – Ramanujan
    Jan 17, 2020 at 23:01
  • $\begingroup$ 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$? $\endgroup$
    – Ramanujan
    Jan 17, 2020 at 23:15
  • $\begingroup$ @Denis It is correct that $x_n \ge 2$ also follows from the induction hypothesis. $\endgroup$
    – Ramanujan
    Jan 17, 2020 at 23:21
1
$\begingroup$

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}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.