Zeros in a sequence

inequalitysequence-of-functionsequences-and-series

Define the sequence $x_n$ by $x_1=0$ and
$$
x_n=x_{\lfloor n / 2\rfloor}+(-1)^{n(n+1) / 2}
$$
for $n \geq 2$. Find the number of $n \leq 2023$ such that $x_n=0$.

My approach was the following:

To find the number of values of $n \leq 2023$ for which $x_n = 0$, we can observe some patterns in the sequence and use it to our advantage.

Let's start by calculating the first few terms of the sequence:

$x_1 = 0$
$x_2 = x_1 + (-1)^{2(2+1)/2} = 0 + (-1)^3 = -1$
$x_3 = x_1 + (-1)^{3(3+1)/2} = 0 + (-1)^6 = 1$
$x_4 = x_2 + (-1)^{4(4+1)/2} = -1 + (-1)^{10} = -1 – 1 = -2$
$x_5 = x_2 + (-1)^{5(5+1)/2} = -1 + (-1)^{15} = -1 + 1 = 0$
$x_6 = x_3 + (-1)^{6(6+1)/2} = 1 + (-1)^{21} = 1 – 1 = 0$
$x_7 = x_3 + (-1)^{7(7+1)/2} = 1 + (-1)^{28} = 1 + 1 = 2$
$x_8 = x_4 + (-1)^{8(8+1)/2} = -2 + (-1)^{36} = -2 + 1 = -1$

From the above calculations, we can observe some patterns:

  1. $x_1 = 0$
  2. $x_2 = -1$
  3. $x_3 = 1$
  4. $x_4 = -2$
  5. $x_5 = x_6 = 0$
  6. $x_7 = 2$
  7. $x_8 = -1$

We can see that the sequence repeats itself in a pattern of length 6: $0, -1, 1, -2, 0, 0$. After these initial terms, the sequence becomes periodic.

Now, to find the number of values of $n \leq 2023$ for which $x_n = 0$, we can break it down as follows:

  1. The values of $x_1, x_2, x_3, x_4, x_5, x_6$ are fixed, and they are not equal to 0.
  2. For $n \geq 7$, the sequence becomes periodic with a period of 6. Therefore, for any $n$ such that $n \geq 7$, $x_n = x_{n \mod 6 + 7}$.

Now, let's calculate the values of $x_n$ for $n = 7, 8, 9, 10, 11, 12$:

$x_7 = x_1 + (-1)^{7(7+1)/2} = 0 + (-1)^{28} = 0 + 1 = 1$
$x_8 = x_2 + (-1)^{8(8+1)/2} = -1 + (-1)^{36} = -1 + 1 = 0$
$x_9 = x_3 + (-1)^{9(9+1)/2} = 1 + (-1)^{45} = 1 – 1 = 0$
$x_{10} = x_4 + (-1)^{10(10+1)/2} = -2 + (-1)^{55} = -2 – 1 = -3$
$x_{11} = x_5 + (-1)^{11(11+1)/2} = 0 + (-1)^{66} = 0 + 1 = 1$
$x_{12} = x_6 + (-1)^{12(12+1)/2} = 0 + (-1)^{78} = 0 + 1 = 1$

Now we see that $x_8, x_9, x_{11}, x_{12}$ are equal to 0.

So, every 6th value of $n$ starting from $n = 7$ will have $x_n = 0$, i.e., $n = 7, 13, 19, 25, \ldots$.

To find the number of such values of $n$ less than or equal to 2023, we can calculate the largest value of $n$ in this sequence that is less than or equal to 2023:

$$
7 + 6k \leq 2023
$$

Solving for $k$:

$$
6k \leq 2016
$$

$$
k \leq 336
$$

So, there are 336 values of $k$ that satisfy this inequality. Therefore, there are 336 values of $n$ such that $x_n = 0$ and $n \leq 2023$.

Best Answer

Let us pick some random number $n$ and see how to compute $x_n$ in this specific case. The computer gave me:

sage: import random; n = random.choice([1000..2023])
sage: n
1399

OK, we take $n=1399$ and write it in base two.

sage: n.digits(base=2)
[1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1]

This representation is "reversed", well $n$ is seven mod eight. So: $$ n = 10101110111_{\text{base two}}\ . $$ Now we inspect $n$ and the corresponding term. I will write $x(n)$ instead of $x_n$, since the music should not be minimalized in a sub index. We have $x(n)$ defined in terms of $x(m)$ with $m={[n/2]}$, and $m$ is obtained from $n$ by deleting the last binary digit. What about the contribution of $(-1)$ to the power $n(n+1)/2$? Well, we separate into cases. For $n$ with last digits:

  • $00_{\text{base two}}$ we have $n=0$ mod four, so $n(n+1)/2$ is even, $(-1)^{n(n+1)/2}=+1$,
  • $01_{\text{base two}}$ we have $n=1$ mod four, so $n(n+1)/2$ is odd, $(-1)^{n(n+1)/2}=-1$,
  • $10_{\text{base two}}$ we have $n=2$ mod four, so $n(n+1)/2$ is odd, $(-1)^{n(n+1)/2}=-1$,
  • $11_{\text{base two}}$ we have $n=3$ mod four, so $n(n+1)/2$ is even, $(-1)^{n(n+1)/2}=+1$.

It may be useful to define $s$ to be the above function of "two binary digits", so $s(00)=s(11)=+1$, $s(01)=s(10)=-1$. So $s$ is $+1$ for two equal digits, its contribution in the recursive computation of $x_n$ is $+1$ for two equal consecutive digits, and $-1$ for ... non equal consecutive digits. So: $$ \begin{aligned} &x(1399)\\ &=x\left(10101110111_{\text{base two}}\right)\\ &=x\left(1010111011_{\text{base two}}\right) + s(11)\\ &=x\left(101011101_{\text{base two}}\right) + s(11) + s(11)\\ &=x\left(10101110_{\text{base two}}\right) + s(01) + s(11) + s(11)\\ &=x\left(1010111_{\text{base two}}\right) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(101011_{\text{base two}}\right) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(10101_{\text{base two}}\right) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(1010_{\text{base two}}\right) + s(01) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(101_{\text{base two}}\right) + s(10) + s(01) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(10_{\text{base two}}\right) + s(01) + s(10) + s(01) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &= \underbrace{x\left(1_{\text{base two}}\right)}_{=0} + s(10) + s(01) + s(10) + s(01) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\ , \end{aligned} $$ So in essence, we write $n$ in base two, consider the result as a "word" in alphabet $0,1$, and count the number of

  • consecutive two letters which are equal,
  • consecutive two letters which are not equal,
    in this representation, take the difference of the counts, and check if it is zero.

Before we start solving the problem, let us check the receipt found for the first some numbers: $$ \begin{aligned} x(1) &= 0\ ,\\[2mm] x(2) &= x(10) = s(10) = 0-1=-1\ ,\\ x(3) &= x(11) = s(11) = 1-0=1\ ,\\[2mm] x(4) &= x(100) = s(10)+s(00) = 1-1=0\ ,\\ x(5) &= x(101) = s(10)+s(01) = 0-2=-2\ ,\\ x(6) &= x(110) = s(11) + s(10) =1-1=0\ ,\\ x(7) &= x(111) = s(11) + s(11) =2-0=2\ ,\\[2mm] x(8) &= x(1000) = s(10) + s(00) + s(00) =2-1=1\ ,\\ x(9) &= x(1001) = s(10) + s(00) + s(01) =1-2=-1\ ,\\ x(10) &= x(1010) = s(10) + s(01) + s(10) =0-3=-3\ ,\\ x(11) &= x(1011) = s(10) + s(01) + s(11) =1-2=-1\ ,\\ x(12) &= x(1100) = s(11) + s(10) + s(00) =2-1=1\ ,\\ x(13) &= x(1101) = s(11) + s(10) + s(01) =1-2=-1\ ,\\ x(14) &= x(1110) = s(11) + s(11) + s(10) =2-1=1\ ,\\ x(15) &= x(1111) = s(11) + s(11) + s(11) =3-0=3\ ,\\[2mm] x(16) &= x(10000) = s(10) + s(00) + s(00) + s(00) =3-1=2\ ,\\ x(17) &= x(10001) = s(10) + s(00) + s(00) + s(01) =2-2=0\ ,\\ x(18) &= x(10010) = s(10) + s(00) + s(01) + s(10) =1-3=-2\ ,\\ x(19) &= x(10011) = s(10) + s(00) + s(01) + s(11) =2-2=0\ ,\\ x(20) &= x(10100) = s(10) + s(01) + s(10) + s(00) =1-3=-2\ ,\\ x(21) &= x(10101) = s(10) + s(01) + s(10) + s(01) =0-4=-4\ , \end{aligned} $$ and so on. We can draw some conclusions. If the number of the $s$-terms is odd, we cannot get the difference result zero. So there are no $n$ values with $x(n)=0$ for $n$ in the ranges:

  • $n$ between $2=2^1$ and $3=2^2-1$,
  • $n$ between $8=2^3$ and $15=2^4-1$,
  • $n$ between $32=2^5$ and $63=2^6-1$,
  • $n$ between $128=2^7$ and $255=2^8-1$,
  • $n$ between $512=2^9$ and $1023=2^{10}-1$,
  • $n$ between $2048=2^{11}$ and $4095=2^{12}-1$, and so on.

Now we are ready to start. I will call simply a pair a "subword" of length two in the (word of the) binary representation of a number. We count the $n$'s with equal pairs of the shape $AA$, and of the shape $AB$, $A\ne B$. Such an $n$ has an even number of pairs. Thus an odd number of digits, call it $d$. The first digit is one. We follow the word from the next place, the "second place" to the "last place" in its writing. We mark with a star the positions in the word where the second letter in the pair coincides with the first one. The other are not marked, so there is a blank - and if we want to still mark somehow the place, there will be a small dot. The first position remains unmarked. In case of $x(n)=0$ we have an equal number of blanks and stars. We count these words. Looking at only the positions of the stars we obtain a subset of the index set $(d-1),\dots,3,2,1,0$. Conversely, if such a subset is given, we can complete $n$ in a unique manner, so that the stars associated to $n$ are in the given position.

Example:

Consider the numbers $n$ between $256=2^8$ and $511=2^9-1$. Each of them needs $d=$nine digits. The first digit is $a_8=$one. So $n$ is written like: $$ \overline{1a_7a_6a_5a_4a_3a_2a_1a_0}_{\text{base two}}=2^8+a_7\cdot 2^7+\dots+a_1\cdot 2+a_0\ .$$ Fix some subset with four elements in the index set $\{7,6,5,4,3,2,1,0\}$. For instance $7,4,3,1$. Then $7$ is a star place, so $a_7=a_8=1$. And $6$ is not a star place, so $a_6\ne a_7=1$, so $a_6=0$. And $a_5\ne a_6$, so $a_5=1$. And $4$ is on a star place, so $a_4=a_5=1$. Then $3$ is also on a star place, so $a_3=a_4=1$. And $a_2\ne a_3$, so $a_2=0$. And $1$ is on a star place, so $a_1=a_2=0$. Finally $a_0\ne a_1$, so $a_0=1$.

In a picture:

110111001
 *  ** *

How many such "good" numbers are thus in the range from $256$ to $511$? Exactly $\binom84=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}=7\cdot 2\cdot 5=70$.

Which are explicitly the "good" numbers with $d=5$ digits? We search for star patterns on the relevant last four places. Blanks are dots. Here they are:

..** 10111 = 23
.*.* 10011 = 19
*..* 11011 = 27
.**. 10001 = 17
*.*. 11001 = 25
**.. 11101 = 29

How many such good numbers are between one and $2048$? Exactly: $$ \underbrace{\binom00}_{1} + \underbrace{\binom21}_{4,6} + \underbrace{\binom42}_{17,19,23,25,27,29} + \underbrace{\binom63}_{68,\dots,122} + \underbrace{\binom84}_{261,\dots,501} + \underbrace{\binom{10}5}_{1034,\dots,2026} \ . $$

For some reasons, the problems wants us to stop at $2023$, so we miss exactly one "good" number, the greatest one. This greatest one is obtained by insisting to start with "ones" (as digits)

1|11111|?????|
  *****

so the five stars are consumed, we need only blanks/dots after, and the number is

1|11111|01010| = 1 11111 11111 - 10101 = 2047 - (16+4+1) = 2026 .
  ***** .....

(The numbers $2024$ and $2025$ also have the pattern $1\ 11111\ ?????$ but introduce in the last five digits further equal pairs. So we miss only the $2026$ when we stop at $2023$.)

So the answer to the problem is: $$ \bbox[yellow]{\qquad \binom 00 + \binom 21 + \binom 42 + \binom 63 + \binom 84 + \binom {10}5 - 1 \\ = 1+2+6+20+70+252-1 = 350\ .\qquad} $$

Related Question