Consider following polynomial sequence.

$$\begin{cases}a_{-1}=0,~a_0=1, \\a_{n+1}=x \cdot a_n \pm a_{n-1}\end{cases}$$

Here $+$ or $-$ is taken in such a way that all coefficients in $a_n$ do not exceed $1$ by absolute value (i.e. $\forall k \hookrightarrow |[x^k]a_n(x)|\leq 1$). The sequence seems to be infinite, but what is the strict proof of it and what are the properties of such sequence? Maybe it has unique name?

Also it seems that if we will write $0$ each time we use $-$ and $1$ each time we use $+$ in sequence $s_i$, there will be $2^{\lfloor\log_2 n\rfloor+1}$ sequences $s_i$ which generate correct $a_i$. Here is all $16$ possible patterns of first $15$ terms of $s_i$:

001011001011010 110100110100101
001011010011010 110100101100101
001101001010110 110010110101001
001101010010110 110010101101001
010010101101001 101101010010110
010010110101001 101101001010110
010100101100101 101011010011010
010100110100101 101011001011010

Can you see any pattern in here? Note that in the same row it is the sequence and same sequence reversed.

UPD: It seems that $s_0$ does not matter (since it produces $a_1=x$ in any way) and if we consider sequence $g_i$ which generates $\{s_i\}_{i=1}^{2^{n}-2}$, its prefixes can be generated as

$$\begin{cases}g_1=\varepsilon,\\g_{n+1}=g_n + (01|10) + g_n^r\end{cases}$$

where $g_n^r$ stands for reversed $g_n$.

  • $\begingroup$ What is $x$? It seems hard to decide if $|a_n|>1$ without knowing what $x$ is. $\endgroup$ Nov 3, 2017 at 3:50
  • $\begingroup$ You got it wrong, $a_n$ is the polynomial from $x$. So $\forall k \hookrightarrow |[x^k]a_n(x)| \leq 1$. $\endgroup$ Nov 3, 2017 at 4:10

6 Answers 6


Here is an algebraic formalism that seems to finish off the problem. Let ${\mathbb Z}[x]$ be the ring of integer polynomials in $x$, and let ${\mathbb Z}[x]^{\mathbb N}$ denote the ring of functions $f: {\mathbb N} \to {\mathbb Z}[x]$ that take natural numbers $n \in {\mathbb N} = \{0,1,2,\dots\}$ to polynomials. On this ring we have a shift homomorphism $T: {\mathbb Z}[x]^{\mathbb N} \to {\mathbb Z}[x]^{\mathbb N}$ defined by $Tf(n) := f(n-1)$ (with the convention that $f(n)=0$ for negative $n$). Given a sign pattern $\epsilon \in \{-1,+1\}^{\mathbb N} \subset {\mathbb Z}[x]^{\mathbb N}$, solving the recurrence $$ a(0) = 1$$ $$ a(n) = x a(n-1) + \epsilon(n) a(n-2) \hbox{ for } n \geq 1$$ (with the convention $a(n)=0$ for negative $n$) is equivalent to locating an element $a \in {\mathbb Z}[x]^{\mathbb N}$ obeying the equation $$ (1 - x T - \epsilon T^2) a = \delta$$ where $\delta \in {\mathbb Z}[x]^{\mathbb N}$ is the Kronecker delta, defined by setting $\delta(0)=1$ and $\delta(n) = 0$ for $n > 0$. This has a unique solution that we can write as $a = (1 - xT - \epsilon T^2)^{-1} \delta$, where the inverse is expanded by formal Neumann series.

We introduce the ${\mathbb Z}[x]$-linear operators $A, B_\epsilon: {\mathbb Z}[x]^{\mathbb N} \to {\mathbb Z}[x]^{\mathbb N}$ by $A := xT$ and $B_\epsilon := \epsilon T^2$, thus we are trying to find sign patterns $\epsilon$ such that $(1 - A - B_\epsilon)^{-1} \delta$ takes values in polynomials with coefficients in $\{-1,0,+1\}$.

Call a sign pattern $\epsilon \in \{-1,+1\}^N$ good if it obeys the following properties:

  1. $\epsilon(2n+2)=-\epsilon(2n+3)$ for all $n$.
  2. $\epsilon(2^m(2n+3)) = - \epsilon(2^m(2n+1))$ for all $n$ and all $m \geq 1$.

One can make a good sign pattern by the formula $\epsilon(2^m(2n+1)) = \sigma_m (-1)^n$ for all $m \geq 1$ and all $n$ with arbitrary signs $\sigma_m \in \{-1,+1\}$, and then setting $\epsilon(2n+1) = -\epsilon(2n)$ for all $n$.

The point of a good sign pattern is the following: if $\epsilon$ is good, then one has the anti-commutativity property $(A^{2^m} B_\epsilon^{2^m} + B_\epsilon^{2^m} A^{2^m}) f = 0$ whenever $m \geq 0$ and $f \in {\mathbb Z}[x]^{2^{m+1} {\mathbb N}}$ is supported on the multiples $2^{m+1} {\mathbb N}$ of ${\mathbb N}$. Indeed, this is equivalent to the identity $$ \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$$ for any $n$. For $m=0$ this is exactly property 1 of a good sequence. For $m>0$ we cancel off a common factor of $\prod_{j=2^{m-1}+1}^{2^m} \epsilon(2^{m+1}+2j)$ to write the identity as $$ \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$$ and then observe from property 2 that $\epsilon(2^{m+1}(n+1) + 2j) = \epsilon(2^{m+1} n + 2j)$ when $1 \leq j < 2^{m-1}$ and $\epsilon(2^{m+1}(n+1)+ 2j) = -\epsilon(2^{m+1} n + 2j)$ for $j = 2^{m-1}$.

Using this anticommutativity and induction we obtain the Frobenius type identity $$ (A + B_\varepsilon)^{2^m} f = (A^{2^m} + B_\varepsilon^{2^m}) f$$ whenever $m \geq 0$ and $f \in {\mathbb Z}[x]^{2^m {\mathbb N}}$ (note that $A^{2^m}$ and $B_\varepsilon^{2^m}$ map ${\mathbb Z}[x]^{2^{m+1} {\mathbb N}}$ to ${\mathbb Z}[x]^{2^{m} {\mathbb N}}$). A similar induction then leads to the identity $$ (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$$ whenever $m \geq 0$ and $f \in \mathbb{Z}[x]^{2^m {\mathbb N}}$, where the product is ordered from left to right, thus $$ \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}}).$$ Specialising to $f=\delta$, applying $(1-A-B_\varepsilon)^{-1}$ and then sending $m$ to infinity we obtain the formula $$ (1-A-B_\epsilon)^{-1} \delta = \prod_{i=0}^{\infty} (1 + A^{2^i} + B_\epsilon^{2^i}) \delta$$ (where the product converges pointwise). One can check that every term in this pointwise product gives a different monomial located at a different point with coefficient $\pm 1$, so this indeed gives a sequence $a(n) \in {\mathbb Z}[x]$ for $n \in {\mathbb N}$ with the stated properties, with the explicit form $$ a = (1 + A + B_\epsilon) (1 + A^2 + B_\epsilon^2) (1 + A^4 + B_\epsilon^4) \dots \delta.$$

To give some sense of this formula, if we write $a$ as a sequence $a(0),a(1),a(2),\dots$, then $$ \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$$ and one converges to $$ 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$$ which is a reparameterisation of the previous solutions.

One can show that these are in fact the only sequences of polynomials $a$ that maintain their coefficients in $-1,+1$, but the proof of this uniqueness is a somewhat tedious induction and this answer is already quite long, so I'll leave it as an exercise.


No proofs, just experimental facts (hence cw):

Let $a_{n+1}=xa_n+\varepsilon_{n+1}a_{n-1}$, with $\varepsilon_k=\pm1$; then $\varepsilon_{2^k}$ might be arbitrary, while all others are uniquely determined by them. For the first few cases we have $$ \begin{aligned} \varepsilon_{3}&=-\varepsilon_{2}\\ \varepsilon_{5}&=-\varepsilon_{4}\\ \varepsilon_{6}&=-\varepsilon_{2}\\ \varepsilon_{7}&=\varepsilon_{2}\\ \varepsilon_{9}&=-\varepsilon_{8}\\ \varepsilon_{10}&=\varepsilon_{2}\\ \varepsilon_{11}&=-\varepsilon_{2}\\ \varepsilon_{12}&=-\varepsilon_{4}\\ \varepsilon_{13}&=\varepsilon_{4}\\ \varepsilon_{14}&=-\varepsilon_{2}\\ \varepsilon_{15}&=\varepsilon_{2}\\ \varepsilon_{17}&=-\varepsilon_{16}\\ \varepsilon_{18}&=\varepsilon_{2}\\ \varepsilon_{19}&=-\varepsilon_{2}\\ \varepsilon_{20}&=\varepsilon_{4}\\ \varepsilon_{21}&=-\varepsilon_{4}, \end{aligned} $$ the polynomials being, respectively, $$ \begin{aligned} a_1&=x \\ a_2&=x^2+\varepsilon_{2} \\ a_3&=x^3 \\ a_4&=x^4+\varepsilon_{4}x^2 +\varepsilon_{2} \varepsilon_{4} \\ a_5&=x^5+\varepsilon_{2} \varepsilon_{4}x \\ a_6&=x^6-\varepsilon_{2}x^4 -\varepsilon_{4} \\ a_7&=x^7 \\ a_8&=x^8+\varepsilon_{8}x^6 -\varepsilon_{2} \varepsilon_{8}x^4 -\varepsilon_{4} \varepsilon_{8} \\ a_9&=x^9-\varepsilon_{2} \varepsilon_{8}x^5 -\varepsilon_{4} \varepsilon_{8}x \\ a_{10}&=x^{10}+\varepsilon_{2}x^8 -\varepsilon_{8}x^4 - \varepsilon_{4} \varepsilon_{8}x^2-\varepsilon_{2}\varepsilon_{4} \varepsilon_{8} \\ a_{11}&=x^{11}-\varepsilon_{4} \varepsilon_{8}x^3 \\ a_{12}&=x^{12}-\varepsilon_{4}x^{10} -\varepsilon_{2} \varepsilon_{4}x^8 + \varepsilon_{8}x^2+\varepsilon_{2}\varepsilon_{8} \\ a_{13}&=x^{13}-\varepsilon_{2} \varepsilon_{4}x^9 +\varepsilon_{2} \varepsilon_{8}x \\ a_{14}&=x^{14}-\varepsilon_{2}x^{12} +\varepsilon_{4}x^8 - \varepsilon_{8} \\ a_{15}&=x^{15} \\ a_{16}&=x^{16}+\varepsilon_{16}x^{14} -\varepsilon_{2} \varepsilon_{16}x^{12} +\varepsilon_{4} \varepsilon_{16}x^8 -\varepsilon_{8} \varepsilon_{16} \\ a_{17}&=x^{17}-\varepsilon_{2} \varepsilon_{16}x^{13} + \varepsilon_{4} \varepsilon_{16}x^9 - \varepsilon_{8} \varepsilon_{16}x \\ a_{18}&=x^{18}+\varepsilon_{2}x^{16} -\varepsilon_{16}x^{12} +\varepsilon _{4} \varepsilon_{16}x^{10} +\varepsilon_{2}\varepsilon_{4} \varepsilon_{16}x^8 - \varepsilon_{8} \varepsilon_{16}x^2 -\varepsilon_{2} \varepsilon_{8} \varepsilon_{16} \\ a_{19}&=x^{19}+\varepsilon_{4} \varepsilon_{16}x^{11} - \varepsilon_{8} \varepsilon_{16}x^3 \\ a_{20}&=x^{20}+\varepsilon_{4}x^{18} +\varepsilon_{2} \varepsilon_{4}x^{16} +\varepsilon_{16}x^{10} +\varepsilon_{2}\varepsilon_{16}x^8 -\varepsilon_{8} \varepsilon_{16}x^4 -\varepsilon_{4}\varepsilon_{8} \varepsilon _{16}x^2 -\varepsilon_{2}\varepsilon_{4}\varepsilon_{8} \varepsilon_{16} \\ a_{21}&=x^{21}+\varepsilon_{2} \varepsilon_{4}x^{17} +\varepsilon_{2} \varepsilon_{16}x^9 - \varepsilon_{8} \varepsilon_{16}x^5- \varepsilon_{2} \varepsilon_{4} \varepsilon_{8} \varepsilon_{16}x \end{aligned} $$

  • 2
    $\begingroup$ It's also interesting that $a_{2^k-1}=x^{2^k-1}$ $\endgroup$ Nov 3, 2017 at 7:55
  • 1
    $\begingroup$ Hey, that looks like A065176 ! $\endgroup$ Nov 3, 2017 at 7:59
  • 2
    $\begingroup$ As to what coefficients are not zero in $a_n(x)$, note that $a_n(x)=U_n(x/2) \mod 2$, (where $U_n$ are Chebyshev polynomials of second kind), since they solve the same linear recurrence mod 2. $\endgroup$ Nov 3, 2017 at 11:37
  • 2
    $\begingroup$ And the coefficients of $U_n(x/2)$ are binomial coefficients. $\endgroup$ Nov 3, 2017 at 12:02
  • 3
    $\begingroup$ So $[x^r]a^n\neq0$ iff $n-r$ is even and $\big({{n+r\over 2} \atop {n-r\over 2}}\big)$ is odd, which is given by Lucas theorem (sorry, bad connection). This explains why $a_{n}=x^n$ for $n=2^k-1$: the binomial coefficients then fall into a one of those large even $\nabla$-shaped regions within the Pascal triangle $\Delta$. $\endgroup$ Nov 3, 2017 at 12:39

More experimental facts. I think it should not be too hard prove them by induction, taking into account that we know exactly when the coefficients of $a_n$ are non-zero (see my comment to მამუკა ჯიბლაძე's answer).

Given a sequence $\epsilon_{2^n}\in\{-1,+1\}$ for $n\ge1$, let's define inductively the sequence $(\epsilon_j)_{j\ge1}$ for all positive integers according to the recurrence relations:

$$\epsilon_{2^n+1}=-\epsilon_{2^n}\qquad\text{for }n\ge1 $$

$$\epsilon_{2^n+j}=\epsilon_{2^n-j+1}\qquad\text{for }2\le j< 2^n\ ,$$

and also define

$$ \eta_j:=\begin{cases} (-1)^{ j\over 2},& \text {for even }\ j \\ \\ (-1)^{ j-1\over 2}\epsilon_{j+2}, &\text {for odd } j \ .\\ \end{cases} $$ and $$ \delta_j:=\begin{cases} -1,& \text {for }\ j=0 \\ \\ 1, &\text {for } j\neq0 \ .\\ \end{cases} $$

Then (experimentally) the polynomials $a_k= a_k(x,\epsilon_2,\epsilon_4,\dots,\epsilon_{2^n})$ are determined inductively by $a_{-1}:=0, a_0:=1$, and by the recurrence relation, for any $0\le n$ and any $0\le j< 2^n\ $

$$a_{2^n+j}=x^{2^n}b_j+ {\delta_{2^{n-1}-1-j}}\ \eta_j\ \epsilon_{2^n}\ a_{2^n-2-j},$$

$$b_j:=a_j(x,\epsilon_2,\epsilon_4,\dots,\epsilon_{2^{n-2}},-\epsilon_{2^{n-1}})\ .$$

For, instance the above gives $$a_{51}={x}^{51}-\epsilon_{{4}}\epsilon_{{16}}{x}^{43}+ \epsilon_{{8}} \epsilon_{{16}}{x}^{35}+ \epsilon_{{4}}\epsilon_{{32}}{x}^{11}-\epsilon_ {{8}}\epsilon_{{32}}x^3$$

  • $\begingroup$ Is there a typo in the definiton of $a_{2^n+j}$? Because the leading term must be $x^{2^n+j}$ while as it stands, degree seems to be $2^n$ only... $\endgroup$ Nov 4, 2017 at 15:17
  • 1
    $\begingroup$ No, sorry if it wasn't clear: $b_j$ is itself a polynomial of degree $j$, namely $a_j$ but with the sing of $\epsilon_{2^{n-1}}$ inverted. (I added the the $x$ in the notation for clarity) $\endgroup$ Nov 4, 2017 at 15:39
  • 1
    $\begingroup$ Still it is complete mystery for me why the constraints completely free themselves up at each power of two precisely... $\endgroup$ Nov 4, 2017 at 16:22
  • 3
    $\begingroup$ If $x a_{m-1}$ and $a_{m-2}$ have a non-zero term at the same location then the sign $\pm$ in $a_m = x a_{m-1} + a_{m-2}$ is forced. Presumably one can show using Lucas's theorem that this situation occurs for all $m$ that are not powers of two. Then it should be possible to show by induction that Pietro's recipe above completely parameterises all solutions, which presumably finishes off the problem. $\endgroup$
    – Terry Tao
    Nov 5, 2017 at 0:23
  • 2
    $\begingroup$ I think it must be $a_{2^n+j}=x^{2^n}b_j+\epsilon_{2^n} \delta_j a_{2^n-\color{red}{2}-j}$ in your recursion formula. $\endgroup$
    – Wolfgang
    Nov 5, 2017 at 9:58

Not an answer yet but too long for a comment.

For the $a_n$ as in მამუკა ჯიბლაძე's answer, it is worth to look at even and odd indices separately. In fact, for $n$ odd, $a_n$ only seems to have terms for $x^{n-4k}$ and $[x^{n-4k}]a_n=[x^{n-4k-1}]a_{n-1}$, so all the information is contained in the even polynomials.

Writing $r$ for $\varepsilon_{2^r}$ and keeping the signs, we have the following coefficients:

$\begin{array} {rrrrrrrrrrrrrrrr} n&|&x^{n-2}&x^{n-4}&.&x^{n-8}&.&.&.&x^{n-16}\\ \hline 2&|&1\\ \hline 4&|&2&12\\ 6&|&-1&&-2\\ \hline 8&|& 3&-13&&-23\\ 10&|& 1&&-3&-23&-123\\ 12&|& -2&-12&&&3&13\\ 14&|& -1&&2&&&&-3\\ \hline 16&|& 4&-14&&24&&&&-34\\ 18&|& 1&&-4&24&124&&&-34&-134\\ 20&|& 2&12&&&4&14&&-34&-234&-1234\\ 22&|& -1&&-2&&&&-4&-34&134&&234\\ \end{array}$

Except for the signs, which keep some mystery, the patterns of the columns seem already essentially predictable, everything in terms if the A006519 sequence. If you compute some more lines, it should be entirely clear (e.g. what happens in the 5th column?), and from there of course possible to prove that by some induction.

If one adds to your list of $\varepsilon_{n}$'s the lines $\varepsilon_{2^k}=\varepsilon_{2^k}$ for completeness, then the pattern of indices 2,2,4,4,2,2,8,8,2,2,4,4,2,2,16,16... in particular also should be isomorphic to the (doubled) A006519 sequence. But the signs...? (Sadly, $\varepsilon_{22}=-\varepsilon_{2}$.)

Also note that the "main diagonal" of this table (i.e. the array of the absolute terms of the even $a_n$), taken as a binary code, seems to encapsulate a bijection $ 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, ...$ from $\mathbb N\to\mathbb N$, more precisely the Gray code A003188.


On the uniqueness given the data $\{\epsilon_{2^n}\}_{n\ge1}$. As observed by Terry Tao in a comment, the sign in $xa_{m-1}\pm a_{m-2}$ is forced precisely when for some $r$, one has $$[x^r](xa_{m-1})=[x^r]a_{m-2}=1\mod 2$$ (because for integers $a,b$ in $\{-1,0,1\}$ the equation $|a+\epsilon b|\le1$ has a unique solution $\epsilon$ in $\{-1,1\}$ if and only if $|a|=|b|=1$). But the parity of the coefficients of the $a_m$ is known, for $a_m=\sum_{0\le j\le{n/2}}{m-j\choose j}x^{m-2j}\mod 2$ (this follows immediately by induction from the additive formula of binomials).

Therefore, the value of $\epsilon_m$ is free if and only if $ {m-i\choose i-2}{m-i\choose i-1}$ is even for all $i\ge2$. But this is never the case if $m$ is not a power of $2$: indeed, if for some $a$ one has $2^a<m<2^{a+1}$, then $2\le i:=m-2^a+1\le 2^a$, so $m-i=2^a-1$, and both $ {m-i\choose i-2}$ and ${m-i\choose i-1}$ are odd, because all binomial coefficients ${2^a-1 \choose k}$ for $k=0,\dots,2^a-1$ are odd.


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:

  1. In the first summand, $b_{2(8k-7)}$ and $b_{2(8k-5)}$, then $b_{2(8k-3)}$ and $b_{2(8k-1)}$,
  2. 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:

  1. In the first summand, $b_{4(4k-3)}$ and $b_{4(4k-1)}$,
  2. 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.