IMO 1976 Problem 6
The recurrence is
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 44m41s
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 is
$$u_{n+1}=u_n(u_{n-1}^2-2)-u_1,$$
with
$$u_0=2,\qquad u_1=2\frac12=\frac52.$$
The target identity is
$$3\lfloor u_n\rfloor =2^n-(-1)^n.$$
The first task is to compute several terms exactly.
For $n=1$,
$$u_2=u_1(u_0^2-2)-u_1 =\frac52(4-2)-\frac52 =\frac52.$$
Thus
$$3\lfloor u_2\rfloor =3\cdot2=6,$$
while
$$2^2-(-1)^2=4-1=3.$$
The formula fails. The statement must therefore contain a typographical error.
The classical form of this problem is
$$3\lfloor u_n\rfloor =2^{2^n}-(-1)^n.$$
Testing this corrected identity gives:
$$3\lfloor u_0\rfloor =6,\qquad 2^{2^0}-(-1)^0=2-1=1,$$
so the indexing probably begins at $n\ge1$.
Now compute further terms:
$$u_1=\frac52,\qquad u_2=\frac52,$$
and
\begin{align*}
u_3
&=u_2(u_1^2-2)-u_1 \
&=\frac52\left(\frac{25}4-2\right)-\frac52 \
&=\frac52\cdot\frac{17}4-\frac52 \
&=\frac{85}8-\frac{20}8 \
&=\frac{65}8=8+\frac18.
\end{align*}
Hence
$$3\lfloor u_3\rfloor =24,$$
and
$$2^{2^3}-(-1)^3=256+1=257,$$
still impossible. Another mismatch appears.
Trying instead
$$3u_n=2^{2^{n-1}}+(-1)^n$$
gives
$$3u_1=\frac{15}2,$$
again false.
The recurrence resembles the identity
$$x^3-3x=2\cos 3\theta \quad\text{when}\quad x=2\cos\theta.$$
A recurrence involving $u_{n+1}=u_n^2-2$ would naturally generate powers $2^{2^n}$. Here the mixed term $u_n(u_{n-1}^2-2)$ suggests that a hidden linearization may exist after scaling.
Set
$$v_n=2u_n.$$
Then
$$v_0=4,\qquad v_1=5,$$
and
\begin{align*}
v_{n+1}
&=2u_{n+1} \
&=2u_n(u_{n-1}^2-2)-2u_1 \
&=\frac{v_n}{2}\left(\frac{v_{n-1}^2}{4}-2\right)-5 \
&=\frac{v_nv_{n-1}^2}{8}-v_n-5.
\end{align*}
This does not simplify naturally.
Another possibility is that the intended recurrence was
$$u_{n+1}=u_n(u_n^2-3),$$
which would connect directly to the cubic identity. The present recurrence, however, is inconsistent with the stated conclusion.
Since a rigorous proof cannot be given for a false statement, the only mathematically sound course is to identify the contradiction explicitly and prove that the statement as written is false.
Problem Understanding
The problem asks for a proof of a closed formula involving the integral parts of the terms of a recursively defined sequence. This is a Type B problem, since the task is to prove a stated identity.
The sequence is defined by
$$u_{n+1}=u_n(u_{n-1}^2-2)-u_1, \qquad u_0=2, \qquad u_1=\frac52.$$
The claimed conclusion is
$$3\lfloor u_n\rfloor =2^n-(-1)^n$$
for all positive integers $n$.
The core difficulty is that the recurrence is nonlinear and couples two consecutive indices. One expects a hidden algebraic structure or a transformation reducing the recurrence to a simpler form. Before searching for such a structure, the formula must be checked against small values of $n$, since any universal identity must hold for the first few instances.
Direct computation immediately produces a contradiction at $n=2$. Hence the statement, as written, cannot be true.
Proof Architecture
The argument contains two claims.
Lemma 1 states that
$$u_2=\frac52.$$
This follows from direct substitution into the recurrence.
Lemma 2 states that the claimed identity fails for $n=2$. Substituting the exact value of $u_2$ gives
$$3\lfloor u_2\rfloor =6,$$
while the right-hand side equals $3$.
The decisive step is the arithmetic verification at $n=2$. Any attempt to manipulate the recurrence abstractly before checking initial cases risks proving properties of a different sequence or a corrected version of the problem.
Solution
We compute the first terms of the sequence from the defining recurrence
$$u_{n+1}=u_n(u_{n-1}^2-2)-u_1,$$
with
$$u_0=2, \qquad u_1=\frac52.$$
Lemma 1
The second term of the sequence satisfies
$$u_2=\frac52.$$
Proof
Substituting $n=1$ into the recurrence gives
\begin{align*}
u_2
&=u_1(u_0^2-2)-u_1 \
&=\frac52(2^2-2)-\frac52 \
&=\frac52(4-2)-\frac52 \
&=5-\frac52 \
&=\frac52.
\end{align*}
This proves the lemma. ∎
This establishes the exact value of the first nontrivial term; replacing it by a decimal approximation would obscure the later contradiction.
Lemma 2
The identity
$$3\lfloor u_n\rfloor =2^n-(-1)^n$$
fails for $n=2$.
Proof
From Lemma 1,
$$u_2=\frac52.$$
Hence
$$\lfloor u_2\rfloor =2,$$
so
$$3\lfloor u_2\rfloor =3\cdot2=6.$$
On the other hand,
$$2^2-(-1)^2=4-1=3.$$
Thus
$$3\lfloor u_2\rfloor \ne 2^2-(-1)^2.$$
The claimed identity is false for $n=2$. ∎
This establishes that the statement of the problem is inconsistent with the given recurrence and initial conditions; skipping the explicit substitution at $n=2$ would conceal the contradiction.
The proposed identity does not hold for all positive integers $n$. This completes the proof.
∎
Verification of Key Steps
The first delicate point is the computation of $u_2$. Starting directly from the recurrence,
$$u_2=u_1(u_0^2-2)-u_1.$$
Substituting
$$u_0=2,\qquad u_1=\frac52,$$
gives
$$u_2=\frac52(4-2)-\frac52=5-\frac52=\frac52.$$
A careless computation could incorrectly distribute the subtraction and produce
$$\frac52(4-2-1)=\frac52,$$
which happens accidentally to give the same value here. In later terms such an error would become fatal.
The second delicate point is the evaluation of the claimed formula at $n=2$. The left-hand side is
$$3\lfloor \tfrac52\rfloor =3\cdot2=6.$$
The right-hand side is
$$2^2-(-1)^2=4-1=3.$$
The sign in front of $(-1)^n$ is essential. Replacing it by $+$ would give $5$, still not equal to $6$.
A third possible source of error is the interpretation of the notation $2\frac12$. The standard meaning is
$$2\frac12=\frac52.$$
Interpreting it as $2^{1/2}$ would produce a completely different sequence.
Alternative Approaches
Another valid strategy is to compute three or four consecutive terms explicitly and compare their growth with the claimed formula. From
$$u_1=u_2=\frac52,$$
one obtains
$$u_3=\frac{65}{8}=8+\frac18.$$
Then
$$3\lfloor u_3\rfloor =24,$$
while
$$2^3-(-1)^3=9.$$
This produces an even stronger contradiction.
One could also analyze parity alone. Since
$$3\lfloor u_2\rfloor$$
is divisible by $3$, the right-hand side must also be divisible by $3$ if the identity were true. However,
$$2^2-(-1)^2=3,$$
while at $n=3$ the right-hand side equals $9$. The numerical behavior does not match the rapidly growing recurrence, indicating immediately that the printed formula is almost certainly corrupted.