Counting binary strings of length $n$ that contain no two adjacent blocks of 1s of the same length?

I confirm your results for $n \le 16$. It might be useful to compute the values by conditioning on $k\in\{1,\dots,\lfloor(n+3)/2\rfloor\}$: \begin{matrix} n\backslash k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 0 & 1 \\ 1 & 1 & 1 \\ 2 & 1 & 3 \\ 3 & 1 & 6 & 0 \\ 4 & 1 & 10 & 2 \\ 5 & 1 & 15 & 8 & 0 \\ 6 & 1 & 21 & 22 & 1 \\ 7 & 1 & 28 & 48 & 6 & 0 \\ 8 & 1 & 36 & 92 & 25 & 0 \\ 9 & 1 & 45 & 160 & 77 & 2 & 0 \\ 10 & 1 & 55 & 260 & 196 & 16 & 0 \\ 11 & 1 & 66 & 400 & 437 & 74 & 1 & 0 \\ 12 & 1 & 78 & 590 & 883 & 254 & 9 & 0 \\ 13 & 1 & 91 & 840 & 1652 & 726 & 54 & 0 & 0 \\ 14 & 1 & 105 & 1162 & 2908 & 1818 & 239 & 2 & 0 \\ 15 & 1 & 120 & 1568 & 4869 & 4116 & 857 & 24 & 0 & 0 \\ 16 & 1 & 136 & 2072 & 7819 & 8602 & 2627 & 156 & 1 & 0 \\ \end{matrix}

Maybe try inclusion-exclusion together with stars-and-bars? For fixed $k$, the first term of inclusion-exclusion is the number of nonnegative integer solutions to $$\sum_{j=1}^k x_j + \sum_{j=1}^{k-1} y_j = n - (k-2) - (k-1) = n-2k+3,$$ which is $$\binom{(n-2k+3) + (2k-1)-1}{(2k-1)-1} = \binom{n+1}{2k-2}.$$ For $k\in\{1,2\}$, this formula is correct. For $k \ge 3$, it is only an upper bound.

---

An alternative approach is to condition on the tail $(y_{k-1},x_k)$. Explicitly, let state space $$S_n = \left\{k \in \{1,\dots,\lfloor(n+3)/2\rfloor\}, y \in \{[k\not=1],\dots,n\}, x \in \{0,\dots,n-y-2k+5\}\right\}.$$ For $(k,y,x) \in S_n$, let $f_n(k,y,x)$ be the number of such binary strings that end in $1^y 0^x$. Then $f$ satisfies the recursion $$f_n(k,y,x) = \begin{cases} 1 &\text{if $n = 0$} \\ [y = 0 \land x = n] &\text{if $k = 1$} \\ \sum\limits_{\substack(k-1,y_{k-2},x_{k-1}) \in S_{n-y-x}:\\ y_{k-2} \not= y \land ((y_{k-2} \ge 1 \land x_{k-1} \ge 1) \lor k=2)} f_{n-y-x}(k-1,y_{k-2},x_{k-1}) &\text{otherwise} \end{cases}$$

The desired values are then $\sum\limits_{(k,y,x) \in S_n} f_n(k,y,x)$.

An aproximation for large $n$

The runs of $0$s and $1$s can be approximated by iid geometric random variables (with $p=1/2$, mean $2$). Hence we have in average $n/2$ runs, of which $n/4$ are runs of $1$s.

Then, the problem is asymtpotically equivalent to : given $m=n/4$ iid Geometric variables $X_1, X_2 \cdots X_m$ find $P_m=$ probability that $X_{i+1} \ne X_i$ for all $i$.

This does not seem a trivial problem, though (and I haven't found any reference).

A crude aproximation would be to assume that the events $X_{i+1} \ne X_i$ are independent. Under this assumption we get

$$P_m \approx P_2^{m-1}= (2/3)^{m-1} \tag 1$$

This approximation is not justified, and it does not seem to improve with $n$ increasing.

The exact value can be obtained by a recursion on the probabilities for each final value, which together with a GF gives me this recursion :

$$P_m = r(1,m) $$

$$r(z,m)= \frac{1}{2z-1} r(1,m-1) - r(2z,m-1) \tag 2$$

with the initial value $r(z,1)=\frac{1}{2z-1}$

Finally, the total number of valid sequences is $C_m = P_m \, 2^n$ ($n=4m$)

I've not yet found an explicit or asympotic for $(2)$.

Some values oc $C_m$

n    m  r(2)            iid(1)          exact
4    1  16              16              13
8    2  170.6           170.6           154
12   3  1950.5          1820.4          1815
16   4  21637.3         19418.1         21414
20   5  243540.2        207126.1        252680     
24   6  2720810.9       2209345.3       2981452
28   7  30515606.3      23566350.0      35179282

Here I am going to use generating functions like in this answer to a related problem to compute columns of @RobPratt table for $k \ge 3$.

We can define:

$$S_y(k,i) = \left\{\text{n. of solutions for} \sum_{j=1}^{k-1} y_j = i \text{ with } y_j \neq y_{j+1}\right\} \tag{1}\label{1}$$

and then scompose the problem as follows:

$$\left\{\text{n. of solutions for} \sum_{j=1}^k x_j + \sum_{j=1}^{k-1} y_j = n-2k+3 \right\}=\\ \sum_{i=0}^{n-2k+3}\left\{\text{n. of solutions for} \sum_{j=1}^k x_j = n-2k+3-i \right\}S_y(k) =\\ \sum_{i=0}^{n-2k+3}{n-k+2-i \choose k-1}S_y(k,i) \tag{2}\label{2}$$

When $k=3$, the problem of determining $S_y(k,i)=S_y(3,i)$ is all the same as in the above linked problem, only with $2$ variables instead of $4$. Instead of repeating all calculations we can reuse the above answer, removing all terms with an exponent for $y$ greater than $2$, to get the generating function:

$$f(x)=\left[\frac{y^2}{2!}\right]\prod_{n\ge0}(1+yx^n) = \left[\frac{y^2}{2!}\right]\left( 1+\frac y{1-x}+ \frac12\frac{y^2}{(1-x)^2}\right)\left( 1-\frac12\,\frac{y^2}{1-x^2}\right)=\\ \frac{1}{(1-x)^2}-\frac{1}{1-x^2}=\sum_{n=0}^{\infty}\left\{\frac 12 \left[1+(-1)^{n+1}\right]+n\right\}x^n$$

where in the last step I have used WolframAlpha because I am lazy, and then:

$$S_y(3,i) = [x^i]f(x) = \frac 12 \left[1+(-1)^{i+1}\right]+i \tag{3}\label{3}$$

OK, yes, using generating functions for $k = 3$ and $y_1+y_2=i$ is a little overkill, because the $\eqref{3}$ result is obvious (once we choose a value for $y_1$, and this can be done in $i+1$ ways, then $y_2$ is determined; after that the first addendum is needed to discard the $y_1=y_2=i/2$ solution when $i$ is even). Anyway, replacing in $\eqref{2}$ we obtain the formula for the third column of @RobPratt table:

$$\sum_{i=0}^{n-3}{n-1-i \choose 2}\left\{\frac 12 \left[1+(-1)^{i+1}\right]+i\right\}=\\ \frac 1{48} (2 n^4 - 8 n^3 + 4 n^2 + 8 n + 3 (-1)^n - 3)\tag{4}\label{4}$$

where again I have used WolframAlpha for the last step (verified against @RobPratt table here).

Still thinking how to extend this to $k \gt 3$...