1978 IMO Problems/Problem 3
Problem
Let a sequence with all its terms positive The positive integer which doesn't belong to the sequence is Find
Solution
Since the -th number missing is and is a member of the sequence, it results that there are exactly "gaps" less than , which leads us to:
now with a simple induction we can prove that , where is the Fibonacci sequence.
our next step now is to prove that , for all with ....and agaiiiiin induction(on ) : :P
for and it`s trivial and now we supose that it`s true for and to prove that holds for , in other words
If for some , then by the inductive assumption and we have:
If is a gap, then is a gap also:
It follows that :
now since we know that each positive integer is expressible as: , where ,
we obtain that and now that we have the general form, pe particulary calculate for :
we can write , therefore
Remark: it can be shown now that , where
The above solution was posted and copyrighted by pohoatza. The original thread for this problem can be found here: [1]
See Also
1978 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |