Difference between revisions of "1976 IMO Problems/Problem 6"
George-magn (talk | contribs) |
m (→Problem) |
||
Line 2: | Line 2: | ||
A sequence <math>(u_{n})</math> is defined by | 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} \quad \textnormal{for} n = 1,\ldots</cmath> | + | <cmath>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</cmath> |
Prove that for any positive integer <math>n</math> we have | Prove that for any positive integer <math>n</math> we have |
Revision as of 11:57, 23 March 2019
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
&= (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 |