# Difference of two integer sequences: all zeros and ones?

Suppose that $$c$$ is a nonnegative integer and $$A_c = (a_n)$$ and $$B_c = (b_n)$$ are strictly increasing complementary sequences satisfying

$$a_n = b_{2n} + b_{4n} + c,$$

where $$b_0 = 1.$$ Can someone prove that the sequence $$A_1-A_0$$ consists entirely of zeros and ones?

Notes:

$$A_0 = (2, 10, 17, 23, 31, 38, 44, 52, 59, 65, 73, 80, 86, \ldots ) \\ A_1 = (3, 11, 17, 24, 31, 39, 45, 53, 59, 66, 74, 80, 87, \ldots )$$

The sequence $$A_0$$ satisfies the linear recurrence $$a_n = a_{n-1} + a_{n-3} - a_{n-4}$$.

It may help to watch $$A_1$$ get started. Since $$b_0=1$$ we have $$a_0=1+1+1=3$$, and since $$A_1$$ and $$B_1$$ are complementary, we have $$b_1=2$$. Next, $$a_1=b_2+b_2+1 \geq 4+6+1=11$$, so that $$b_2=4, b_3=5,\ldots,b_8=10$$, and $$a_1=11$$. Then $$a_2=b_4+b_8+1 \geq 17$$, and so on.

• I feel like something's not right in this question. It seems that by definition $A_1(n)-A_0(n) = (b_{2n}+b_{4n}+1)-(b_{2n}+b_{4n}+0) = 1$. Yet this does not agree with the initial values of $A_0$ and $A_1$. So either I'm missing something or maybe there's been a typo. – Aeryk Oct 1 '19 at 17:42
• @Aeryk, shouldn't it be $B_c(n)$ instead of $b_n$ in your equation? – René Gy Oct 1 '19 at 18:06
• I don't see how $B_c$ depends on $c$ at all... – Aeryk Oct 1 '19 at 18:52

As for $$(A_0)$$. Starting with a guess $$7n+2\leq a_n\leq 7n+3,$$ and trying to prove it inductionally, we arrive at $$b_{6n+2}\geq 7n+4$$ and $$b_{6n}\leq 7n+1$$, hence $$t+\left\lfloor\frac{t+4}6\right\rfloor+1\leq b_t\leq t+\left\lceil\frac t6\right\rceil+1, \qquad(**_0)$$ which agree for all $$t=6k+2,\dots,6k+6$$. So for all even $$t$$ we have $$b_t=t+\lceil t/6\rceil+1$$, which yields even an exact formula for $$a_n$$: $$a_n=7n+\begin{cases}2,& n\mod 3=0; \\ 3,& n\mod 3\neq 0.\end{cases}$$
As for $$(A_1)$$. Starting with a guess $$7n+3\leq a_n\leq 7n+4,$$ and trying to prove it inductionally, we arrive at $$b_{6n+3}\geq 7n+5$$ and $$b_{6n+1}\leq 7n+2$$, hence $$t+\left\lfloor\frac{t+3}6\right\rfloor+1\leq b_t\leq t+\left\lceil\frac{t-1}6\right\rceil+1, \qquad(**_1)$$ which agree for all $$t=6k+3,\dots,6k+7$$. So we have $$b_t=t+\lceil (t-1)/6\rceil+1$$, except for $$7k+3\leq b_{6k+2}\leq 7k+4$$. This yields that $$a_n=7n+\begin{cases}3,& n\mod 3=0; \\ 3\text{ or }4,& n\mod 3\neq 0.\end{cases}$$
In fact, that conclusion could be also derived directly from $$(**_0)$$ and $$(**_1)$$.