75th 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{\epsilon }_i{x}_i$ with ${\epsilon }_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{\epsilon }_i{x}_i$ and we can take ${\alpha }_i={\epsilon }_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{\epsilon }_i{x}_i$ with ${\epsilon }_i\in \{0,1\}$, $i\in \{1,\dots ,N\}$. Adding $x_{N+1}$ to both sides and setting ${\alpha }_i={\epsilon }_i$ for $i\in \{1,\dots ,N\}$ and ${\alpha }_{N+1}=1$, the induction step is complete.