[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!

Advertisements
This entry was posted in Random and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s