Difference between revisions of "1976 IMO Problems/Problem 6"
Kcbhatraju (talk | contribs) (→Problem) |
George-magn (talk | contribs) |
||
Line 11: | Line 11: | ||
== Solution == | == Solution == | ||
− | {{ | + | |
+ | Let the sequence <math>(x_n)_{n \geq 0}</math> be defined as | ||
+ | \[ | ||
+ | x_{0}=0,x_{1}=1, x_{n}=x_{n-1}+2x_{n-2} | ||
+ | \] | ||
+ | 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>. \\newline 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 | ||
+ | \subsection*{Base case} | ||
+ | For <math>n=1</math> ses det <math>2^{1-0}+2^{0-1}=2^{1}+2^{-1}</math> | ||
+ | |||
+ | \subsection*{Induction 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 | ||
+ | \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 | ||
+ | <cmath>a_n=2^{x_n}+2^{-x_n}</cmath> | ||
+ | This can be done using induction | ||
+ | \subsection*{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 | ||
+ | \subsection*{Induktionsskridt} | ||
+ | Assume for all natural <math>k<n</math> at <math>a_k=2^{x_k}+2^{-x_k}</math>\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: | ||
+ | <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> | ||
+ | |||
== See also == | == See also == | ||
{{IMO box|year=1976|num-b=5|after=Final Question}} | {{IMO box|year=1976|num-b=5|after=Final Question}} |
Revision as of 16:38, 4 August 2018
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 |