, 2023

Solution: We start with a lemma.
Lemma. For any $n$, $x \in A_n$ implies $\frac{1}{x} \in A_n$.
Proof. Induction. Case $n = 1$ is clear. Now, if $x = a_i + a_{n-i} \in A_i + A_{n-i} \subset A_n$, then $\frac{1}{a_i} \in A_i$ and $\frac{1}{a_{n-i}} \in A_{n-i}$, and thus
$$\frac{1}{x} \in \frac{1}{\frac{1}{A_i} + \frac{1}{A_{n-i}}} \subset A_n.$$
Similarly if $x = (\frac{1}{a_i} + \frac{1}{a_{n-i}})^{-1}$, then
$$\frac{1}{x} = \frac{1}{a_i} + \frac{1}{a_{n-i}} \in A_i + A_{n-i} \subset A_n. \quad \square$$
Lower bound.
We now prove that $|A_{n+1}| \ge 2|A_n|$ for all $n$, which proves the lower bound. Let $a$ denote the number of elements in $A_n$ which are larger than or equal to $1$ and let $b$ denote the number of elements in $A_n$ which are strictly larger than $1$. Clearly $a = b$ if $1 \notin A_n$ and otherwise $a = b + 1$.

First note that $A_1 + A_n = \{1\} + A_n \subset A_{n+1}$, so $A_{n+1}$ contains at least $a$ elements which are $\ge 2$. Also note that for any $a_n \in A_n$ for which $a_n > 1$ we have
$$\frac{1}{2} < a_{n+1} := \frac{1}{\frac{1}{1} + \frac{1}{a_n}} < 1$$
and $a_{n+1} \in A_n$. Thus, $A_{n+1}$ contains at least $b$ elements in $(\frac{1}{2}, 1)$ and thus, by the lemma, at least $b$ elements in $(1, 2)$.
Therefore, $A_{n+1}$ has at least $a+b$ elements greater than $1$. By the lemma $A_{n+1}$ thus has at least $2(a+b)$ elements. If $a=b$, then $2|A_n| = 4a = 2(a+b) \le |A_{n+1}|$ and if $a=b+1$, then $2|A_n| = 2(2b+1) = 2(a+b) \le |A_{n+1}|$.

Upper bound.
We then prove the upper bound. Define $s_n := |A_n|$, let $c_n := \frac{1}{n+1} \binom{2n}{n}$ be the $n$-th Catalan number, and $b_n := 2^n c_{n-1}$. Then
$$\begin{aligned} \sum_{i=1}^{n-1} b_i b_{n-i} &= \sum_{i=1}^{n-1} 2^i \cdot c_{i-1} \cdot 2^{n-i} \cdot c_{n-2-(i-1)} \\ &= 2^n \cdot \sum_{i=0}^{n-2} c_i c_{(n-2)-i} = 2^n \cdot c_{n-1} = b_n, \end{aligned}$$
where we used the well-known recursion formula for the Catalan numbers.
We prove that $s_n < b_n$ for all $n$, which certainly is enough since $b_n = \frac{2^n}{n} \binom{2(n-1)}{n-1} < 2^n \cdot 2^{2n} = 8^n$. The proof is by induction. The cases $n \le 4$ may be checked by hand, as we have
$$s_1 = 1 < 2 = b_1, \quad s_2 = 2 < 4 = b_2, \quad s_3 = 4 < 16 = b_3, \quad \text{and} \quad s_4 = 9 < 80 = b_4.$$
We now assume $n \ge 5$.
We have the trivial bound
$$s_n \le \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} 2s_i s_{n-i}.$$

s_n \le \sum_{i=1}^{n-1} s_i s_{n-i}.
$$Use the induction hypothesis to get$$
s_n \le \sum_{i=1}^{n-1} s_i s_{n-i} < \sum_{i=1}^{n-1} b_i b_{n-i} = b_n.
For $n$ even we need more care. Note that $|A_{n/2} + A_{n/2}| \le \binom{s_{n/2}}{2} + s_{n/2}$ and
\left| \frac{1}{\frac{1}{A_{n/2}} + \frac{1}{A_{n/2}}} \right| \le \binom{s_{n/2}}{2} + s_{n/2}.
Therefore, for $n$ even we have
s_n \le \sum_{i=1}^{\frac{n}{2}-1} 2s_i s_{n-i} + s_{n/2}^2 + s_{n/2} = \sum_{i=1}^{n-1} s_i s_{n-i} + s_{n/2}.
We now note that for $n \ge 6$ we have, by the induction hypothesis, $s_3 s_{n-3} < (b_3 - 1) b_{n-3}$, and hence
\sum_{i=1}^{n-1} s_i s_{n-i} + s_{n/2} < \sum_{i=1}^{n-1} b_i b_{n-i} - b_{n-3} + b_{n/2} \le \sum_{i=1}^{n-1} b_i b_{n-i} = b_n,
$$$$
as Catalan numbers and also the $b_n$ are increasing, concluding the proof.