$\def\Ker{\operatorname{Ker}}$Let me try to rewrite my answer --- at least, for clarity reasons. Thanks to Pat Devlin and YCor for stimulation.

First, several definitions. A $k$-triangle is a triangle constructed in the described way. We work over $\mathbb F_2$; the $k$-dimensional coordinate space is denoted by $V_k$ (so, any side of a $k$-triangle is a vector in this space). There is a linear operator $\varphi_k\colon V_k\to V_k$ mapping the top vector of a $k$-triangle into its right vector. We have $\varphi_k^3=1$, so $V_k=U_k\oplus W_k$, where $U_k=\Ker(\varphi+1)$ and $W_k=\Ker(\varphi^2+\varphi+1)$ (recall that $1=-1$). Denote $u_k=\dim U_k$ and $w_k=\dim W_k$ (*one can see that $w_k$ is always even*). For every $v\in V_k$, its $U_k$- and $W_k$-part are $x_u=(\varphi_k^2+\varphi_k+1)x\in U_k$ and $x_w=(\varphi_k^2+\varphi)x\in W_k$ (recall that $x=x_u+x_w$).

We say that vectors in $U_k$ are *stable*. Vectors starting with $1$ are *proper*. So, we are interested in the number of proper stable vectors, and it is either $2^{u_k-1}$ or $0$, depeding on whether $U_k$ contains a proper vector or not.

**Observation 1.** Each vector in $U_k$ has equal first and last coordinates. So, for $k\geq 2$ the space $W_k$ contains a vector with distinct first and last coordinates. The triangles of such vectors have all three sides in $W_k$ and have two ones at the corners. Hence, there are vectors in $W_k$ starting with $1$ and endind with $0$, starting with $0$ and ending with $1$, and also starting and ending with $1$.

Introduce also the following mixing operator. If $a,b\in V_k$, then $\mu_{2k}(a,b)=(a_1,b_1,a_2,b_2,\dots,a_k,b_k)\in V_{2k}$. If $a\in V_{k+1},b\in V_k$, then $\mu_{2k+1}(a,b)=(a_1,b_1,\dots,a_k,b_k,a_{k+1})\in V_{2k+1}$. For $c\in V_n$, denote by $o(c)\in V_{\lceil n/2\rceil}$ and $e(c)\in V_{\lfloor n/2\rfloor}$ the unique vectors such that $\mu_n(o(),e(c))=c$.

The indices will be omitted when they are clear.

Finally, for a vector $c\in V_{k+1}$ we denote by $c\rangle, \langle c\in V_k$ the vector $c$ without the last coordinate and without the first coordinate, respectively. By $\overleftarrow c$ we denote the left cyclic shift of $c$, i.e., $(c_2,c_3,\dots,c_1)$.

**Observation 2.** The sum of the three digits in the vertices of a $3$-triangle is zero. By induction, the same holds for any $(2^k+1)$-triangle.

**Corollary 1.** There are no proper stabe vectors in $U_{2^k+1}$.

**Corollary 2.** Ay $k$-triangle falls into four sparse triangles (of sizes $\lceil k/2\rceil$, $\lfloor k/2\rfloor$, $\lfloor k/2\rfloor$, and $\lceil k/2\rceil-1$).

**Corollary 3. (a)** Let $a,b\in V_k$, and let $\varphi_{2k}(\mu(a,b))=\mu(c,d)$. Then $c=\varphi_k(b)$ and $d=\varphi_k(a)+c=\varphi_k(a+b)$. The first claim is clear; the second follows from the observation that a sparse $k$-triangle with $d$ on the right has $a+b$ on the top.

**(b)** Let $a\in V_{k+1}$, $b\in V_k$, and let $\varphi_{2k+1}(\mu(a,b))=\mu(c,d)$. Then $c=\varphi_{k+1}(a)$ and $d=\varphi_k(b+\langle a)=\varphi_k(b)+c\rangle$.

Hugh. Now come to the problem itself.

Assume first that **$n=2k$ is even**. Then $c=\mu(a,b)\in V_{2k}$ lies in $U_{2k}$ iff $a=\varphi_k(b)$ and $b=\varphi_k(a+b)$, so $b=\varphi_k^2(b)+\varphi_k(b)$, i.e., $b\in W_k$ (and hence $a\in W_k$ as well). Therefore, we have a one-to-one correspondence $W_k\to U_{2k}$ given by $a\mapsto \mu(a,\varphi^2(a))$, and proper vectors correspond to proper ones.

Therefore,
$$
u_{2k}=w_k=k-u_k,
$$
and the number of proper stable $2k$-vectors is $2^{w_k-1}$ by Observation 1.

Now comes a bit harder case when **$n=2k+1$ is odd**. A vector $c=\mu(a,b)\in V_{2k+1}$ is stable iff $\varphi(a)=a$ and $\varphi(b)=b+a\rangle$, which rewrites as $a\rangle=(\varphi+1)(b)=\varphi^2(b_w)$. Similarly, we get $\langle a(=\overleftarrow{a\rangle})=\varphi(b_w)$.

So, basicaly we need to search for (proper) $a\in U_{k+1}$ such that $a\rangle\in W_k$; each such will lead to $2^{w_k}$ (proper) stable vectors of the form $\mu(a,b)$, where $b_u=\varphi(a\rangle)$. In other words, we need to find the dimendsion of $W_k\cap (U_{k+1}\rangle)$ and check whether it contains proper vectors.

But in fact $U_{k+1}\rangle \subseteq W_k$. Indeed, take the $(k+1)$-triangle with first row $a$ and remove that first row. We will get the $k$-triangle with top vector $\langle a+a\rangle$, right vector $\langle a$ and left vetor $a\rangle$ which sum up to $0$, as desired.

Hence we get
$$
u_{2k+1}=u_{k+1}+u_k.
$$

Now the small values yield the dimensions claimed by YCor, namely $u_k=a,a+1,a$ when, respectively, $k=3a,3a+1,3a+2$. Mpreover, each $U_{2k}$ contains a proper vector, and $U_{2k+1}$ does contains a one iff $U_{k+1}$ does. This yields that proper stable vectors exist for all $n$ except for those of the form $2^t+1$, and their number is exactly $2^{u_n-1}$ in all thoese cases. We are done.

25more comments