Difference between revisions of "1976 IMO Problems/Problem 6"
m (→Problem) |
|||
Line 22: | Line 22: | ||
<cmath>2^{x_{n}-2x_{n-1}}+2^{-x_{n}+2x_{n-1}}=2^{x_1}+2^{-x_1}</cmath> | <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 | 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> | 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> | 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 | We notice | ||
− | \begin{align*} | + | <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}-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_{n-1}+2x_{n-2}}+2^{x_{n-1}-2x_{n-2}}\\ | ||
&=2^{x_1}+2^{-x_1} | &=2^{x_1}+2^{-x_1} | ||
− | \end{align*} | + | \end{align*}</cmath> |
We then want to show | We then want to show | ||
<cmath>a_n=2^{x_n}+2^{-x_n}</cmath> | <cmath>a_n=2^{x_n}+2^{-x_n}</cmath> | ||
This can be done using induction | This can be done using induction | ||
− | + | ||
− | 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 | + | 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 | Assume for all natural <math>k<n</math> at <math>a_k=2^{x_k}+2^{-x_k}</math>\newline | ||
Then we have that: | Then we have that: | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
a_n &= a_{n}(a_{n-1}^{2}-2)-a_{1} \\ | 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^{-x_{n-2}})^2-2)-(2^{x_{1}}+2^{-x_{0}}) \\ | ||
Line 50: | Line 55: | ||
&=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-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}} | &=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*} | + | \end{align*}</cmath> |
From our first induction proof we have that: | 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> | <cmath>2^{x_{n-1}-2x_{n-2}}+2^{-x_{n-1}+2x_{n-2}}=2^{x_1}+2^{-x_1}</cmath> |
Revision as of 15:29, 29 January 2021
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
Base Case: For ses det
Inductive step: Assume We notice We then want to show This can be done using induction
Base Case
For , it is clear that and Therefore, the base case is proved.
Inductive Step
Assume for all natural at \newline Then we have that: 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 |