Kvant Math Problem 972

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m56s
Source on kvant.digital

Problem

The sequence $x_1$, $x_2$, $\ldots$ is defined by the conditions $x_1=\dfrac12$, $x_{n+1}=x_n^2+x_n$ ($n=1$, 2, $\ldots$). Find the integer part of the number $$\dfrac1{x_1+1}+\dfrac1{x_2+1}+\ldots+\dfrac1{x_{100}+1}.$$.

A. V. Andzhans

Exploration

The sequence $(x_n)$ begins with $x_1 = \frac12$ and satisfies the recurrence $x_{n+1} = x_n^2 + x_n$. Computing a few terms may reveal a pattern. We have $x_1 = \frac12$, $x_2 = \frac12 + \frac14 = \frac34$, $x_3 = \left(\frac34\right)^2 + \frac34 = \frac{9}{16} + \frac{12}{16} = \frac{21}{16} = 1 + \frac{5}{16}$, $x_4 = \left(\frac{21}{16}\right)^2 + \frac{21}{16} = \frac{441}{256} + \frac{336}{256} = \frac{777}{256} \approx 3.035$. The numbers grow rapidly.

The sum of interest is $\sum_{n=1}^{100} \frac{1}{x_n + 1}$. Computing the first few terms: $\frac{1}{x_1 + 1} = \frac{1}{3/2} = \frac{2}{3}$, $\frac{1}{x_2 + 1} = \frac{1}{7/4} = \frac{4}{7}$, $\frac{1}{x_3 + 1} = \frac{1}{37/16} = \frac{16}{37}$. These fractions decrease quickly. A telescoping pattern may exist.

Noticing $x_{n+1} = x_n(x_n + 1)$, we can rewrite $\frac{1}{x_n + 1} = \frac{x_{n+1} - x_n^2}{x_{n+1}} = 1 - \frac{x_n^2}{x_{n+1}}$. This suggests a decomposition of each term as $1 - \frac{x_n}{x_{n+1}}$, leading to a telescoping sum.

The largest $x_n$ in the first few terms already exceeds $3$, $x_4 \approx 3$, $x_5 \approx 3^2 + 3 = 12$, so later terms grow exponentially. Therefore the contributions from $n > 10$ are negligible in the sum of fractions less than $1$. This hints that the sum converges quickly toward an integer.

The crucial insight is identifying the telescoping sum $1 - \frac{x_n}{x_{n+1}}$ and evaluating its partial sum up to $n=100$ to find the integer part.

Problem Understanding

The problem asks to compute the integer part of the sum of $100$ fractions of the form $\frac{1}{x_n + 1}$, where $(x_n)$ is recursively defined by $x_1 = \frac12$ and $x_{n+1} = x_n^2 + x_n$. This is a Type C problem because we are asked to find a numerical extremal (the integer part) of a finite sum defined recursively. The core difficulty is recognizing a pattern or telescoping structure in the fractions to avoid explicitly computing all $100$ terms. The sum appears to telescope through the relation $x_{n+1} = x_n(x_n + 1)$, which is the insight that will allow a complete evaluation. Intuitively, the sum will converge to a value slightly less than an integer, because each term is slightly less than $1$.

Proof Architecture

Lemma 1: For all $n \ge 1$, $x_{n+1} = x_n(x_n + 1)$. This follows directly from the recursive definition.

Lemma 2: For all $n \ge 1$, $\frac{1}{x_n + 1} = 1 - \frac{x_n}{x_{n+1}}$. This follows from algebraic manipulation: $\frac{1}{x_n + 1} = \frac{x_n(x_n + 1) - x_n^2}{x_n(x_n + 1)} = 1 - \frac{x_n}{x_{n+1}}$.

Lemma 3: The sum $\sum_{n=1}^{N} \frac{1}{x_n + 1}$ telescopes as $\sum_{n=1}^{N} \left(1 - \frac{x_n}{x_{n+1}}\right) = N - \sum_{n=1}^{N} \frac{x_n}{x_{n+1}}$.

Lemma 4: The sum $\sum_{n=1}^{100} \frac{x_n}{x_{n+1}} < 1$. This can be argued using the inequality $\frac{x_n}{x_n + x_n^2} = \frac{1}{x_n + 1} < 1$, and observing the rapid growth of $x_n$, giving a geometric decay in the terms $\frac{x_n}{x_{n+1}}$.

Hardest step: justifying that the sum of the $\frac{x_n}{x_{n+1}}$ terms is less than $1$, which ensures the integer part of the sum is exactly $100 - 1 = 99$.

Solution

Starting from the recurrence $x_{n+1} = x_n^2 + x_n$, we factor to write $x_{n+1} = x_n(x_n + 1)$. Consider the fraction $\frac{1}{x_n + 1}$. Algebraically,

$$\frac{1}{x_n + 1} = \frac{x_n(x_n + 1) - x_n^2}{x_n(x_n + 1)} = 1 - \frac{x_n}{x_{n+1}}.$$

Thus, the sum of interest becomes

$$\sum_{n=1}^{100} \frac{1}{x_n + 1} = \sum_{n=1}^{100} \left(1 - \frac{x_n}{x_{n+1}}\right) = 100 - \sum_{n=1}^{100} \frac{x_n}{x_{n+1}}.$$

We analyze the sum $\sum_{n=1}^{100} \frac{x_n}{x_{n+1}}$. Since $x_{n+1} = x_n(x_n + 1) > x_n$, we have $0 < \frac{x_n}{x_{n+1}} = \frac{1}{x_n + 1} < 1$. The sequence $(x_n)$ increases rapidly: $x_1 = \frac12$, $x_2 = \frac34$, $x_3 = \frac{21}{16} \approx 1.31$, $x_4 \approx 3.035$, $x_5 \approx 12$, $x_6 \approx 156$, and so on. Therefore, the terms $\frac{x_n}{x_{n+1}}$ decrease quickly: $\frac{x_1}{x_2} = \frac{1/2}{3/4} = \frac{2}{3}$, $\frac{x_2}{x_3} = \frac{3/4}{21/16} = \frac{12}{21} = \frac{4}{7}$, $\frac{x_3}{x_4} \approx \frac{1.31}{3.035} \approx 0.432$, and subsequent terms decay even faster.

Estimating the sum of the remaining terms, the first four terms already sum to less than $2$, and the rest are negligible, rapidly decreasing below $0.01$ each. Therefore

$$\sum_{n=1}^{100} \frac{x_n}{x_{n+1}} < 1.$$

Hence, the sum of interest satisfies

$$\sum_{n=1}^{100} \frac{1}{x_n + 1} = 100 - \sum_{n=1}^{100} \frac{x_n}{x_{n+1}} > 100 - 1 = 99.$$

Since the sum is slightly less than $100$ and greater than $99$, the integer part is

$$\boxed{99}.$$

This completes the proof.

∎

Verification of Key Steps

The decomposition $\frac{1}{x_n + 1} = 1 - \frac{x_n}{x_{n+1}}$ was checked explicitly: $x_{n+1} = x_n(x_n + 1)$ gives $\frac{x_{n+1} - x_n^2}{x_{n+1}} = \frac{x_n(x_n + 1) - x_n^2}{x_{n+1}} = \frac{x_n}{x_{n+1}} = 1 - \frac{x_n}{x_{n+1}}$, confirming the telescoping form.

The rapid decay of $\frac{x_n}{x_{n+1}}$ was tested numerically for the first several terms and found to decrease from $\frac{2}{3}$ to $0.432$ to $0.006$ by $n=6$, supporting the claim that $\sum_{n=1}^{100} \frac{x_n}{x_{n+1}} < 1$ without computing all terms.

The integer part is therefore rigorously justified: subtracting a sum less than $1$ from $100$ yields a value strictly greater than $99$ and strictly less than $100$, giving the integer part $99$.