1976 IMO Problems/Problem 6
Problem
A sequence is defined by
Prove that for any positive integer we have
(where denotes the smallest integer
)
Solution
Let the sequence be defined as
\[
x_{0}=0,x_{1}=1, x_{n}=x_{n-1}+2x_{n-2}
\]
We notice
Because the roots of the characteristic polynomial
are
and
. \\newline We also see
,
We want to prove
This is done by induction
\subsection*{Base case}
For
ses det
\subsection*{Induction step}
Assume
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
This can be done using induction
\subsection*{Base case}
For
, it is clear that
and
Therefore, the base case is proved
\subsection*{Induktionsskridt}
Assume for all natural
at
\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:
Then:
We notice
, Because
and
, for all
Finally we conclude
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 |