4
$\begingroup$

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.

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

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .