Counting binary strings of length $n$ that contain no two adjacent blocks of 1s of the same length? Is it possible to count exactly the number of binary strings of length $n$ that contain no two adjacent blocks of 1s of the same length? More precisely, if we represent the string as $0^{x_1}1^{y_1}0^{x_2}1^{y_2}\cdots 0^{x_{k-1}}1^{y_{k-1}}0^{x_k}$ where all $x_i,y_i \geq 1$ (except perhaps $x_1$ and $x_k$ which might be zero if the string starts or ends with a block of 1's), we should count a string as valid if $y_i\neq y_{i+1}$ for every $1\leq i \leq k-2$.
Positive examples : 1101011 (block sizes are 2-1-2), 00011001011 (block sizes are 2-1-2), 1001100011101 (block sizes are 1-2-3-1)
Negative examples : 1100011 (block sizes are 2-2), 0001010011 (block sizes are 1-1-2), 1101011011 (block sizes are 2-1-2-2)
The sequence for the first $16$ integers $n$ is:  2, 4, 7, 13, 24, 45, 83, 154, 285, 528, 979, 1815, 3364, 6235, 11555, 21414. For $n=3$, only the string 101 is invalid, whereas for $n=4$, the invalid strings are 1010, 0101 and 1001.
 A: 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

A: 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$...
A: Consider a binary string  with $s$ ones and $m$ zeros in total.
Let's put an additional (dummy) fixed zero at the start and at the end of the string.
We individuate as a run the consecutive $1$'s between two zeros, thereby including runs of null length. With this scheme we have a fixed number of $m+1$ runs.

The number of different strings with the  above numbers of zeros and ones is obviously
$$
\left( \matrix{  m + s \cr   s \cr}  \right) = \left( \matrix{  m + 1 + s - 1 \cr   s \cr}  \right)
$$
which corresponds to the weak compositions
of $s$ into $m+1$ parts.
The number of compositions of $s$ into $k$ non-null parts (strong compositions) is instead
$$ \binom{s-1}{k-1} $$
and
$$
\eqalign{
  & \left( \matrix{  m + s \cr   s \cr}  \right)
 = \sum\limits_{\left( {1\, \le } \right)\,k\,\left( { \le \,\min \left( {m + 1,s} \right)} \right)}
 {\left( \matrix{  m + 1 \cr   k \cr}  \right)\left( \matrix{  s - 1 \cr   k - 1 \cr}  \right)}  =   \cr 
  &  = \sum\limits_{\left( {1\, \le } \right)\,k\,\left( { \le \,\min \left( {m + 1,s} \right)} \right)}
 {\left( \matrix{  m + 1 \cr  m + 1 - k \cr}  \right)\left( \matrix{  s - 1 \cr   k - 1 \cr}  \right)}  \cr} 
$$
So we can concentrate on strong compositions with no equal consecutive parts.
Consider the strong composition of $s$ into $k$ parts, the last of which is $r$
$$
\left[ {r_{\,1} ,\,r_{\,2} ,\; \cdots ,\,r_{\,k - 1} ,r\;} \right]
\quad \left| {\;r_{\,1}  + \,r_{\,2}  + \; \cdots  + \,r_{\,k - 1}  + r = s} \right.
$$
whose number is
$$
C_T(s,k,r) = \left[ {k = 1} \right] + \left( \matrix{  s - r - 1 \cr   k - 2 \cr}  \right)
 = \left( \matrix{  s - r - 1 \cr   s - r - k + 1 \cr}  \right)
\quad \left| \matrix{  \;1 \le k \le s \hfill \cr   \;1 \le r \le s \hfill \cr}  \right.
$$
where $[P]$ denotes the Iverson bracket.
Then the sum over $r$ will correctly give
$$
\eqalign{
  & \sum\limits_{r = 1}^s {C_T (s,k,r)}
  = \sum\limits_{r = 1}^s {\left( \matrix{  s - r - 1 \cr   s - r - k + 1 \cr}  \right)}
  = \sum\limits_{j = 0}^{s - 1}
 {\left( \matrix{  j - 1 \cr   j - k + 1 \cr}  \right)}  =   \cr 
  &  = \sum\limits_{\left( {k - 1\, \le } \right)\,j\,\left( { \le \,s - 1} \right)}
 {\left( \matrix{  s - 1 - j \cr   s - 1 - j \cr}  \right)\left( \matrix{  j - 1 \cr  j - k + 1 \cr}  \right)}
  = \left( \matrix{  s - 1 \cr   s - k \cr}  \right) \cr} 
$$
Let's indicate with $C_G (s,p,r), \; C_B (s,p,r)$ the number of good and bad strong compositions of $s$ into  $p$ parts the last of which
equal to $r$.
Then we have the relations
$$
\left\{ \matrix{
  C_T (s,p,r) = \left[ {1 \le p \le s} \right]\left[ {1 \le r \le s} \right]\left( \matrix{
  s - r - 1 \cr 
  s - r - p + 1 \cr}  \right) \hfill \cr 
  C_G (s,1,r) = C_T (s,1,r) = \left[ {r = s} \right]\quad C_B (s,1,r) = 0 \hfill \cr 
  C_G (s,p,r) + C_B (s,p,r) = C_T (s,p,r) \hfill \cr 
  C_B (s,p,r) = \sum\limits_{k = 1}^{s - r} {C_B (s - r,p - 1,k)}  + C_G (s - r,p - 1,r) =  \hfill \cr 
   = \sum\limits_{k = 1}^{s - r} {C_B (s - r,p - 1,k)}  - C_B (s - r,p - 1,r) + C_T (s - r,p - 1,r) \hfill \cr 
  C_G (s,p,r) = \sum\limits_{k = 1}^{s - r} {C_G (s - r,p - 1,k)}  - C_G (s - r,p - 1,r) \hfill \cr}  \right.
$$
In particular for the good strong compositions we can write the recurrence
$$
C_G (s,p,r) = \sum\limits_{k = 1}^{s - r} {C_G (s - r,p - 1,k)}  - C_G (s - r,p - 1,r) + \left[ {1 = p} \right]\left[ {r = s} \right]
$$
After computing $C_G$, we can sum on $r$ and then go back along the previous steps
to compute the good weak compositions in terms of $s,m$ and finally the number in $n$,
i.e.:
$$
N_G (n) = \sum\limits_{s = 1}^n {\sum\limits_{p = 1}^{n - s + 1}
 {\left( \matrix{  n - s + 1 \cr   p \cr}  \right)
\sum\limits_{r = 1}^s {C_G (s,p,r)} } } 
$$
which in fact for $0 \le n \le 16$ gives
$$
0, \, 1, \, 3, \, 6, \, 12, \, 23, \, 44, \, 82, \, 153,
 \, 284, \, 527, \, 978, \, 1814, \, 3363, \, 6234, \, 11554, \, 21413
$$
not counting as good the all zeros string.
A: I am gonna attempt to complement RobPratt's proposed approach involving inclusion exclusion and stars and bars and be that person who posts a horribly long formula.
Consider $$A_{n,k,r}=\left |\left \{0^{l_1}1^{k_1}\cdots 0^{l_r}1^{k_r}0^{l_{r+1}}\in \{0,1\}^n: k_i>0,k_i\neq k_{i+1}, \sum _{i=1}^rk_i=k \text{ and for $i\neq 1,r+1,$ }l_i>0\right \}\right |.$$ Our desired result will be $$A_n=\sum _{k=0}^n\sum _{r=0}^nA_{n,k,r}.$$
Notice that we can, by the multiplication principle, express $A_{n,k,r}$ as
$$A_{n,k,r}=|B_{n,k,r}|\times |C_{k,r}|,$$
where $$B_{n,k,r}=\left \{(l_1,\cdots ,l_{r+1})\in \left (\mathbb{Z}^{\geq 0}\right )^{r+1}:\sum l_i=n-k, l_i>0 \text{ for $1<i<r+1$}\right \}$$
represents the way to place the $0'$s and $$C_{k,r}=\{(k_1,\cdots ,k_r)\in \left (\mathbb{Z}^{> 0}\right )^{r}:\sum k_i=k,k_i\neq k_{i+1}\}.$$
represents the way to place the 1's.
By stars and bars we get that  $|B_{n,k,r}|=\binom{n-k-(r-1)+(r+1)-1}{(r+1)-1}=\binom{n-k+1}{r}.$ Now, consider the following set $C_{k,r,x}=\{(k_1,\cdots k_r)\in C_{k,r}:k_x=k_{x+1}\}$ which carries the words with at least one consecutive chunk of 1's of the same size(at index $x$). To illustrate the next step, notice that $|C_{k,r,x}|=\sum _{t=1}^{\lfloor k/2\rfloor}\binom{k-2t-1}{r-2-1},$ for any $1\leq x<r$ by assuming the summands at position $x$ and $x+1$ are the same, this value is given by $t.$
We can then express $$C_{k,r}=\binom{k-1}{r-1}-\sum _{\ell =1}^{r-1}(-1)^{\ell -1}\sum _{X\in \binom{[r-1]}{\ell}}\left | \bigcap_{x\in X} C_{k,r,x}\right |,$$
but now the problem starts again because we need to know how many chunks of elements(consecutive) are in the set $X$ for us to be able to know how many summands are equal. When we know this, we can use stars and bars.  Call thr number of chunks $s$ and call the size of $i-$th chunk $\ell _i.$ Notice that we want $\ell _i>0$ and $\sum \ell _i=\ell.$ We then associate a number $t_i$ to be the number in the summand of all elements in the $i-$th chunk (for a total contribution of $(\ell _i+1)t_i$ to the whole sum). We get then that
$$C_{k,r}=\sum _{\ell =0}^{r-1}(-1)^{\ell}\sum _{s = 0}^{\ell}\sum _{\substack{ \ell_1+\cdots +\ell_s=\ell \\ \ell _i,t_i>0}}\binom{r-1-\ell -(s-1)+(s+1)-1}{s+1-1}\binom{k-\left (\sum _{i=1}^s(l_i+1)t_i\right )-1}{r-(\ell+s)-1}.$$
Putting all this together we get
$$A_{n}=\sum _{k=0}^n\sum _{r=0}^n\binom{n-k+1}{r}\sum _{\ell =0}^{r-1}(-1)^{\ell}\sum _{s = 0}^{\ell}\sum _{\substack{ \ell_1+\ell_2+\cdots +\ell_s=\ell \\ \ell _i,t_i>0}}\binom{r-\ell}{s}\binom{k-\left (\sum _{i=1}^s(l_i+1)t_i\right )-1}{r-(\ell+s)-1}.$$
In this formula,by the combinatorial interpretation, treat $\binom{-1}{-1}=1.$
Using sage I get the sequence $2,4,7,13,24,45,83,154,\dots.$
For the moment I do not see any way to make this less painful.

Another approach that might yield to something. Construct the DFA associated with that language (fix the maximal number of chunks to be $n$ and the maximum number of $1's$ in each chunk to be $k.$) The DFA looks like an $k\times n$ array and consider the Chomsky-Schutzenberger technique One has to solve a system of $k(n-k)$ equations and then try to take the limit as $n,k$ go to $\infty.$ The system to solve in variables $R_{i,j}\in \mathbb{Q}[[x]]$ looks like
$$R_{i,j}=\begin{cases}xR_{i,j+1}+xR_{j,0}+[i\neq j] & \text{If }j>0\\
xR_{i,1}+xR_{i,0}+1 & \text{If }j=0.\end{cases}$$
