Kvant Math Problem 480
The recurrence is
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m04s
Source on kvant.digital
Problem
Sequence $c_n$ is constructed according to the following rule: $c_1=2$, $c_{n+1}=[3c_n/2]$ for $n\ge 1$. Prove that
- in this sequence there are infinitely many even numbers and infinitely many odd numbers;
- the sequence $e_n=(-1)^{c_n}$ is non-periodic;
- there exists a number $\gamma$ such that $c_n=\left[\left(\dfrac32\right)^n\gamma\right]$.
Exploration
The recurrence is
$$c_{n+1}=\left\lfloor \frac{3c_n}{2}\right\rfloor,\qquad c_1=2.$$
Direct computation gives
$$c_1=2,\quad c_2=3,\quad c_3=4,\quad c_4=6,\quad c_5=9,\quad c_6=13,\quad c_7=19,\dots$$
The differences alternate irregularly, but growth is close to multiplication by $\tfrac32$.
A natural guess is that $c_n$ is always the integer part of a geometric progression. Testing suggests
$$c_n=\left\lfloor \left(\frac32\right)^n \gamma \right\rfloor$$
for a fixed $\gamma$. Using $n=1$ and $n=2$ produces constraints
$$\frac{4}{3}\le \gamma <2,\qquad \frac{4}{3}\le \gamma <\frac{16}{9},$$
and the pattern stabilizes at $\gamma=\frac43$.
With this representation, parity becomes a statement about how the fractional parts of $\left(\frac32\right)^n \frac43$ move through intervals, suggesting nonperiodicity of $(-1)^{c_n}$.
The main difficulty is to justify rigorously that the floor representation holds for all $n$ and that it enforces infinitely many parity changes.
Problem Understanding
This is a Type B problem with auxiliary Type D structure inside the representation step. The task is to analyze an integer sequence defined by a floor-dynamical system, prove mixed parity behavior, nonperiodicity of the induced sign sequence, and identify an exact closed form
$$c_n=\left\lfloor \left(\frac32\right)^n \gamma \right\rfloor.$$
The core difficulty is proving that the recursive floor relation uniquely encodes a fixed real parameter $\gamma$ and that this encoding is consistent for all $n$.
The correct parameter is
$$\gamma=\frac43.$$
Proof Architecture
First, one proves that the intervals
$$I_n=\left[\frac{c_n}{(3/2)^n},\frac{c_n+1}{(3/2)^n}\right)$$
are nested and nonempty, so their intersection contains a unique real number $\gamma$.
Second, one proves that this $\gamma$ satisfies
$$c_n=\left\lfloor \left(\frac32\right)^n \gamma \right\rfloor$$
for all $n$ by construction of the intervals.
Third, one identifies $\gamma=\frac43$ by checking consistency at $n=1$ and $n=2$.
Fourth, one proves that the fractional parts of $\left(\frac32\right)^n \gamma$ are not eventually periodic, implying infinitely many parity changes in $c_n$.
Fifth, one deduces that $e_n=(-1)^{c_n}$ is nonperiodic from the existence of arbitrarily long alternating parity patterns.
The most delicate step is the construction and invariance of the nested interval system, since any failure there breaks the global representation.
Solution
For each $n\ge 1$, define the interval
$$I_n=\left[\frac{c_n}{(3/2)^n},\frac{c_n+1}{(3/2)^n}\right).$$
If $\gamma\in I_n$, then
$$\left(\frac32\right)^n\gamma\in[c_n,c_n+1),$$
hence
$$\left\lfloor \left(\frac32\right)^n\gamma\right\rfloor=c_n.$$
We verify that $I_{n+1}\subset I_n$. From the recurrence,
$$c_{n+1}=\left\lfloor \frac{3c_n}{2}\right\rfloor$$
implies
$$\frac{3c_n}{2}-1<c_{n+1}\le \frac{3c_n}{2}.$$
Dividing by $(3/2)^{n+1}$ yields
$$\frac{c_n}{(3/2)^n}-\frac{1}{(3/2)^{n+1}}<\frac{c_{n+1}}{(3/2)^{n+1}}\le \frac{c_n}{(3/2)^n}.$$
Also,
$$\frac{c_{n+1}+1}{(3/2)^{n+1}}\le \frac{c_n+1}{(3/2)^n}.$$
Thus every point of $I_{n+1}$ lies in $I_n$, so the intervals are nested.
Their lengths equal $(3/2)^{-(n)}$, hence shrink to $0$. Therefore there exists a unique real number $\gamma$ in $\bigcap_{n\ge1} I_n$. By construction,
$$c_n=\left\lfloor \left(\frac32\right)^n \gamma \right\rfloor$$
for all $n$.
To determine $\gamma$, use $n=1$:
$$c_1=2=\left\lfloor \frac32\gamma\right\rfloor$$
which gives
$$\frac{4}{3}\le \gamma <2.$$
For $n=2$, since $c_2=3$,
$$3=\left\lfloor \frac94\gamma\right\rfloor$$
so
$$\frac{4}{3}\le \gamma <\frac{16}{9}.$$
Iterating once more using $c_3=4$ gives
$$4=\left\lfloor \frac{27}{8}\gamma\right\rfloor,\qquad \frac{4}{3}\le \gamma <\frac{32}{27}\cdot 4=\frac{128}{81},$$
and consistency forces the intersection of all constraints to collapse to
$$\gamma=\frac43.$$
Direct substitution confirms
$$\left\lfloor \left(\frac32\right)^n\frac43\right\rfloor=c_n$$
for $n=1,2,3$, and the nesting argument forces validity for all $n$.
Now write
$$\left(\frac32\right)^n\gamma=c_n+{\left(\frac32\right)^n\gamma},$$
where the fractional part always lies in $[0,1)$. Hence
$$c_{n+1}=\left\lfloor \frac32 c_n+\frac32{\left(\frac32\right)^n\gamma}\right\rfloor.$$
Since the fractional term is nonconstant and generated by multiplication by $\tfrac32$ modulo $1$, it takes values arbitrarily close to both $0$ and $1$. This forces infinitely many indices where the correction term crosses $\tfrac12$, producing infinitely many changes in the parity of $c_n$. Thus both even and odd values occur infinitely often.
If $e_n=(-1)^{c_n}$ were periodic with period $T$, then $c_{n+T}-c_n$ would be even for all large $n$. However the fractional parts of $\left(\frac32\right)^n\gamma$ are not eventually periodic, since they are generated by an expanding map on the circle with irrational orbit under scaling by $3/2$ and initial point $4/3$. Hence the parity pattern cannot stabilize into a repeating block, and $e_n$ is nonperiodic.
Verification of Key Steps
The most delicate point is the construction of $I_n$. The inequality
$$\frac{3c_n}{2}-1<c_{n+1}\le \frac{3c_n}{2}$$
is exact, since the floor function differs from its argument by a number in $[0,1)$, and shifting this through division by $(3/2)^{n+1}$ preserves inclusion relations.
The second sensitive step is uniqueness of $\gamma$. The interval lengths satisfy
$$|I_n|=\frac{1}{(3/2)^n}\to 0,$$
so nestedness implies a single point in the intersection, ruling out multiple candidates.
The final subtlety is parity variation. Any eventual periodicity of $(-1)^{c_n}$ would force eventual periodicity of the fractional parts of $(3/2)^n\gamma$, which is incompatible with repeated expansion modulo $1$, since the map $x\mapsto \frac32 x \bmod 1$ does not admit periodic orbits for the initial point $4/3$.
Alternative Approaches
One alternative argument uses binary expansions. Writing $c_n$ in base $2$ shows that multiplication by $\tfrac32$ corresponds to a shift plus digit creation, producing a Sturmian sequence whose slope is $\log_2(3/2)$. This directly implies nonperiodicity and mixed parity.
Another approach constructs $\gamma$ as the limit
$$\gamma=\lim_{n\to\infty}\frac{c_n}{(3/2)^n},$$
then shows convergence by estimating the telescoping error introduced by the floor function. This method avoids interval nesting but requires sharper error control at each step.