Define $A=(a\_n)$ and $B=(b\_n)$ by $b\_0=1$ and 


$$a\_n=b\_n+b\_{2n}$$


for $n \geq 0$, where $A$ and $B$ are increasing and every positive integer occurs exactly once in $A$ or $B$. Can someone prove that


$$b\_{3n+2}=4n+4$$


for $n \geq 0$? Initial terms:


$$A=(2,7,10,14,18,23,26,31,34,38,43,46,50,\ldots)$$
$$B=(1,3,4,5,6,8,9,11,12,13,15,16,17,19,20,\ldots).$$


This question resembles [Limit associated with complementary sequences](https://mathoverflow.net/questions/290220/limit-associated-with-complementary-sequences), but I don't see how the method of solution there applies here. The sequences $A$ and $B$ are <https://oeis.org/A304799> and <https://oeis.org/A304800>. 



Simple-looking sequences $A$ and $B$ defined by a complementary equation
THis can be shown by a bit less concrete estimates that in @Deld's answer.


**[EDIT]** Initially I thought $(b\_i)$ starts with $b\_1$, but it actually starts with $b\_0$. Here is a proof for the actual case; the previous answer is left below.


We show by induction on $n$ that 
$$
 4n+2\leq a\_n\leq 4n+3; \qquad(\*)
$$
while proving that, we show the required equality as well, together with $b\_{3n}=4n+1$. The base cases $n=0,1$ are trivial.


Assuming $(\*)$ for $n=0,1,2,\dots,k$, we first show 
$$
 \frac{4t+5}3\geq t+\left\lceil\frac{t}3\right\rceil+1\geq b\_t\geq t+\left\lfloor\frac{t+1}3\right\rfloor+1\geq \frac{4t+2}3
 \qquad(\*\*)
$$
for $2\leq t\leq 3k$. 


Set $s=\left\lceil\frac t3\right\rceil\in[0,k]$; then $a\_s\geq 4s+2$, so there are at least $3s+1$ values of $b$ in $[1,4s+1]$, and hence $b\_{3s}\leq 4s+1<a\_s$. This yields that there are at most $s$ values of $a$ in $[1,b\_{3s}]$; so, since $t\leq 3s$, we get $b\_t\leq (t+1)+s$, as desired.


Similarly, setting $p=\bigl\lfloor\frac{t+1}3\bigr\rfloor\in[1,k]$, we have $a\_{p-1}\leq 4p-1$, so $[1,4p]$ contains at most $3p$ values of $b$, and $b\_{3p-1}\geq 4p>a\_{p-1}$. Hence $[1,b\_{3p-1}]$ contains at least $p$ values of $a$; so, as $t\geq 3p-1$, we get $b\_t\geq (t+1)+p$. Thus $(\*\*)$ is proved. 


Moreover, we have shown that $b\_{3p-1}=4p$ for all $1\leq p\leq k$, as the estimates in $(\*\*)$ agree for $t=3p-1$. That is, we have showed the initially requested equality. Similarly, for $t=3p$ we get $b\_{3p}=4p+1$.


It remains to finish the step of induction, proving $(\*)$ for $n=k+1$. Indeed, by $(\*\*)$ we have
$$
 4(k+1)+\frac{10}3=\frac{4(k+1)+5}3+\frac{4(2k+2)+5}3\geq b\_{k+1}+b\_{2k+2}=a\_{k+1}\geq \frac{4(k+1)+2}3+\frac{4(2k+2)+2}3=4(k+1)+\frac43,
$$
which yields the required result, as $a\_{k+1}$ is integer. (Here we used that $k+1\geq 2$ and $2k+2\leq 3k$, i.e., that $k\geq 2$.)


**Remark.** The same method works equally well (or even better) for similar relations, e.g., $a\_n=b\_n+b\_{2n}+b\_{3n}$ etc. The linear term is found by asymptotical reasons; then the constants are found from the system of inequalities. In this case, even more residues in indices act good.




---


**[OLD ANSWER]** Here we assume that the first term in $(b\_i)$ is $b\_1$.


We show by induction on $n$ that 
$$
 4n-2\leq a\_n\leq 4n; \qquad(\*)
$$
while proving that, we show the required equality as well. The base cases $n=1,2$ are trivial.


Assuming $(\*)$ for $n=1,2,\dots,k$, we get
$$
 \frac{4t+1}3\geq t+\left\lceil\frac{t-1}3\right\rceil\geq b\_t\geq t+\left\lfloor\frac{t-1}3\right\rfloor\geq \frac{4t}3-1
 \qquad(\*\*)
$$
for $t\leq 3k$. Indeed, if $s=\left\lceil\frac{t-1}3\right\rceil\leq k-1$, then $a\_{s+1}\geq 4s+2$, so there are at least $3s+1$ values of $b$ in $[1,4s+1]$. This yields that there are at most $s$ values of $a$ in $[1,b\_{3s+1}]$; so, since $t\leq 3s+1$, we get $b\_t\leq t+s$, as desired.


Similarly, setting $p=\left\lfloor\frac{t-1}3\right\rfloor\leq k-1$, we have $a\_p\leq 4p$, so $[1,4p+1]$ contains at most $3p+1$ values of $b$. Hence $[1,b\_{3p+1}]$ contains at least $p$ values of $a$; so, as $t\geq 3p+1$, we get $b\_t\geq t+p$. Thus $(\*\*)$ is proved. Moreover, we have shown that $b\_{3p+1}=(3p+1)+p$ for all $p\leq k-1$, as the estimates in $(\*\*)$ agree for $t=3p+1$. That is, we have showed the initially requested equality.


It remains to finish the step of induction, proving $(\*)$ for $n=k+1$. Indeed, by $(\*\*)$ we have
$$
 4(k+1)+\frac23=\frac{4(k+1)+1}3+\frac{4(2k+2)+1}3\geq b\_{k+1}+b\_{2k+2}=a\_{k+1}\geq \frac{4(k+1)}3+\frac{4(2k+2)}3-2=4(k+1)-2,
$$
which yields the required result, as $a\_{k+1}$ is integer. (Here we used that $2k+2\leq 3k$, i.e., that $k\geq 2$.)


