Assume we have: \begin{cases} a_{n} = 2^{n} \times \left(1 - b_{{\left\lfloor \frac{n}{2} \right\rfloor}}\right) \\ b_{n} = b_{n - 1} + \frac{a_{n}}{4^{n}} \\ b_{0} = 0 \end{cases}
I tried finding the closed formula for $a_{n}$ using generator functions. But I am stuck at this point: $$ \frac{1}{1 - x} - A(\frac{x}{2}) = \frac{1}{1 - x} \cdot \left(A(\frac{x^{2}}{4}) - 1\right) $$
in which: $$ A(x) = \sum_{i = 0}^{\infty} a_{i}x^{i}, B(x) = \sum_{i = 0}^{\infty} b_{i}x^{i}$$
This is how I got to this point: $$ A(\frac{x}{2}) = (a_{0}, 1 - b_{0}, 1 - b_{1}, \dots) \Rightarrow \frac{1}{1 - x} - A(\frac{x}{2}) = (0, b_{0}, b_{1}, b_{1}, b_{2}, b_{2}, \dots) $$ $$ B(x^{2}) + xB(x^{2}) = \frac{1}{1 - x} - A(\frac{x}{2}) $$ and we also have: $$ B(x) = \frac{A(\frac{x}{4}) - 1}{1 - x} $$ with a little algebra, you should get there.
Can the closed formula be found? If so how can I proceed with the solution? If you have any other solution I would be glad to hear it.
I'm not sure about the title of this question and which category of generator functions I should put this in. Please edit this if you know a better title.
P.S.
$a_{n}$ counts the number of binary strings of length $n$ which doesn't have the same prefix and suffix of any length. (except the prefix or suffix that covers all the string.) Keep this in mind if it is helpful.
As mentioned in comments, you can find the sequence in OEIS