, 2022

For all $k$, since there are only finitely many possible values for $a_n$ ($n \ge k$) to take, there exists $n_{max} \ge k$ so that $a_{n_{max}} \ge a_n$ for all $n \ge k$. Now, we can prove by induction that $a_m \ge (1 - 2^{-n_{max}} - 2^{-n_{max}-1} - \dots - 2^{-(m+1)})a_{n_{max}}$ for all $k \le m \le n_{max}$. This is trivial when $m = n_{max}$. Now suppose that it holds for $m + 1$, then we have
$$a_{m+1} \le a_m + 2^{-(m+1)} a_{2(m+1)} \le a_m + 2^{-(m+1)} a_{n_{max}}$$
since $2(m+1) > k$. By the induction hypothesis, we get that
$$a_m \ge a_{m+1} - 2^{-(m+1)} a_{n_{max}} \ge (1 - 2^{-n_{max}} - \dots - 2^{-(m+1)}) a_{n_{max}},$$
as desired. In particular, we can set $m = k$ to get that
$$a_k \ge (1 - 2^{-n_{max}} - \dots - 2^{(k+1)}) a_{n_{max}} \ge 1 - \sum_{i=k+1}^{\infty} 2^{-i} = 1 - 2^{-k}$$
where the inequality follows from the fact that $a_{n_{max}} \ge a_N \ge 1$ and the fact that we are extending the finite sum to the infinite sum. $\square$

We first reduce the problem to the case where $a_n = a_{n-1} + 2^{-n}a_{2n}$ holds for all $n \le N$. We will show this by showing that we can decrease $a_1, \dots, a_{N-1}$ to achieve this. Let $k \in [N]$ be the largest such that $a_k < a_{k-1} + 2^{-k}a_{2k}$. Let $M$ be the difference between the two sides. Let $a'_k = a_k, a'_{k+1} = a_{k+1}, \dots$ and for each $i = 1, \dots, k-1$ we
let $a'_i = a_i - (1 - 2^{-i-1} - \cdots - 2^{-k+1})M < a_i$ (in particular, $a'_{k-1} = a_{k-1} - M$). Then
it is clear that $a'_i \ge a_i - M$, and so
$$a'_{n-1} = a_{n-1} - a_n + a'_n + 2^{-n}M \ge a'_n + 2^{-n}(M - a_{2n}) \ge a'_n - 2^{-n}a'_{2n}.$$
for all $n = 1, \dots, k-1$. It is also clear that $a'_{k-1} = a'_k - 2^{-k}a'_{2k}$ by definition. Therefore $a'_1, a'_2, \dots$ is a sequence not greater than $a_1, a_2, \dots$ term-wise that satisfies the inequality and have one additional equality holding. We can therefore iteratively decrease the sequence term-wise so that all the equalities hold for $n < N$. Then we can simply prove by induction that $1 - 2^{-k} < a_k \le 1$. In particular, $a_k > 1 - 2^{-k}$ holds for the original sequence. $\square$