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