For each positive integer $k$, let $S_k$ be the set of real numbers that can be expressed in the form \[\frac{1}{n_1}+\frac{1}{n_2}+\dots+\frac{1}{n_k},\]where $n_1,n_2\dots,n_k$ are positive integers. Prove that $S_k$ does not contain an infinite strictly increasing sequence.
Problem
Source: 2020 Simon Marais Mathematics Competition B2
Tags: number theory
XbenX
17.11.2020 13:57
We induct.
For $k=1$, there are only finitely integers $b$ such that for fixed positive integer $a$ we have $\frac{1}{a}<\frac{1}{b}$, so an increasing sequence can't be infinite.
Assume that there isn't such a sequence in $S_{k-1}$. Now, assume there is such a sequence in $S_k$, let that sequence be $(x_i)_{i\in \mathbb{N}}$.
For each $x_i$ let $y_i\in \mathbb{N}$ be the minimum of the denominators of $k$ summands of $x_i$.
We claim that $(y_i)_{i\in \mathbb{N}}$ is bounded. If on the contrary for large $M$ there is an $i$ such that $y_{i}>M$ then
\[ x_i<\frac{1}{M}+\frac{1}{M}+\dots+\frac{1}{M}=\frac{k}{M} < x_1.\]which cannot hold.
Therefore $(y_i)$ is bounded and by infinite Pigeon-hole, it takes one value infinitely many times which implies the existence of an increasing subsequence of $S_{k-1}$ which is not true by the induction hypothesis, hence there is no infinite increasing sequence in $S_k$ which finishes the induction.
DanDumitrescu
25.01.2021 18:24
I will solve this problem with induction. k = 1. We suppose that a sequence is increasing $x_n$ then all numbers $x_n$ , $n \ge 2$ are greater than $ x_1$ but there are only a finite number in $S_1$ greater than $x_1$ so case k = 1 is solve. Now we suppose $S_{l}$ don't contain any strictly increasing sequence and I will prove for $S_{l+1}$. I suppose that $S_{l+1}$ contains a sequence $y_n$ strictly increasing. $y_1 = \frac{1}{x_1} + \frac{1}{x_2} \ldots + \frac{1}{x_{l+1}}$ and WLOG $x_1$ is maximum from $x_1, x_2, \ldots x_{l+1}$. Because $y_n > y_1, n \ge 2$. $y_n = \frac{1}{x_{1,n}} + \frac{1}{x_{2,n}} \ldots + \frac{1}{x_{l+1,n}}$. At least one from $ x_{1,n}$, $x_{2,n} \ldots x_{l+1,n}$ is less than $x_1$. We suppose WLOG that every $y_n$ has first term $x_{1,n}$ less than $x_1$. So first term from $y_n$ can take only a finite values so we can find a subsequence from $y_n$ , $s_n$ for which first term is constant. So $s_n = a + \frac{1}{s_{2,n}} \ldots + \frac{1}{s_{l+1,n}}$, so $s_n - a$ is a strictly increasing sequence , but $s_n - a$ is a term from $S_l$. $s_n - a$ is strictly increasing in $S_l$ which is a contradiction from induction.