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?


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

  • $\begingroup$ 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. $\endgroup$
    – Aeryk
    Oct 1 '19 at 17:42
  • $\begingroup$ @Aeryk, shouldn't it be $B_c(n)$ instead of $b_n$ in your equation? $\endgroup$
    – René Gy
    Oct 1 '19 at 18:06
  • $\begingroup$ I don't see how $B_c$ depends on $c$ at all... $\endgroup$
    – Aeryk
    Oct 1 '19 at 18:52

The same method as in this answer to a previous your question works as well.

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

The required conclusion follows.

In fact, that conclusion could be also derived directly from $(**_0)$ and $(**_1)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.