While Terry Tao provided a formal answer here, I kept thinking about the problem for some time, hoping to find a more simple and insightful explanation for what's going on. And, hopefully, I managed to do so!

### Visualization with Sierpinski triangle

Let's use the formulation in which we consider the sequence $A_0, A_1, A_2, \dots$, such that

$$\begin{gather}
A_{0} = 1,~ A_1 = x, \\
A_k = x A_{k-1} + b_k A_{k-2}.
\end{gather}$$

In other words, $b_k$ is either $1$ or $-1$ depending on the sign used. Let $a_{ij} = [x^j]A_i$, then
$$
a_{ij} = a_{(i-1)(j-1)}+b_i a_{(i-2)j}.
$$

Note that when both $a_{(i-1)(j-1)}$ and $a_{(i-2)j}$ are non-zero, $b_i$ must be such that $a_{ij}=0$. From this follows, that when fully expanded, every $a_{ij}$ is either $0$, or equates to a product of all elements of some subset of the sequence $b_1, b_2, \dots, b_n$. Keeping this in mind, we can, assuming $b_1, b_2, \dots$ to be infinite, organize all values of $a_{ij}$ in a triangular shaped table, in which above the cell corresponding to $a_{ij}$ are the cells corresponding to $a_{(i-1)(j-1)}$ to the left and $a_{(i-2)j}$ to the right:

Then, a special color designation is used for each cell. If the corresponding coefficient must be non-zero, the cell is colored grey.

Otherwise, the color of the cell depends on the structure of its parents. Generally, each zero cell has $t$ non-zero parents in both directions (left and right). For example, the cell $a_{62}$ has non-zero parents $a_{40}$ and $a_{51}$ to the left, and non-zero parents $a_{42}$ and $a_{22}$ to the right. So, on the picture above:

- White cells have $0$ such parents (i. e. they are directly below cells that also have value $0$),
- $\color{red}{\textrm{Red}}$ cells have $1$ such parent on each side,
- $\color{orange}{\textrm{Orange}}$ cells have $2$ such parents on each side,
- $\color{goldenrod}{\textrm{Yellow}}$ cells have $4$ such parents on each side,
- $\color{green}{\textrm{Green}}$ cells have $8$ such parents on each side.

### Tedious induction sketch

Note that when we descend from a grey node to the right into another grey node, it copies the value from that node, and if we descend to the left into the node $a_{ij}$, it gets multiplied by $b_i$. On the other hand, of a non-grey node has $t$ grey parents, they will also reach a common parent in $t$ more steps. In other words, each non-grey node $a_{ij}$ with $t > 0$ grey parents defines an equation of form

$$
b_{i-t-2(t-1)} b_{i-t-2(t-2)} b_{i-t-2(t-3)} \dots b_{i-t} + b_i b_{i-2} b_{i-4} \dots b_{i - 2(t-1)} = 0.
$$

The first summand here is obtained by multiplying $t$ pieces of $b_k$ from the left path to the common parent, and the second summand is obtained by multiplying $t$ pieces of $b_k$ from the right path to the common parent. For example, the cell $a_{97}$ with $t=1$ defines the equation $b_8 + b_9 = 0$, and the cell $a_{62}$ defines the equation $b_2 b_4 + b_4 b_6 = 0$. These equations are not in a very convenient form (yet), but adhering to them is necessary and sufficient for $a_{ij}$ to maintain the property that each $a_{ij}$ is either $-1$, $0$ or $1$.

Note that, very conveniently, the equations defined by $a_{ij}$ do not depend on $j$ at all!

Now, these equations may be simplified by induction. First of all, we should notice that red equations only occur in odd $i$, so assuming $i = 2k+1$ we may rewrite them as

$$
b_{2k+1} + b_{2k} = 0
$$

for every $k \geq 1$. What about orange equations? First such equation occurs in $a_{62}$ with $i=6$, where it looks like $b_2 b_4 + b_4 b_6 = 0$ and repeats with steps of $4$, where it writes as

$$
b_{4k-2} b_{4k} + b_{4k} b_{4k+2} = 0 \iff b_{2(2k-1)} + b_{2(2k+1)} = 0.
$$

First yellow equation occurs with $i=12$ and repeats with steps of $8$, and rewrites as

$$
b_{8k-6} b_{8k-4} b_{8k-2} b_{8k} + b_{8k-2} b_{8k} b_{8k+2} b_{8k+4} = 0.
$$

On the other hand we know that $b_{2(4k-3)}+b_{2(4k-1)}=0$ and $b_{2(4k-1)} + b_{2(4k+1)}=0$, which rewrites

$$
b_{8k-4} b_{8k} + b_{8k} b_{8k+4} = 0 \iff b_{4(2k-1)} + b_{4(2k+1)} = 0.
$$

So, the equation with $t=2^{n-1}$ first occurs in $i=2^n+2^{n-1}$ and repeats every $2^n$ steps, hence

$$
b_{2^n k - 2(t-1)} \dots b_{2^n k} + b_{2^n k - (t - 2) } \dots b_{2^n k + (t - 2)} b_{2^n k + t} = 0.
$$

From this, we may by induction prove that such equation simplifies as

$$
b_{2^{n-1}(2k-1)} + b_{2^{n-1} (2k+1)} = 0.
$$

#### Example with $t=8$

To do this, we should note that we may meticulously cancel out every odd multiplier until only two multipliers are left in each summand, one of them being $b_{2^{n} k}$. For example, with $t=8$, we start with

$$
b_{16k - 14} b_{16k-12}\dots b_{16k-2} b_{16k} + b_{16k-6} b_{16k-4} \dots b_{16k+6} b_{16k+8} = 0.
$$

On the first step, we cancel out the following pairs:

- In the first summand, $b_{2(8k-7)}$ and $b_{2(8k-5)}$, then $b_{2(8k-3)}$ and $b_{2(8k-1)}$,
- In the second summand, $b_{2(8k-3)}$ and $b_{2(8k-1)}$, then $b_{2(8k+1)}$ and $b_{2(8k+3)}$,

after which we're left with the equation

$$
b_{16k-12} b_{16k-8} b_{16k - 4} b_{16k} + b_{16k-4} b_{16k} b_{16k+4} b_{16k+8} = 0,
$$

and we again cancel out:

- In the first summand, $b_{4(4k-3)}$ and $b_{4(4k-1)}$,
- In the second summand, $b_{4(4k-1)}$ and $b_{4(4k+1)}$,

after which we are left with

$$
b_{16k - 8} b_{16k} + b_{16k} b_{16k+8} = 0 \iff b_{8(2k-1)} + b_{8(2k+1)} = 0.
$$

Formal proof for all $n, k \geq 1$ is a bit tedious, but should follow from the procedure above.

### Final criterion

Summarizing the above, we reduced everything to a set of equations:

$$
\begin{cases}
b_{2k+1} + b_{2k} = 0, & \forall k \geq 1, \\
b_{2^n(2k-1)} + b_{2^n(2k+1)} = 0, & \forall n, k \geq 1,
\end{cases}
$$

which is necessary and sufficient for the specified condition to hold.

Note that the second equation is equivalent to

$$\begin{gather}
b_{2^n(2k+1)} = (-1)^k b_{2^n}, & \forall n, k \geq 1,
\end{gather}$$

meaning that the subsequence $b_2, b_4, b_8, b_{16}, \dots$ uniquely defines the whole sequence $b_2, b_3, b_4, \dots$.