Kvant Math Problem 943

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m47s
Source on kvant.digital

Problem

The sequence $a_1$, $a_2$, $\ldots$ is defined by the rules: $a_{2n}=a_n$ for $n\ge 1$ and $a_{4n+1}=1$, $a_{4n+3}=0$ for $n\ge 0$. Prove that this sequence is not periodic.

Yu. V. Nesterenko

All-Union Mathematical Olympiad (1985)

Exploration

Let us compute the first terms. Since $a_{2n}=a_n$, every term is eventually reduced by repeatedly dividing its index by $2$ until an odd index remains. For odd indices we have

$$a_{4m+1}=1,\qquad a_{4m+3}=0.$$

Hence

$$a_1=1,\ a_2=1,\ a_3=0,\ a_4=1,\ a_5=1,\ a_6=0,\ a_7=0,\ a_8=1,$$

and continuing,

$$1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,1,\ldots$$

The value of $a_n$ is determined by the odd part of $n$. If

$$n=2^k m,\qquad m\ \text{odd},$$

then $a_n=a_m$, and for odd $m$ the value equals $1$ when $m\equiv1\pmod4$ and equals $0$ when $m\equiv3\pmod4$.

Thus $a_n$ depends only on the residue modulo $4$ of the odd part of $n$.

To prove nonperiodicity, suppose a period $T$ exists. Since dividing by powers of $2$ plays a central role, it is natural to compare indices whose difference is $T$ and whose $2$-adic divisibility is very different.

Take $2^r>T$. Then

$$a_{2^r}=a_1=1.$$

If $T$ is even, then $2^r+T$ has the same odd part as $T$, so its value is independent of $r$. This suggests reducing the period repeatedly by factors of $2$.

The crucial point is to show that any period must be divisible by arbitrarily large powers of $2$, which is impossible for a fixed positive integer.

Problem Understanding

We are given a sequence defined recursively by

$$a_{2n}=a_n,$$

together with

$$a_{4n+1}=1,\qquad a_{4n+3}=0.$$

We must prove that the sequence is not periodic.

This is a Type B problem. The task is to prove a stated property.

The core difficulty is that the sequence is defined recursively through powers of $2$. A hypothetical period must be compatible with this recursive structure. The strategy is to assume a period exists and show that the period must be divisible by $2,4,8,\ldots$, hence by arbitrarily large powers of $2$.

Proof Architecture

First lemma: if $T$ is a period of the sequence, then $T$ is even. The idea is to compare $a_{2^r}$ and $a_{2^r+T}$ for $2^r>T$.

Second lemma: if $T$ is an even period, then $T/2$ is also a period. The idea is to use the identity $a_{2n}=a_n$ and periodicity.

Third lemma: every period is divisible by every power of $2$. Apply the second lemma repeatedly and combine with the first lemma.

The hardest direction is the second lemma, because one must show carefully that periodicity of $T$ implies periodicity of $T/2$.

The lemma most likely to fail under scrutiny is the second one; every index manipulation must be justified directly from the defining recurrence.

Solution

Assume, for contradiction, that the sequence is periodic. Let $T>0$ be a period, so that

$$a_{n+T}=a_n$$

for all $n\ge1$.

We first prove that $T$ must be even.

Choose $r$ such that $2^r>T$. Since

$$a_{2^r}=a_1=1,$$

periodicity gives

$$a_{2^r+T}=1.$$

Suppose that $T$ is odd. Then $2^r+T$ is odd. Because $2^r\equiv0\pmod4$ for $r\ge2$,

$$2^r+T\equiv T\pmod4.$$

Hence the value of $a_{2^r+T}$ is determined by the residue class of $T$ modulo $4$.

If $T\equiv1\pmod4$, then for every sufficiently large $r$,

$$a_{2^r+T}=1.$$

Now consider $2^r+2T$. This number is odd and

$$2^r+2T\equiv3\pmod4,$$

because $2T\equiv2\pmod4$. Therefore

$$a_{2^r+2T}=0.$$

But periodicity yields

$$a_{2^r+2T}=a_{2^r+T}=1,$$

a contradiction.

If $T\equiv3\pmod4$, then

$$a_{2^r+T}=0,$$

while periodicity and $a_{2^r}=1$ give

$$a_{2^r+T}=1,$$

again a contradiction.

Both odd congruence classes lead to contradictions. Hence $T$ is even.

Write

$$T=2S.$$

We now show that $S$ is also a period.

For every $n\ge1$,

$$a_{n+S} =a_{2(n+S)} =a_{2n+2S} =a_{2n+T}.$$

Since $T$ is a period,

$$a_{2n+T}=a_{2n}.$$

Using the defining relation once more,

$$a_{2n}=a_n.$$

Combining these equalities,

$$a_{n+S}=a_n$$

for all $n\ge1$. Thus $S=T/2$ is a period.

We have proved two facts:

$$T\ \text{period} \implies T\ \text{even},$$

and

$$T\ \text{period} \implies T/2\ \text{period}.$$

Starting from the period $T$, repeated application of the second fact shows that

$$\frac{T}{2},\ \frac{T}{2^2},\ \frac{T}{2^3},\ldots$$

are all periods as long as they are integers. Since every period is even by the first fact, each of these integers must itself be even. Consequently $T$ is divisible by $2^k$ for every positive integer $k$.

No positive integer has this property. The contradiction shows that no period exists.

Thus the sequence is not periodic.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is proving that an odd period is impossible. For $2^r>T$, the index $2^r$ has value $1$. If $T\equiv3\pmod4$, then $2^r+T$ is an odd number congruent to $3$ modulo $4$, hence its value is $0$, contradicting periodicity immediately.

If $T\equiv1\pmod4$, periodicity forces $a_{2^r+T}=1$. The number $2^r+2T$ is odd and congruent to $3$ modulo $4$, so its value is $0$. Since $(2^r+2T)-(2^r+T)=T$, periodicity would require these values to be equal. This contradiction is independent of the choice of large $r$.

The second delicate step is proving that $T/2$ is a period. Starting from

$$a_{n+T/2},$$

one cannot apply periodicity directly. The recurrence must be used first:

$$a_{n+T/2}=a_{2n+T}.$$

This follows from

$$a_{2m}=a_m$$

with $m=n+T/2$. Then periodicity gives

$$a_{2n+T}=a_{2n},$$

and another application of the recurrence yields

$$a_{2n}=a_n.$$

The chain is complete and valid for every $n$.

The final step is the infinite divisibility argument. If $T$ were divisible only by $2^m$, then $T/2^m$ would be an odd positive integer. Repeated application of the period-halving lemma shows that $T/2^m$ is a period, but the first lemma says every period is even. This contradiction confirms that no period exists.

Alternative Approaches

The sequence can be described explicitly. Write

$$n=2^\nu m,$$

where $m$ is odd. Then

$$a_n= \begin{cases} 1,& m\equiv1\pmod4,\ 0,& m\equiv3\pmod4. \end{cases}$$

Equivalently,

$$a_n=\frac{1+\chi(m)}2,$$

where $\chi$ is the nontrivial character modulo $4$.

Assuming a period $T$, one may choose $r$ with $2^r>T$ and compare the odd parts of $2^r$ and $2^r+T$. The odd part of $2^r$ is $1$, whereas the odd part of $2^r+T$ is determined by the odd part of $T$. This leads directly to the conclusion that $T$ must be even. Repeating the argument for $T/2$ yields the same infinite divisibility contradiction. The main proof is preferable because it isolates a simple structural lemma, namely that every even period can be halved, and then derives the contradiction in a very short and transparent way.