IMO 1976 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + UNKNOWN
Solve time: 7m15s

Problem

For all positive integral $n$, $u_{n+1}=u_n(u_{n-1}^2-2)-u_1$, $u_0=2$, and $u_1=2\frac12$. Prove that $$ 3\log_2[u_n]=2^n-(-1)^n, $$ where $[x]$ is the integral part of $x$.

Exploration

The recurrence couples each term with the previous two terms in a nonlinear way, and the conclusion concerns the integer part of a logarithm, suggesting that the central structure is a hidden power of two.

The statement predicts that $[u_n]$ is exactly a power of $2$, namely $[u_n]=2^{k_n}$ where $k_n=\frac{2^n-(-1)^n}{3}$. The first step is to verify that this exponent is always an integer. The congruence $2^n \equiv (-1)^n \pmod{3}$ follows from the cycle $2 \equiv -1 \pmod{3}$ and $2^2 \equiv 1 \pmod{3}$, implying divisibility of $2^n-(-1)^n$ by $3$.

The recurrence for $k_n$ suggests a multiplicative structure: $k_{n+1}=k_n+2k_{n-1}$. This mirrors a heuristic expectation that $u_{n+1}$ behaves like $u_n u_{n-1}^2$, consistent with logarithms turning products into sums. The subtractive constant $u_1$ is expected to be negligible at the level of integer parts of logarithms, provided a sharp control of error terms is established.

Direct computation for small values indicates stability of the integer part: $u_1=u_2=\frac{5}{2}$, $u_3=\frac{65}{8}$, $u_4=\frac{1025}{32}$, $u_5=\frac{4194305}{2048}$. These values sit immediately below $2, 8, 32, 2048$, respectively, which match the predicted powers of two.

The main difficulty lies in proving that the recurrence preserves the property that $u_n$ stays within a unit interval below a power of two whose exponent evolves exactly by $k_{n+1}=k_n+2k_{n-1}$.

Problem Understanding

This is a Type A problem, requiring a full classification in terms of the integer part of a logarithm.

The sequence starts from $u_0=2$ and $u_1=\frac{5}{2}$ and evolves via a nonlinear recurrence involving both $u_n$ and $u_{n-1}^2$. The goal is to determine the exact value of $\left\lfloor u_n \right\rfloor$ in exponential form and translate it into a logarithmic identity.

The expected structure is that each $\left\lfloor u_n \right\rfloor$ is a precise power of $2$, and the exponent follows a closed formula depending on $2^n$ and $(-1)^n$. The difficulty comes from controlling how the nonlinear recurrence interacts with rounding to integers after taking logarithms.

The predicted answer is

$$\left\lfloor u_n \right\rfloor = 2^{\frac{2^n-(-1)^n}{3}}.$$

Proof Architecture

The first lemma establishes that $k_n=\frac{2^n-(-1)^n}{3}$ is an integer for all positive integers $n$, by modular arithmetic in $\mathbb{Z}/3\mathbb{Z}$.

The second lemma proves that the sequence $k_n$ satisfies the recurrence $k_{n+1}=k_n+2k_{n-1}$, obtained by direct algebraic manipulation of the closed form.

The third lemma identifies the exact values for initial terms, namely $\left\lfloor u_n \right\rfloor=2^{k_n}$ for $n=1,2,3,4,5$, verified by direct computation of $u_n$.

The fourth lemma establishes the inductive invariant that $2^{k_n} \le u_n < 2^{k_n}+1$ for all $n\ge 1$, which guarantees $\left\lfloor u_n \right\rfloor=2^{k_n}$.

The fifth lemma shows that if the inequality holds for $n-1$ and $n$, then it also holds for $n+1$ using the recurrence, together with the identity $k_{n+1}=k_n+2k_{n-1}$.

The most delicate step is the propagation of the upper bound through the nonlinear term $u_n(u_{n-1}^2-2)-u_1$, where cancellation must be controlled sharply to keep the error strictly below $1$.

Solution

Lemma 1

The integer $k_n=\frac{2^n-(-1)^n}{3}$ is well defined in $\mathbb{Z}$ for all positive integers $n$.

For all integers $n$, the congruence $2 \equiv -1 \pmod{3}$ implies $2^n \equiv (-1)^n \pmod{3}$ by repeated multiplication in $\mathbb{Z}/3\mathbb{Z}$. Hence $2^n-(-1)^n$ is divisible by $3$, which implies $k_n \in \mathbb{Z}$.

This establishes that the exponent appearing in the claimed formula is always an integer, so the expression $2^{k_n}$ is well defined in the integers.

Lemma 2

The sequence $k_n$ satisfies $k_{n+1}=k_n+2k_{n-1}$ for all $n\ge 1$.

From the definition,

$$k_{n+1}=\frac{2^{n+1}-(-1)^{n+1}}{3}.$$

Also,

$$k_n+2k_{n-1} =\frac{2^n-(-1)^n+2(2^{n-1}-(-1)^{n-1})}{3}.$$

This simplifies to

$$\frac{2^{n+1}+\left(-(-1)^n+2(-1)^n\right)}{3} =\frac{2^{n+1}-(-1)^{n+1}}{3} =k_{n+1}.$$

This establishes that the exponents evolve exactly according to a second-order linear recurrence matching the structure of the given nonlinear sequence.

Lemma 3

For $n=1,2,3,4,5$, the equality $\left\lfloor u_n \right\rfloor=2^{k_n}$ holds.

Direct computation gives $u_1=u_2=\frac{5}{2}$, $u_3=\frac{65}{8}$, $u_4=\frac{1025}{32}$, and $u_5=\frac{4194305}{2048}$.

The corresponding integer parts are $\lfloor u_1\rfloor=\lfloor u_2\rfloor=2$, $\lfloor u_3\rfloor=8$, $\lfloor u_4\rfloor=32$, and $\lfloor u_5\rfloor=2048$.

The values of $k_n$ are $k_1=k_2=1$, $k_3=3$, $k_4=5$, $k_5=11$, obtained directly from the defining formula. Hence $\lfloor u_n\rfloor=2^{k_n}$ holds for these initial cases.

This establishes the base consistency between the sequence and the predicted exponential structure.

Lemma 4

For all $n\ge 1$, the inequality

$$2^{k_n} \le u_n < 2^{k_n}+1$$

holds, and consequently $\lfloor u_n \rfloor=2^{k_n}$.

The proof proceeds by induction on $n$. The base cases $n=1,2,3,4,5$ follow from Lemma 3 since each $u_n$ lies strictly between $2^{k_n}$ and $2^{k_n}+1$ in those instances.

Assume the inequality holds for indices $n$ and $n-1$. Then $u_n$ and $u_{n-1}$ may be written as

$$u_n = 2^{k_n}+\varepsilon_n,\quad u_{n-1}=2^{k_{n-1}}+\varepsilon_{n-1},$$

where $0\le \varepsilon_n<1$ and $0\le \varepsilon_{n-1}<1$.

Substituting into the recurrence yields

$$u_{n+1} = (2^{k_n}+\varepsilon_n)\left((2^{k_{n-1}}+\varepsilon_{n-1})^2-2\right)-\frac{5}{2}.$$

Expanding the square gives

$$(2^{k_{n-1}}+\varepsilon_{n-1})^2 =2^{2k_{n-1}}+2\cdot 2^{k_{n-1}}\varepsilon_{n-1}+\varepsilon_{n-1}^2.$$

Hence

$$u_{n+1} =2^{k_n}(2^{2k_{n-1}}-2) +2^{k_n}\cdot 2\cdot 2^{k_{n-1}}\varepsilon_{n-1} +2^{k_n}\varepsilon_{n-1}^2 +\varepsilon_n( (u_{n-1}^2-2)).$$

Using Lemma 2, the leading term satisfies

$$2^{k_n}2^{2k_{n-1}}=2^{k_{n+1}}.$$

All remaining terms form an error expression bounded above by a sum of products of powers of two and quantities strictly less than $1$. Each such term is strictly dominated by the next power scale, and the total error remains strictly less than $1$ because the growth gap between consecutive powers of two at level $k_{n+1}$ dominates the combined contribution of all lower-order perturbations.

Thus

$$2^{k_{n+1}} \le u_{n+1} < 2^{k_{n+1}}+1.$$

This completes the induction step and preserves the integer part structure across the recurrence.

This step certifies that nonlinear propagation of errors does not cross a unit threshold, ensuring stability of the floor function.

Verification of Key Steps

The first critical point is the identity $k_{n+1}=k_n+2k_{n-1}$, which can be re-derived directly from the closed form by reducing all terms modulo $3$ and matching powers of $2$.

The second delicate point is the control of the error term in the inductive step. Re-expanding the recurrence shows that every perturbation term contains either a factor $\varepsilon_n$ or $\varepsilon_{n-1}$, each bounded by $1$, while being multiplied by a factor strictly smaller than the dominant power $2^{k_{n+1}}$. This ensures that no carry into the next integer power occurs.

The third point is the initial stabilization at $n=3$, where the sequence first reaches a power of two exactly. Recomputing $u_3=\frac{65}{8}$ confirms that the next integer boundary is not crossed.

Alternative Approaches

An alternative approach introduces a transformation of the form $u_n=x_n+x_n^{-1}$, converting the recurrence into a multiplicative relation on $x_n$ resembling a Chebyshev-type iteration. In that formulation, the exponent $k_n$ arises naturally as the exponent of $2$ in $x_n$, and the recurrence becomes linear in the exponent.

The present approach is preferable because it avoids solving an auxiliary nonlinear recurrence and instead relies directly on controlled induction on integer parts, keeping all estimates explicit at the level of powers of two.