Given any integer $n \ge 0$, let $( n_0, n_1, n_2, \ldots )$ be its binary representation, i.e.
$$n = \sum_{i=0}^\infty n_i 2^i, \quad n_i \in \{ 0, 1 \}$$
Let $P(n) = n_0$ be the parity of $n$ and $N(n) = \sum\limits_{i=0}^\infty n_i$ be the number of set bits in this binary representation. It is not hard to see
$t_n = 1$ when and only when $N(n)$ is odd. i.e.
$$t_n = P(N(n))$$
Notice
$$n - \sum_{k=1}^n (-1)^{\binom{n}{k}}
= \sum_{k=0}^n \left(1 - (-1)^{\binom{n}{k}}\right) -2
= 2\sum_{k=0}^nP\left(\binom{n}{k}\right) - 2\tag{*1}
$$
For any $0 \le k \le n$, let $(k_0,k_1,k_2,\ldots)$ be the binary representation of $k$.
By Lucas' theorem, we have
$$P\left(\binom{n}{k}\right) = \prod_{i=0}^\infty P\left(\binom{n_i}{k_i}\right)$$
where $\displaystyle\;\binom{n_i}{k_i}$ should be interpreted as $0$ whenever $n_i < k_i$.
In order for the summand in RHS of $(*1)$ to be non-zero,
- For those $i$ where $n_i = 1$, $k_i$ can be $0$ or $1$.
- For those $i$ where $n_i = 0$, $k_i$ can only be $0$.
This means in the rightmost sum of $(*1)$, exactly $2^{N(n)}$ of $P(\cdot)$ contributes. This leads to
$$\begin{align}
& n - \sum_{k=1}^n(-1)^{\binom{n}{k}} = 2^{N(n)+1} - 2 \equiv 2P(N(n)) \pmod 3\\
\implies &
\frac43\sin^2\left(\frac{\pi}{3}\left(n - \sum_{k=1}^n (-1)^{\binom{n}{k}}\right)\right)
= \frac43\sin^2\left(\frac{2\pi}{3}P(N(n))\right)
\stackrel{\color{blue}{\because P(\cdot) = 0\text{ or } 1}}{=}
P(N(n)) = t_n
\end{align}$$
I get heuristically , for the sequence beginning with $n=0$ and $$T(n)=\text{Hammingweight}(n) \\
\qquad \qquad =\text{bitcount}(n) \pmod 2 \tag 1$$ for $s(n)=\sum_{k=0}^n T(n)$
$$ s(n)=\sum_{k=0}^n T(n) = \frac n2 + \begin{cases}
T(n) &\text{if } n \equiv 0,2 \pmod 4 \\
\frac 12 &\text{if } n \equiv 1,3 \pmod 4 \\
\end{cases} \tag 2$$
(modulo typing-error)....
Using $(-1)^n$ one can even make a oneliner from Eq (2).
----------------------------------------------
n T(n) s(n) n/2 + T(n)
----------------------------------------------
0 0 0 0
4 1 3 2
8 1 5 4
12 0 6 6
16 1 9 8
20 0 10 10
24 0 12 12
28 1 15 14
----------------------------------------------
n T(n) s(n) n/2 +1/2
----------------------------------------------
1 1 1 1/2 1/2
5 0 3 5/2 1/2
9 0 5 9/2 1/2
13 1 7 13/2 1/2
17 0 9 17/2 1/2
21 1 11 21/2 1/2
25 1 13 25/2 1/2
29 0 15 29/2 1/2
----------------------------------------------
n T(n) s(n) n/2 +T(n)
----------------------------------------------
2 1 2 1
6 0 3 3
10 0 5 5
14 1 8 7
18 0 9 9
22 1 12 11
26 1 14 13
30 0 15 15
----------------------------------------------
n T(n) s(n) n/2 +1/2
----------------------------------------------
3 0 2 3/2 1/2
7 1 4 7/2 1/2
11 1 6 11/2 1/2
15 0 8 15/2 1/2
19 1 10 19/2 1/2
23 0 12 23/2 1/2
27 0 14 27/2 1/2
31 1 16 31/2 1/2
Best Answer
If you want an algorithm then here it is: the Prouhet-Morse-Thue sequence is given by the iteration of the map $1\mapsto 10, 0\mapsto 01$ starting with $1$. If you want to check if a word $w$ is a subword of the sequence, start with $1$ and iterate the map sufficient number of times. The sequence is uniformly recurrent (Morse), so "sufficient" is not large, at most $|w|$ in this case because every subword $U$ of length $2^{n}$ contains all subwords of length $n$. I am sure that the $2^n$ bound can be made polynomial and that the original problem is in $P$.
Edit. In fact by Theorem 8.2 in Morse, Marston; Hedlund, Gustav A. Symbolic Dynamics. Amer. J. Math. 60 (1938), no. 4, 815–866 one can replace $2^n$ above by $10n$ and so the number of iterations needed is $O(\log n)$ and the time complexity of the problem is $O(n^2)$ (or $O(n)$ depending on the mode of computation).