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

Question

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, 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.

Answer 1

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$.)

Answer 2

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$.

Answer 3

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!

Answer 4

This is only an observation and not a solution, but perhaps it may save some time for anyone else who looks at this problem. So far as the sequences are given in OEIS, the following formulae (the second of which is given by the proposer) fit the data:

$$b_{3n} = 4n + 1$$ $$b_{3n+2} = 4n + 4$$ $$b_{9n+1} = 12n + 3$$ $$b_{18n+7} = 24n + 10$$ $$b_{27n + 4} = 36n + 6$$ $$b_{27n + 16} = 36n + 22.$$

If those formulae are correct, then the original condition that $a_n = b_n + b_{2n}$ would give determinations of $A$ in the following cases:

$$a_{3n} = 12n + 2$$ $$a_{9n+1} = 36n + 7$$ $$a_{18n+7} = 72n + 31$$ $$a_{27n+4} = 108n + 18$$ $$a_{27n+16} = 108n + 66.$$

(Formula for $a_{18n+7}$ corrected Aug 29 2019.)