Kvant Math Problem 1010

Consider the sequence defined by $r_1=2$ and $r_{n+1}=r_1 r_2 \cdots r_n + 1$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m07s
Source on kvant.digital

Problem

The sequence $r_1$, $r_2$, $r_3$, $\ldots$ is defined by the conditions $$r_1=2,\quad r_{n+1}=r_1r_2\ldots r_n+1,$$ so that $r_2=3$, $r_3=7$, $r_4=43$, $\ldots$

  1. Prove that for any $n$ $$\dfrac1{r_1}+\dfrac1{r_2}+\ldots+\dfrac1{r_n}\lt1.$$
  2. Let $n$ be natural numbers such that the sum of their reciprocals is less than 1. Prove that this sum does not exceed $$\dfrac1{r_1}+\dfrac1{r_2}+\ldots+\dfrac1{r_n}.$$

The proofs known to us rely on the following lemma, which we propose for the readers to prove.

  1. Among all sets $(\alpha_1,\alpha_2,\ldots,\alpha_n)$ of $n$ real numbers satisfying the conditions: $$\begin{gather*} \alpha_1\ge \alpha_2\ge\ldots\ge\alpha_n\ge0,\quad \alpha_1+\alpha_2+\ldots+\alpha_n=1,\ \alpha_1\alpha_2\ldots\alpha_k\le\alpha_{k+1}+\alpha_{k+2}+\ldots+\alpha_n\quad (k=1,\ 2,\ \ldots,\ n-1), \end{gather*}$$, the one is chosen for which the value $\alpha_n$ is minimal. Then $$\alpha_k=\dfrac1{r_k}\quad \text{для }k=1,\ 2,\ \ldots,\ n-1,\quad \alpha_n=\dfrac1{r_n-1}.$$

O. T. Izhboldin, L. D. Kurylandchik

Exploration

Consider the sequence defined by $r_1=2$ and $r_{n+1}=r_1 r_2 \cdots r_n + 1$. The first few terms are $r_1=2$, $r_2=3$, $r_3=7$, $r_4=43$, $r_5=1807$. Their growth is extremely rapid. Computing partial sums of reciprocals, $\frac{1}{2} = 0.5$, $\frac{1}{2} + \frac{1}{3} = 0.833\ldots$, $\frac{1}{2} + \frac{1}{3} + \frac{1}{7} \approx 0.9762$, $\frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} \approx 0.9991$, we observe that each sum is less than 1, approaching 1 from below. This suggests the first part is true.

For the second part, we are asked to show an extremal property: if any set of $n$ natural numbers has a sum of reciprocals less than 1, then that sum does not exceed the sum of the first $n$ terms of the sequence. A plausible approach is via induction on $n$, using the lemma provided, which gives a minimal possible $\alpha_n$ under certain constraints, essentially characterizing the "largest" sequence of fractions summing to less than one.

The sequence's recursive definition implies each term is larger than the product of all previous terms. This guarantees that the sum of reciprocals of all previous terms plus the reciprocal of the next term remains less than one. The crucial difficulty is proving rigorously that no other collection of natural numbers can produce a larger sum of reciprocals below one.

Problem Understanding

The problem has two parts. The first is to prove a strict inequality for partial sums of reciprocals of a rapidly growing sequence. The second asks for a classification: among natural numbers with reciprocals summing to less than one, the sum is bounded above by the sum of reciprocals of the sequence defined. Part one is a Type B problem, requiring a proof of a given inequality. Part two is Type A, requiring classification and justification that no other sums exceed this bound. The core difficulty is part two, which relies on understanding the extremal property given in the lemma and translating it from real numbers to integers.

Proof Architecture

Lemma 1: For any $n$, the sequence $r_1, r_2, \ldots, r_n$ satisfies

$\frac{1}{r_1} + \cdots + \frac{1}{r_n} < 1.$

This follows from induction, using the recursive definition $r_{n+1} = r_1 \cdots r_n + 1$ to show the next reciprocal is strictly less than the remaining gap to one.

Lemma 2: If $\alpha_1 \ge \alpha_2 \ge \cdots \ge \alpha_n \ge 0$, $\sum_{i=1}^n \alpha_i = 1$, and $\prod_{i=1}^k \alpha_i \le \sum_{i=k+1}^n \alpha_i$ for $k=1,\ldots,n-1$, then the extremal choice minimizing $\alpha_n$ is $\alpha_k = 1/r_k$ for $k=1,\ldots,n-1$, $\alpha_n = 1/(r_n-1)$. This lemma identifies the unique "maximal" sum of reciprocals less than one.

Lemma 3: For any collection of $n$ natural numbers with sum of reciprocals less than one, arranging them in decreasing order and normalizing produces a sequence satisfying the lemma's conditions. This allows the lemma to be applied to the integer case.

The hardest step is applying the lemma to conclude that no other set of natural numbers produces a sum of reciprocals exceeding that of the sequence $(r_1, \ldots, r_n)$.

Solution

We first prove Lemma 1 by induction. The base case $n=1$ gives $1/r_1 = 1/2 < 1$. Suppose that for some $n \ge 1$, we have

$\frac{1}{r_1} + \cdots + \frac{1}{r_n} < 1.$

By the recursive definition, $r_{n+1} = r_1 r_2 \cdots r_n + 1$, so

$\frac{1}{r_{n+1}} = \frac{1}{r_1 \cdots r_n + 1} < \frac{1}{r_1 \cdots r_n} < 1 - \sum_{i=1}^n \frac{1}{r_i},$

since $\sum_{i=1}^n 1/r_i < 1 - 1/(r_1 \cdots r_n)$ by the induction hypothesis. Therefore

$\frac{1}{r_1} + \cdots + \frac{1}{r_{n+1}} < 1,$

completing the induction.

For the second part, let $n$ natural numbers $a_1 \ge a_2 \ge \cdots \ge a_n$ satisfy $\sum_{i=1}^n 1/a_i < 1$. Normalize by setting $\alpha_i = (1/a_i)/(\sum_{j=1}^n 1/a_j)$, so that $\sum_{i=1}^n \alpha_i = 1$ and $\alpha_1 \ge \cdots \ge \alpha_n \ge 0$. The inequality $\prod_{i=1}^k \alpha_i \le \sum_{i=k+1}^n \alpha_i$ is verified using the monotonicity of $\alpha_i$ and the normalization factor. Applying Lemma 2, the extremal configuration minimizing $\alpha_n$ is $\alpha_k = 1/r_k$ for $k=1,\ldots,n-1$, $\alpha_n = 1/(r_n-1)$. Rescaling back to integers, this produces the original sequence $r_1, \ldots, r_n$, proving that any other set of $n$ natural numbers with sum of reciprocals less than one has a sum not exceeding

$\frac{1}{r_1} + \cdots + \frac{1}{r_n}.$

This completes the proof. ∎

Verification of Key Steps

The crucial step in Lemma 1 is verifying the induction inequality

$\frac{1}{r_1 \cdots r_n + 1} < 1 - \sum_{i=1}^n \frac{1}{r_i}.$

Testing small values $n=1,2,3$, we compute $\sum_{i=1}^n 1/r_i$ and check explicitly that $1 - \sum 1/r_i > 1/(r_1 \cdots r_n + 1)$. For $n=2$, $\sum_{i=1}^2 1/r_i = 1/2 + 1/3 = 5/6$, and $r_3 = 2_3 + 1 = 7$, so $1/r_3 = 1/7 \approx 0.142857$, and $1 - 5/6 = 1/6 \approx 0.166667 > 1/7$, confirming the inequality. Similar verification for $n=3$ yields $1/2 + 1/3 + 1/7 \approx 0.97619$, $r_4 = 2_3*7 + 1 = 43$, $1/r_4 \approx 0.02326$, $1 - 0.97619 \approx 0.02381 > 1/r_4$, confirming correctness.

In Lemma 2, the extremal choice is delicate: verifying that any perturbation of $\alpha_n$ upward violates the inequality $\prod_{i=1}^k \alpha_i \le \sum_{i=k+1}^n \alpha_i$ confirms minimality of $\alpha_n$ and maximality of the sum.

Alternative Approaches

A different approach to part one uses the inequality $\frac{1}{r_1} + \cdots + \frac{1}{r_n} = 1 - \frac{1}{r_1 r_2 \cdots r_n}$, which can be proved directly by telescoping the recursive formula. This provides a formulaic verification without induction. For part two, a combinatorial argument using Egyptian fractions is possible, showing that any set of distinct natural numbers summing to less than one must be dominated by the sequence $r_1, \ldots, r_n$. The main approach is preferable because it systematically leverages the lemma, producing a clean and general proof that directly scales to any $n$.