Aquí es un formalismo algebraico que parece acabar con el problema. Deje ${\mathbb Z}[x]$ ser el anillo de enteros de polinomios en $x$, y deje ${\mathbb Z}[x]^{\mathbb N}$ denotar el anillo de funciones $f: {\mathbb N} \to {\mathbb Z}[x]$ que tomar números naturales $n \in {\mathbb N} = \{0,1,2,\dots\}$ a los polinomios. En este anillo tenemos un cambio homomorphism $T: {\mathbb Z}[x]^{\mathbb N} \to {\mathbb Z}[x]^{\mathbb N}$ definido por $Tf(n) := f(n-1)$ (con el convenio que $f(n)=0$ negativos $n$). Dada una señal patrón de $\epsilon \in \{-1,+1\}^{\mathbb N} \subset {\mathbb Z}[x]^{\mathbb N}$, la solución de la recurrencia
$$ a(0) = 1$$
$$ a(n) = x a(n-1) + \epsilon(n) a(n-2) \hbox{ for } n \geq 1$$
(con la convención de las $a(n)=0$ negativos $n$) es equivalente a la localización de un elemento $a \in {\mathbb Z}[x]^{\mathbb N}$ obedeciendo a la ecuación
$$ (1 - x T - \epsilon T^2) a = \delta$$
donde $\delta \in {\mathbb Z}[x]^{\mathbb N}$ es la delta de Kronecker, que se define mediante el establecimiento $\delta(0)=1$ e $\delta(n) = 0$ para $n > 0$. Esto tiene una solución única que nos puede escribir como $a = (1 - xT - \epsilon T^2)^{-1} \delta$, donde el inverso se expandió formal de la serie de Neumann.
Presentamos el ${\mathbb Z}[x]$-lineal de operadores de $A, B_\epsilon: {\mathbb Z}[x]^{\mathbb N} \to {\mathbb Z}[x]^{\mathbb N}$ por $A := xT$ e $B_\epsilon := \epsilon T^2$, con lo que estamos tratando de encontrar los patrones de signos de $\epsilon$ tal que $(1 - A - B_\epsilon)^{-1} \delta$ toma los valores de los polinomios con coeficientes en $\{-1,0,+1\}$.
Llamar a un signo de patrón $\epsilon \in \{-1,+1\}^N$ buena si obedece a las siguientes propiedades:
- $\epsilon(2n+2)=-\epsilon(2n+3)$ para todos los $n$.
- $\epsilon(2^m(2n+3)) = - \epsilon(2^m(2n+1))$ para todos los $n$ y todos los $m \geq 1$.
Uno puede hacer una buena señal de que el patrón de la fórmula $\epsilon(2^m(2n+1)) = \sigma_m (-1)^n$ para todos los $m \geq 1$ y todos los $n$ con signos arbitrarios $\sigma_m \in \{-1,+1\}$, y, a continuación, configuración de $\epsilon(2n+1) = -\epsilon(2n)$ para todos los $n$.
El punto de una buena señal de que el patrón es el siguiente: si $\epsilon$ es bueno, entonces uno tiene el anti-conmutatividad de la propiedad $(A^{2^m} B_\epsilon^{2^m} + B_\epsilon^{2^m} A^{2^m}) f = 0$ siempre $m \geq 0$ e $f \in {\mathbb Z}[x]^{2^{m+1} {\mathbb N}}$ es compatible con los múltiplos $2^{m+1} {\mathbb N}$ de % de${\mathbb N}$. De hecho, esto es equivalente a la identidad
$$ \prod_{j=1}^{2^m} \epsilon(2^{m+1} n + 2j) + \prod_{j=1}^{2^m} \epsilon(2^{m+1} n + 2^m + 2j) = 0$$
para cualquier $n$. Para $m=0$ esto es exactamente de la propiedad 1 de una buena secuencia. Para $m>0$ cancelamos fuera un factor común de $\prod_{j=2^{m-1}+1}^{2^m} \epsilon(2^{m+1}+2j)$ a la escritura de la identidad como
$$ \prod_{j=1}^{2^{m-1}} \epsilon(2^{m+1} n + 2j) + \prod_{j=1}^{2^{m-1}} \epsilon(2^{m+1} (n+1) + 2j) = 0$$
y, a continuación, observar, desde la propiedad 2 $\epsilon(2^{m+1}(n+1) + 2j) = \epsilon(2^{m+1} n + 2j)$ al $1 \leq j < 2^{m-1}$ e $\epsilon(2^{m+1}(n+1)+ 2j) = -\epsilon(2^{m+1} n + 2j)$ para $j = 2^{m-1}$.
El uso de este anticommutativity y la inducción obtenemos el tipo Frobenius de la identidad
$$ (A + B_\varepsilon)^{2^m} f = (A^{2^m} + B_\varepsilon^{2^m}) f$$
siempre que $m \geq 0$ e $f \in {\mathbb Z}[x]^{2^m {\mathbb N}}$ (tenga en cuenta que $A^{2^m}$ e $B_\varepsilon^{2^m}$ mapa de ${\mathbb Z}[x]^{2^{m+1} {\mathbb N}}$ a ${\mathbb Z}[x]^{2^{m} {\mathbb N}}$). Un similares de inducción, a continuación, conduce a la identidad
$$ (1-A-B_\epsilon) \prod_{i=0}^{m-1} (1 + A^{2^i} + B_\epsilon^{2^i}) f = (1 - A^{2^m} - B_\epsilon^{2^m}) f$$
siempre que $m \geq 0$ e $f \in \mathbb{Z}[x]^{2^m {\mathbb N}}$, donde el producto se ordena de izquierda a derecha, así
$$ \prod_{i=0}^{m-1} (1 + A^{2^i} + B_\epsilon^{2^i}) = (1 + A + B_\epsilon) (1 + A^2 + B_\epsilon^2) \dots (1 + A^{2^{m-1}} + B_\epsilon^{2^{m-1}}).$$
La especialidad de a $f=\delta$, aplicando $(1-A-B_\varepsilon)^{-1}$ y, a continuación, envío de $m$ hasta el infinito obtenemos la fórmula
$$ (1-A-B_\epsilon)^{-1} \delta = \prod_{i=0}^{\infty} (1 + A^{2^i} + B_\epsilon^{2^i}) \delta$$
(donde el producto converge pointwise). Uno puede comprobar que cada término en este pointwise producto les da otro monomio encuentra en un punto diferente con coeficiente de $\pm 1$, por lo que este hecho da una secuencia $a(n) \in {\mathbb Z}[x]$ para $n \in {\mathbb N}$ con el de las propiedades, con la forma explícita
$$ a = (1 + A + B_\epsilon) (1 + A^2 + B_\epsilon^2) (1 + A^4 + B_\epsilon^4) \dots \delta.$$
Para dar sentido de esta fórmula, si escribimos $a$ como una secuencia $a(0),a(1),a(2),\dots$, luego
$$ \delta = 1, 0, 0, \dots$$
$$ (1+A+B_\epsilon) \delta = 1, x, \epsilon(2), 0, \dots$$
$$ (1+A+B_\epsilon) (1+A^2+B_\epsilon^2) \delta = 1, x, \epsilon(2) + x^2, x^3, \epsilon(2)\epsilon(4) + \epsilon(2) x^2, \epsilon(2)\epsilon(4) x, \epsilon(2)\epsilon(4)\epsilon(6),0, \dots$$
y uno converge a
$$ a(0) = 1$$
$$ a(1) = x$$
$$ a(2) = \epsilon(2) + x^2$$
$$ a(3) = x^3$$
$$ a(4) = \epsilon(2) \epsilon(4) + \epsilon(2) x^2 + x^4 $$
$$ a(5) = \epsilon(2) \epsilon(4) x + x^5 $$
$$ a(6) = \epsilon(2)\epsilon(4) \epsilon(6) + \epsilon(6)x^4 + x^6 $$
$$ \dots$$
que es un reparameterisation de las soluciones anteriores.
Uno puede mostrar que estas son en realidad las únicas secuencias de polinomios $a$ que mantienen sus coeficientes en $-1,+1$, pero la prueba de esta singularidad es un poco tedioso de inducción y esta respuesta ya es bastante largo, así que voy a dejar como un ejercicio.
