## [Soln] Problem-Solving Strategies Ch 9 Problem 25

Engel 9.25. The sequence $x_n$ is defined by $x_1 = 1/2$, $x_{k+1} = x_k^2 + x_k$. Find the integer part of the sum

$\displaystyle\frac{1}{x_1 + 1} + \frac{1}{x_2+1} + \dots + \frac{1}{x_{100}+1}.$

Note: This problem was taken from Arthur Engel’s Problem-Solving Strategies.

Let’s work out the small values of $x_n$:

\begin{aligned} x_1 &= \frac{1}{2}, \\ x_2 &= \frac{1}{4} + \frac{1}{2} = \frac{3}{4}, \\ x_3 &= \frac{9}{16} + \frac{3}{4} = \frac{21}{16}, \\ x_4 &= \frac{441}{256} + \frac{21}{16} = 3 \frac{9}{256}. \end{aligned}

$x_1$ and $x_2$ are smaller than 1. $x_3$ is greater than 1. Looking at the recurrence relation, note that a term is bigger than the square of the previous terms. This means that once our numbers go past 1, they increase very very quickly. For example, compare this with the sequence $2, 4, 8, 16, \dots$. The $x_n$ sequence is going to grow even faster than this.

Now, noting that

$\displaystyle\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots = 1,$

this suggests that $\frac{1}{x_1+1} + \frac{1}{x_2+1} + \dots$ is going to converge very quickly as well, and to a small value.

How can we use the recurrence relation to get the terms $\frac{1}{x_k + 1}$? Well, $x_k + 1$ is already lurking in the RHS:

\begin{aligned} x_{k+1} &= x_k(x_k + 1), \\ \frac{1}{x_{k+1}} &= \frac{1}{x_k(x_k + 1)} \\ &= \frac{1}{x_k} - \frac{1}{x_k + 1}, \\ \frac{1}{x_k + 1} &= \frac{1}{x_k} - \frac{1}{x_{k+1}}. \end{aligned}

This is a big result! We can turn the sum we are supposed to evaluate into a telescoping sum, canceling many terms in the middle:

\begin{aligned} \sum_{k = 1}^{100} \frac{1}{x_k + 1} &= \sum_{k=1}^{100} \frac{1}{x_k} - \frac{1}{x_{k+1}} \\ &= \frac{1}{x_1} - \frac{1}{x_{101}} \\ &= 2 - \frac{1}{x_{101}}.\end{aligned}

Hence, the integer part of the sum is less than 2. From our earlier analysis, we know that for large $n$, $x_n$ is large, which means that $\frac{1}{x_n+1}$ is small, almost definitely less than 1, which means that the sum above would be equal to “1 point something”. We just need to show that

$\displaystyle\frac{1}{x_{101}} < 1$, or $x_{101} > 1$.

But that is (more or less obvious), we always have $x_{k+1} \geq x_k$, which means that $x_{101} \geq x_3 > 1$.

Thus, the integer part of the sum is 1. Done!