Romanian Mathematical Olympiad

Let $k$ be a nonzero natural number such that $1 \le k < 2x_n$ for some natural number $n \ge 1$. We will prove by induction that we can write $k = \sum_{i=1}^{n} \varepsilon_i x_i$ with $\varepsilon_i \in \{0, 1\}$ for $i = 1, \dots, n$. Since the sequence $(x_n)_{n \ge 1}$ is unbounded, we can cover all positive integers using this construction.

The statement is clearly true for $n = 1$. Assume it is true for $n = N$. We will now show that for any $1 \le k < 2x_{N+1}$, we can write $k = \sum_{i=1}^{N+1} \alpha_i x_i$ with $\alpha_i \in \{0, 1\}$, $i \in \{1, \dots, N+1\}$.

If $x_N = x_{N+1}$, then by the induction hypothesis, $k = \sum_{i=1}^{N} \varepsilon_i x_i$ and we can take $\alpha_i = \varepsilon_i$ for $i \in \{1, \dots, N\}$ and $\alpha_{N+1} = 0$.

If $x_N < x_{N+1}$, then it is sufficient to consider values of $k$ for which $2x_N \le k < 2x_{N+1}$, since the case $k < 2x_N$ is already covered by the induction hypothesis. In this case, we have $k - x_{N+1} \ge 2x_N - x_{N+1} \ge 0$ by the given condition. We distinguish two cases:

Case 1. If $k - x_{N+1} = 0$, the statement is clearly true.

Case 2. If $k - x_{N+1} > 0$, we use again the hypothesis and observe that
$$0 < k - x_{N+1} < 2x_{N+1} - x_{N+1} \le 2x_N.$$
By the induction hypothesis, we can write $k - x_{N+1} = \sum_{i=1}^{N} \varepsilon_i x_i$ with $\varepsilon_i \in \{0, 1\}$, $i \in \{1, \dots, N\}$. Adding $x_{N+1}$ to both sides and setting $\alpha_i = \varepsilon_i$ for $i \in \{1, \dots, N\}$ and $\alpha_{N+1} = 1$, the induction step is complete.