# 1976 IMO Problems/Problem 6

## Problem

A sequence $(u_{n})$ is defined by

$$u_{0} = 2 \quad u_{1} = \frac {5}{2}, u_{n + 1} = u_{n}(u_{n - 1}^{2} - 2) - u_{1} \quad \textnormal{ for } n = 1,\ldots$$

Prove that for any positive integer $n$ we have

$$\lfloor u_{n} \rfloor = 2^{\frac {(2^{n} - ( - 1)^{n})}{3}}$$

(where $\lfloor x\rfloor$ denotes the smallest integer $\leq$ $x$)$.$

## Solution

Let the sequence $(x_n)_{n \geq 0}$ be defined as $x_{0}=0,x_{1}=1, x_{n}=x_{n-1}+2x_{n-2}$ We notice $$x_n=\frac{2^n-(-1)^n}{3}$$ Because the roots of the characteristic polynomial $x_{n}=x_{n-1}+2x_{n-2}$ are $-1$ and $2$. \\newline We also see $\frac{2^1-(-1)^1}{3}=1=x_1$, $\frac{2^2-(-1)^2}{3}=1=x_2$ We want to prove $$2^{x_{n}-2x_{n-1}}+2^{-x_{n}+2x_{n-1}}=2^{x_1}+2^{-x_1}$$ This is done by induction \subsection*{Base case} For $n=1$ ses det $2^{1-0}+2^{0-1}=2^{1}+2^{-1}$

\subsection*{Induction step} Assume $2^{x_{n-1}-2x_{n-2}}+2^{-x_{n-1}+2x_{n-2}}=2^{x_1}+2^{-x_1}$ We notice \begin{align*} 2^{x_{n}-2x_{n-1}}+2^{-x_{n}+2x_{n-1}} &=2^{x_{n-1}+2x_{n-2}-2x_{n-1}}+2^{-(x_{n-1}+2x_{n-2})+2x_{n-1}}\\ &=2^{-x_{n-1}+2x_{n-2}}+2^{x_{n-1}-2x_{n-2}}\\ &=2^{x_1}+2^{-x_1} \end{align*}\newline We then want to show $$a_n=2^{x_n}+2^{-x_n}$$ This can be done using induction \subsection*{Base case} For $n=1$, it is clear that $$a_1=\frac{5}{2}$$ and $$2^{x_1}+2^{-x_1}=2^1+2^{-1}=2+\frac{1}{2}=\frac{5}{2}$$ Therefore, the base case is proved \subsection*{Induktionsskridt} Assume for all natural $k at $a_k=2^{x_k}+2^{-x_k}$\newline Then we have that: \begin{align*} a_n &= a_{n}(a_{n-1}^{2}-2)-a_{1} \\

&=  (2^{x_{n-1}}+2^{-x_{n-1}})((2^{x_{n-2}}+2^{-x_{n-2}})^2-2)-(2^{x_{1}}+2^{-x_{0}}) \\
&= (2^{x_{n-1}}+2^{-x_{n-1}})((2^{x_{n-2}})^2+(2^{-x_{n-2}})^2+2*2^{x_{n-2}}*2^{-x_{n-2}}-2)-(2^{x_{1}}+2^{-x_{0}}) \\
&=(2^{x_{n-1}}+2^{-x_{n-1}})((2^{2x_{n-2}})+(2^{-2x_{n-2}})+2*2^{x_{n-2}-x_{n-2}}-2)-(2^{x_{1}}+2^{-x_{0}}) \\
&=(2^{x_{n-1}}+2^{-x_{n-1}})((2^{2x_{n-2}})+(2^{-2x_{n-2}})+2-2)-(2^{x_{1}}+2^{-x_{0}}) \\


&=2^{x_{n-1}}*2^{2x_{n-2}}+2^{-x_{n-1}}2^{-2x_{n-2}}+2^{x_{n-1}}*2^{-2x_{n-2}}+2^{-x_{n-1}}*2^{2x_{n-2}}-2^{x_{1}}-2^{-x_{0}}\\ &=2^{x_{n-1}+2x_{n-2}}+2^{-(x_{n-1}+2x_{n-2}})+2^{x_{n-1}-2x_{n-2}}+2^{-x_{n-1}+2x_{n-2}}-2^{x_{1}}-2^{-x_{0}}\\ &=2^{x_{n}}+2^{-x_{n}}+2^{x_{n-1}-2x_{n-2}}+2^{-x_{n-1}+2x_{n-2}}-2^{x_{1}}-2^{-x_{0}} \end{align*} From our first induction proof we have that: $$2^{x_{n-1}-2x_{n-2}}+2^{-x_{n-1}+2x_{n-2}}=2^{x_1}+2^{-x_1}$$ Then: $$a_n=2^{x_n}+2^{-x_n}+2^{x_1}+2^{-x_1}-(2^{x_1}+2^{-x_1})=2^{x_n}+2^{-x_n}$$ We notice $\left[a_n\right]=\left[2^{x_n}+2^{-x_n}\right]=2^{x_n}$, Because $2^{x_n} \in \mathbb{N}$ and $2^{-x_n}<1$, for all $n>0$ Finally we conclude $$\left[a_n\right]=2^{\frac{2^n-(-1)^n}{3}}$$