2022 IMO Shortlist A8

For a positive integer $n$, an $n$-sequence is a sequence $\left(a_{0}, \ldots, a_{n}\right)$ of non-negative integers satisfying the following condition: if $i$ and $j$ are non-negative integers with $i+j \leq n$, then $a_{i}+a_{j} \leq n$ and $a_{a_{i}+a_{j}}=a_{i+j}$. Let $f(n)$ be the number of $n$-sequences. Prove that there exist positive real numbers $c_{1}, c_{2}$ and $\lambda$ such that $$c_{1} \lambda^{n}<f(n)<c_{2} \lambda^{n}$$ for all positive integers $n$.

对于正整数 $n$，$n$ 序列是满足以下条件的非负整数序列 $\left(a_{0}, \ldots, a_{n}\right)$：如果 $i$ 和 $j$ 是 $i+j \leq n$ 的非负整数，则 $a_{i}+a_{j} \leq n$ 且$a_{a_{i}+a_{j}}=a_{i+j}$。令 $f(n)$ 为 $n$ 序列的数量。证明对于所有正整数 $n$，存在正实数 $c_{1}、c_{2}$ 和 $\lambda$，使得 $$c_{1} \lambda^{n}<f(n)<c_{2} \lambda^{n}$$。