Problem 1390

We show that $n_{k+1} \le 2n_k + 2$ for all indices $k$. Since $n_4 = 6 = 2^{4-1} - 2$, the conclusion follows inductively. (None of the first three exponents, $n_1 = 1$, $n_2 = 4$, $n_3 = 5$, satisfies the inequality in the statement.)

Write $\alpha = (\sqrt{5}-1)/2$, $m = 2^{n_k} \sum_{j=1}^k 2^{-n_j}$ and $\beta = \alpha - m \cdot 2^{-n_k}$, and notice that $m \cdot 2^{-n_k} \le \sum_{j=1}^{n_k} 2^{-j} = 1 - 2^{-n_k} < 1$ and $\beta \le \sum_{j \ge n_{k+1}} 2^{-j} \le 2^{1-n_{k+1}}$. Since $\alpha$ is irrational, so is $\beta$, and therefore $0 < \beta < 2^{1-n_{k+1}}$.

Next, write $1 = \alpha + \alpha^2 = m \cdot 2^{-n_k} + m^2 \cdot 2^{-2n_k} + \beta (1 + 2m \cdot 2^{-n_k} + \beta)$, to infer that $2^{2n_k} \beta (1 + 2m \cdot 2^{-n_k} + \beta)$ is an integer; it is clearly positive, so it is at least 1.

By the preceding, $2^{2n_k} \beta (1 + 2m \cdot 2^{-n_k} + \beta) < 2^{2n_k+1-n_{k+1}} (1 + 2 + 2^{1-n_{k+1}})$, so
$$2^{2n_k+1-n_{k+1}} (3 + 2^{1-n_{k+1}}) > 1.$$
Finally, since $n_{k+1} \ge n_2 = 4$, it follows that $3 + 2^{1-n_{k+1}} \le 3 + 1/8 < 2^2$, so $n_{k+1} < 2n_k + 3$; that is, $n_{k+1} \le 2n_k + 2$.