Simple-looking sequences $A$ and $B$ defined by a complementary equation

Your formula is true. From the construction of the sequences $a_n$ and $b_n$, it is not hard to see that for all $n \in \mathbb{N}$:

\begin{equation} \begin{cases} b_{n + 1} - b_n & \in \left\lbrace 1, 2 \right\rbrace , \\ b_{n + 2} - b_n & \in \left\lbrace 2, 3 \right\rbrace . \end{cases} \end{equation}

In general : \begin{equation} b_{n + 1} - b_n = \begin{cases} 2 & \text{if } b_{n} + 1 \in \left\lbrace a_k, k \in \mathbb{N} \right\rbrace , \\ 1 & \text{else}. \end{cases} \tag{1} \end{equation}

This implies:

\begin{equation} \Delta_n := a_{n + 1} - a_n = \left(b_{2 n + 2} - b_{2 n} \right) + \left( b_{n + 1} - b_n \right) \in \left\lbrace 3, 4, 5 \right\rbrace . \tag{2} \end{equation}

It turns out that $\Delta_n$ actually follows a more rigid pattern. In particular, my key claim is the following: denote $x_n := \left( \Delta_n, a_n \mod 4 \right)$, then:

For all $n \in \mathbb{N}$, $x_n \in \left\lbrace \left( 3, 3 \right), \left( 4, 2 \right), \left( 4, 3 \right), \left( 5, 2 \right) \right\rbrace$. More precisely : \begin{equation} \begin{cases} \text{If } x_{n - 1} = \left( 3, 3 \right) \text{, then} & x_n \in \left\lbrace \left( 4, 2 \right), \left( 5, 2 \right) \right\rbrace , \\ \text{If } x_{n - 1} = \left( 4, 2 \right) \text{, then} & x_n \in \left\lbrace \left( 4, 2 \right), \left( 5, 2 \right) \right\rbrace , \\ \text{If } x_{n - 1} = \left( 4, 3 \right) \text{, then} & x_n \in \left\lbrace \left( 4, 3 \right), \left( 3, 3 \right) \right\rbrace , \\ \text{If } x_{n - 1} = \left( 5, 2 \right) \text{, then} & x_n \in \left\lbrace \left( 4, 3 \right), \left( 3, 3 \right) \right\rbrace . \end{cases} \tag{*} \end{equation}

Before turning to the proof of this claim, let us see how it yields your formula. It implies by induction the important fact that for all $n \in \mathbb{N}$ :

\begin{equation} a_n \in \left\lbrace 4 n + 2, 4 n + 3 \right\rbrace . \end{equation}

Let us now assume $b_{3 n + 2} = 4 n + 4$. Then, formula $(1)$ iterated three times yields :

\begin{equation} b_{3 \left( n + 1 \right) + 2} - b_{3 n + 2} = 4 , \end{equation}

because we now know $\left\lbrace a_k, k \in \mathbb{N} \right\rbrace$ intersects $\left[ 4 n + 4, 4 n + 8 \right]$ exactly once. Then, $b_{3 \left( n + 1 \right) + 2} = 4 \left( n + 1 \right) + 4$ and the original claim follows by induction:

\begin{equation} b_{3 n + 2} = 4 n + 4 . \end{equation}

I think the same argument can be used to prove similar formulas such as those sugested by another user.

Let us now mention the following fact, which will be helpful for my proof of $(*)$: from $(1)$ and $(2)$, it is straightforward that for $n \in \mathbb{N}$:

If $b_{n + 1} - b_n = 2$, then $b_{n + 2} - b_{n + 1} = 1$.

If $b_{n + 2} - b_n = 2$, then $b_{n + 4} - b_{n + 2} = 3$.

I now need to prove $(*)$, which I will do by induction. I only show the induction part, since it is easily checked that the claim holds for small values of $n$. Let $n$ big enough ($n \geq 5$ should suffice for my argument) and assume $(*)$ is true for all $0 \leq k \leq n$.

There are obviously 4 cases to consider:

Case 1: $x_n = \left( 3, 3 \right)$.

Since $a_{n + 1} = a_n + \Delta_n = 2 \mod 4$, it is enough to prove $\Delta_{n + 1} \in \left\lbrace 4, 5 \right\rbrace$. By hypothesis, in this case we have:

\begin{equation} 3 = \Delta_n = \underbrace{\left(b_{2 n + 2} - b_{2 n} \right)}_{\in \left\lbrace 2, 3 \right\rbrace} + \underbrace{\left( b_{n + 1} - b_n \right)}_{\in \left\lbrace 1, 2 \right\rbrace}. \end{equation}

Hence:

\begin{equation} \begin{cases} b_{2 n + 2} - b_{2 n} & = 2 , \\ b_{n + 1} - b_n & = 1 . \end{cases} \end{equation}

Thus by a previous remark:

\begin{equation} \begin{cases} b_{2 n + 4} - b_{2 n + 2} & = 3 , \\ b_{n + 2} - b_{n + 1} & \in \left\lbrace 1, 2 \right\rbrace . \end{cases} \end{equation}

And as wanted:

\begin{equation} \Delta_{n + 1} = \left( b_{2 n + 4} - b_{2 n + 2} \right) + \left( b_{n + 2} - b_{n + 1} \right) \in \left\lbrace 4, 5 \right\rbrace . \end{equation}

Case 2: $x_n = \left( 5, 2 \right)$.

It is enough to prove $\Delta_{n + 1} \in \left\lbrace 3, 4 \right\rbrace$. By hypothesis, in this case we have:

\begin{equation} 5 = \Delta_n = \underbrace{\left(b_{2 n + 2} - b_{2 n} \right)}_{\in \left\lbrace 2, 3 \right\rbrace} + \underbrace{\left( b_{n + 1} - b_n \right)}_{\in \left\lbrace 1, 2 \right\rbrace}. \end{equation}

Hence:

\begin{equation} \begin{cases} b_{2 n + 2} - b_{2 n} & = 3 , \\ b_{n + 1} - b_n & = 2 . \end{cases} \end{equation}

Thus by a previous remark:

\begin{equation} \begin{cases} b_{2 n + 4} - b_{2 n + 2} & \in \left\lbrace 2, 3 \right\rbrace , \\ b_{n + 2} - b_{n + 1} & = 1. \end{cases} \end{equation}

And as wanted:

\begin{equation} \Delta_{n + 1} = \left( b_{2 n + 4} - b_{2 n + 2} \right) + \left( b_{n + 2} - b_{n + 1} \right) \in \left\lbrace 3, 4 \right\rbrace . \end{equation}

Case 3: $x_n = \left( 4, 2 \right)$.

It is enough to prove $\Delta_{n + 1} \in \left\lbrace 4, 5 \right\rbrace$. By hypothesis, in this case we have:

\begin{equation} 4 = \Delta_n = \underbrace{\left(b_{2 n + 2} - b_{2 n} \right)}_{\in \left\lbrace 2, 3 \right\rbrace} + \underbrace{\left( b_{n + 1} - b_n \right)}_{\in \left\lbrace 1, 2 \right\rbrace}. \end{equation}

Hence we have to distinguish two subcases:

Subcase 3.1 :

\begin{equation} \begin{cases} b_{2 n + 2} - b_{2 n} & = 2 , \\ b_{n + 1} - b_n & = 2 . \end{cases} \end{equation}

In this case, a previous remark implies:

\begin{equation} \begin{cases} b_{2 n + 4} - b_{2 n + 2} & = 3 , \\ b_{n + 2} - b_{n + 1} & = 1. \end{cases} \end{equation}

And as wanted:

\begin{equation} \Delta_{n + 1} = \left( b_{2 n + 4} - b_{2 n + 2} \right) + \left( b_{n + 2} - b_{n + 1} \right) = 4 . \end{equation}

Subcase 3.2 :

\begin{equation} \begin{cases} b_{2 n + 2} - b_{2 n} & = 3 , \\ b_{n + 1} - b_n & = 1 . \end{cases} \end{equation}

We know:

\begin{equation} \Delta_{n + 1} = \underbrace{\left(b_{2 n + 4} - b_{2 n + 2} \right)}_{\in \left\lbrace 2, 3 \right\rbrace} + \underbrace{\left( b_{n + 2} - b_{n + 1} \right)}_{\in \left\lbrace 1, 2 \right\rbrace}. \end{equation}

Hence, it is enough to show that it is impossible to have:

\begin{equation} \begin{cases} b_{2 n + 4} - b_{2 n + 2} & = 2 , \\ b_{n + 2} - b_{n + 1} & = 1. \end{cases} \end{equation}

In light of previous remarks, this would imply the existence of $0 \leq i \leq j \leq n$ such that :

\begin{equation} \begin{cases} a_i & \in \left\lbrace b_n + 3, b_n + 4 \right\rbrace , \\ a_j & \in \left\lbrace b_{2 n} + 1, b_{2 n} + 2 \right\rbrace . \end{cases} \end{equation}

We now apply the induction hypothesis : $a_i, a_j \mod 4 \in \left\lbrace 2, 3 \right\rbrace$. Furthermore, in the case $a_i = b_n + 4$, the configuration is such that $b_n$, $b_{n + 1}$, $b_{n + 2}$, $b_{n + 3}$ are consecutive integers so that we can only have $\Delta_{i - 1} = 5$, thus by the induction hypothesis, $a_i = 3 \mod 4$. Similarly in the case $a_j = b_{2 n} + 1$, the configuration is such that $b_{2 n + 1}$, $b_{2 n + 2}$ , $b_{2 n + 3}$ , $b_{2 n + 4}$ are consecutive integers so that we can only have $a_j = 2 \mod 4$.

In all possible cases for $a_i$ and $a_j$, these considerations yield :

\begin{equation} \begin{cases} b_n \mod 4 & \in \left\lbrace 3, 0 \right\rbrace , \\ b_{2 n} \mod 4 & \in \left\lbrace 0, 1 \right\rbrace . \end{cases} \end{equation}

But this contradicts our initial hypothesis that modulo 4, $b_n + b_{2 n} = a_n = 2$.

Case 4: $x_n = \left( 4, 3 \right)$.

It is enough to prove $\Delta_{n + 1} \in \left\lbrace 3, 4 \right\rbrace$. By hypothesis, in this case we have:

\begin{equation} 4 = \Delta_n = \underbrace{\left(b_{2 n + 2} - b_{2 n} \right)}_{\in \left\lbrace 2, 3 \right\rbrace} + \underbrace{\left( b_{n + 1} - b_n \right)}_{\in \left\lbrace 1, 2 \right\rbrace}. \end{equation}

Hence we again have to distinguish two subcases:

Subcase 4.1 :

\begin{equation} \begin{cases} b_{2 n + 2} - b_{2 n} & = 2 , \\ b_{n + 1} - b_n & = 2 . \end{cases} \end{equation}

This is the same as case 3.1, and implies: $\Delta_{n + 1} = 4$.

Subcase 4.2 :

\begin{equation} \begin{cases} b_{2 n + 2} - b_{2 n} & = 3 , \\ b_{n + 1} - b_n & = 1 . \end{cases} \end{equation}

We know:

\begin{equation} \Delta_{n + 1} = \underbrace{\left(b_{2 n + 4} - b_{2 n + 2} \right)}_{\in \left\lbrace 2, 3 \right\rbrace} + \underbrace{\left( b_{n + 2} - b_{n + 1} \right)}_{\in \left\lbrace 1, 2 \right\rbrace}. \end{equation}

Hence, it is enough to show that it is impossible to have:

\begin{equation} \begin{cases} b_{2 n + 4} - b_{2 n + 2} & = 3 , \\ b_{n + 2} - b_{n + 1} & = 2. \end{cases} \end{equation}

The induction hypothesis implies that $x_{n - 1} \in \left\lbrace \left(4, 3 \right), \left(5, 2 \right) \right\rbrace$. Hence, it suffices to consider the three following subsubcases :

Subsubcase 4.2.1 : $x_{n - 1} = \left(4, 3 \right)$ and:

\begin{equation} \begin{cases} b_{2 n} - b_{2 n - 2} & = 3 , \\ b_{n} - b_{n - 1} & = 1 . \end{cases} \end{equation}

Subsubcase 4.2.1 : $x_{n - 1} = \left(4, 3 \right)$ and:

\begin{equation} \begin{cases} b_{2 n} - b_{2 n - 2} & = 2 , \\ b_{n} - b_{n - 1} & = 2 . \end{cases} \end{equation}

Subsubcase 4.2.1 : $x_{n - 1} = \left(5, 2 \right)$ and:

\begin{equation} \begin{cases} b_{2 n} - b_{2 n - 2} & = 3 , \\ b_{n} - b_{n - 1} & = 2 . \end{cases} \end{equation}

In all three of the subsubcases, I find that the same argument as in the subcase 3.2 yields a contradiction ($a_n$ can never be 3 modulo 4 as assumed). Hopefully, I did not make any mistake in this long and tedious argument, so that this proves the induction hypothesis is true at rank $n + 1$.

This is another observation showing that, after all, the pattern is only partially regular. The diagram refers to Greg Martin's comment with the observation that for $n\equiv1\pmod3$, the choice between $b_n=\lfloor 4n/3+7/6 \rfloor$ and $b_n=\lceil 4n/3+7/6 \rceil$ does not follow an easy pattern. It appears that rounding down happens more often than rounding up, and it is the excess which I have displayed here.
Reading example: for the $500$ such values below $n=1500$, rounding down happens $102$ times more often than rounding up (i.e. $301$ times down versus $199$ times up).
While the excess seems essentially linear (red line, slope about $1/15$, thus $60$% rounding down and $40$% rounding up), the bumps and dents are quite irregular.
Not that this helps for the original question, but it gives more evidence for the fact that the sequences $A$ and $B$ are not that simple-looking as it may seem!