Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1976 IMO Problems/Problem 6"

(New page: == Problem == {{problem}} == Solution == {{solution}} == See also == {{IMO box|year=1976|num-b=1|num-a=3}})
 
(→‎Solution)
 
(9 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
{{problem}}
+
A sequence <math>(u_{n})</math> is defined by
 +
 
 +
<cmath>u_{0} = 2 \quad u_{1} = \frac {5}{2}, u_{n + 1} = u_{n}(u_{n - 1}^{2} - 2) - u_{1} \ \text{ for } n = 1,\cdots</cmath>
 +
 
 +
Prove that for any positive integer <math>n</math> we have
 +
 
 +
<cmath>\lfloor u_{n} \rfloor = 2^{\frac {(2^{n} - ( - 1)^{n})}{3}}</cmath>
 +
 
 +
(where <math>\lfloor x\rfloor</math> denotes the smallest integer <math>\leq</math> <math>x</math>)<math>.</math>
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
 
 +
Let the sequence <math>(x_n)_{n \geq 0}</math> be defined as
 +
<cmath>x_{0}=0,x_{1}=1, x_{n}=x_{n-1}+2x_{n-2}</cmath>
 +
We notice
 +
<cmath>x_n=\frac{2^n-(-1)^n}{3}</cmath>
 +
Because the roots of the characteristic polynomial <math>x_{n}=x_{n-1}+2x_{n-2}</math> are <math>-1</math> and <math>2</math>.
 +
 
 +
We also see <math>\frac{2^1-(-1)^1}{3}=1=x_1</math>, <math>\frac{2^2-(-1)^2}{3}=1=x_2</math>
 +
We want to prove
 +
<cmath>2^{x_{n}-2x_{n-1}}+2^{-x_{n}+2x_{n-1}}=2^{x_1}+2^{-x_1}</cmath>
 +
This is done by induction
 +
 
 +
Base Case:
 +
For <math>n=1</math> ses det <math>2^{1-0}+2^{0-1}=2^{1}+2^{-1}</math>
 +
 
 +
Inductive step:
 +
Assume <math>2^{x_{n-1}-2x_{n-2}}+2^{-x_{n-1}+2x_{n-2}}=2^{x_1}+2^{-x_1}</math>
 +
We notice
 +
<cmath>\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*}</cmath>
 +
We then want to show
 +
<cmath>a_n=2^{x_n}+2^{-x_n}</cmath>
 +
This can be done using induction
 +
 
 +
Base Case
 +
 
 +
For <math>n=1</math>, it is clear that <cmath>a_1=\frac{5}{2}</cmath> and <cmath>2^{x_1}+2^{-x_1}=2^1+2^{-1}=2+\frac{1}{2}=\frac{5}{2}</cmath> Therefore, the base case is proved.
 +
 
 +
Inductive Step
 +
 
 +
Assume for all natural <math>k<n</math> at <math>a_k=2^{x_k}+2^{-x_k}</math>\newline
 +
Then we have that:
 +
<cmath>\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*}</cmath>
 +
From our first induction proof we have that:
 +
<cmath>2^{x_{n-1}-2x_{n-2}}+2^{-x_{n-1}+2x_{n-2}}=2^{x_1}+2^{-x_1}</cmath>
 +
Then:
 +
<cmath>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}</cmath>
 +
We notice
 +
<math>\left[a_n\right]=\left[2^{x_n}+2^{-x_n}\right]=2^{x_n}</math>, Because <math>2^{x_n} \in \mathbb{N}</math> and <math>2^{-x_n}<1</math>, for all <math>n>0</math>
 +
Finally we conclude
 +
<cmath>\left[a_n\right]=2^{\frac{2^n-(-1)^n}{3}}</cmath>
 +
 
 +
==Solution 2==
 +
 
 +
We note that there is a slightly easier claim that can be proved also by induction. By testing out smaller terms, one sees that
 +
 
 +
<cmath>u_n= 2^{\frac{2^n-(-1)^n}{3}} + 2^{- \frac{2^n-(-1)^n}{3}}</cmath>
 +
 
 +
for <math>n=1,2,3</math> (note that since we are using strong induction to prove this result this suffices as the base case).
 +
 
 +
Suppose that the equation above holds for all <math>k \le n</math>. Then for <math>n+1</math>, one have
 +
 
 +
<cmath>\begin{align*}
 +
u_{n+1} &= u_n (u_{n-1} ^2 -2) -u_1 \\
 +
&= (2^{\frac{2^n-(-1)^n}{3}}+2^{- \frac{2^n-(-1)^n}{3}}) \cdot ( (2^{\frac{2^{n-1}-(-1)^{n-1}}{3}}+2^{- \frac{2^{n-1}-(-1)^{n-1}}{3}} )^2 -2) - \frac{5}{2} \\
 +
&= (2^{\frac{2^n-(-1)^n}{3}}+2^{- \frac{2^n-(-1)^n}{3}}) \cdot ( (2^{\frac{2^{n-1}-(-1)^{n-1}}{3}})^2 + (2^{- \frac{2^{n-1}-(-1)^{n-1}}{3}})^2 )- \frac{5}{2} \\
 +
&= (2^{\frac{2^n-(-1)^n}{3}}+2^{- \frac{2^n-(-1)^n}{3}}) \cdot (2^{\frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} + 2^{- \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}})- \frac{5}{2} \\
 +
&= 2^{\frac{2^n-(-1)^n}{3} + \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} + 2^{- \frac{2^n-(-1)^n}{3} - \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} + 2^{(-1)^n} + 2^{-(-1)^n} -\frac{5}{2} \\
 +
&= 2^{\frac{2^n-(-1)^n}{3} + \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} + 2^{- \frac{2^n-(-1)^n}{3} - \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} \\
 +
&= 2^{\frac{2^{n+1}-(-1)^{n+1}}{3}}+2^{- \frac{2^{n+1}-(-1)^{n+1}}{3}}
 +
\end{align*}</cmath>
 +
 
 +
as desired. The strong induction proves our claim. Now, it is rather obvious that <math>2^{- \frac{2^n-(-1)^n}{3}}</math> is between 0 and 1, so indeed our claim proves the result. <math>\square</math>
 +
 
 +
~[[Ddk001]]
 +
 
 
== See also ==
 
== See also ==
−
{{IMO box|year=1976|num-b=1|num-a=3}}
+
{{IMO box|year=1976|num-b=5|after=Final Question}}

Latest revision as of 20:57, 28 May 2025

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} \ \text{ for } n = 1,\cdots\]

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$.

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

Base Case: For $n=1$ ses det $2^{1-0}+2^{0-1}=2^{1}+2^{-1}$

Inductive 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*} We then want to show \[a_n=2^{x_n}+2^{-x_n}\] This can be done using induction

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.

Inductive Step

Assume for all natural $k<n$ 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}}\]

Solution 2

We note that there is a slightly easier claim that can be proved also by induction. By testing out smaller terms, one sees that

\[u_n= 2^{\frac{2^n-(-1)^n}{3}} + 2^{- \frac{2^n-(-1)^n}{3}}\]

for $n=1,2,3$ (note that since we are using strong induction to prove this result this suffices as the base case).

Suppose that the equation above holds for all $k \le n$. Then for $n+1$, one have

\begin{align*} u_{n+1} &= u_n (u_{n-1} ^2 -2) -u_1 \\ &= (2^{\frac{2^n-(-1)^n}{3}}+2^{- \frac{2^n-(-1)^n}{3}}) \cdot ( (2^{\frac{2^{n-1}-(-1)^{n-1}}{3}}+2^{- \frac{2^{n-1}-(-1)^{n-1}}{3}} )^2 -2) - \frac{5}{2} \\ &= (2^{\frac{2^n-(-1)^n}{3}}+2^{- \frac{2^n-(-1)^n}{3}}) \cdot ( (2^{\frac{2^{n-1}-(-1)^{n-1}}{3}})^2 + (2^{- \frac{2^{n-1}-(-1)^{n-1}}{3}})^2 )- \frac{5}{2} \\ &= (2^{\frac{2^n-(-1)^n}{3}}+2^{- \frac{2^n-(-1)^n}{3}}) \cdot (2^{\frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} + 2^{- \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}})- \frac{5}{2} \\ &= 2^{\frac{2^n-(-1)^n}{3} + \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} + 2^{- \frac{2^n-(-1)^n}{3} - \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} + 2^{(-1)^n} + 2^{-(-1)^n} -\frac{5}{2} \\ &= 2^{\frac{2^n-(-1)^n}{3} + \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} + 2^{- \frac{2^n-(-1)^n}{3} - \frac{2^{n}-2 \cdot (-1)^{n-1}}{3}} \\ &= 2^{\frac{2^{n+1}-(-1)^{n+1}}{3}}+2^{- \frac{2^{n+1}-(-1)^{n+1}}{3}} \end{align*}

as desired. The strong induction proves our claim. Now, it is rather obvious that $2^{- \frac{2^n-(-1)^n}{3}}$ is between 0 and 1, so indeed our claim proves the result. $\square$

~Ddk001

See also

1976 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Final Question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1976_IMO_Problems/Problem_6&oldid=249335"