Engel 9.25. The sequence is defined by , . Find the integer part of the sum
Note: This problem was taken from Arthur Engel’s Problem-Solving Strategies.
Let’s work out the small values of :
and are smaller than 1. 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 . The sequence is going to grow even faster than this.
Now, noting that
this suggests that is going to converge very quickly as well, and to a small value.
How can we use the recurrence relation to get the terms ? Well, is already lurking in the RHS:
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:
Hence, the integer part of the sum is less than 2. From our earlier analysis, we know that for large , is large, which means that 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
, or .
But that is (more or less obvious), we always have , which means that .
Thus, the integer part of the sum is 1. Done!