1977 IMO Problems/Problem 6
Let be a function . Prove that if for each positive integer , then .
We will prove this via induction. First we will prove there is a such that and then that is the only such solution.
Define the sequence with for and . By the given inequality we have that , this can be used to form a inequality chain of decreasing positive integers: By Infinite Descent, this sequence must terminate, and the only way it can terminate is if we input something into that is outside of its range. This can only happen if since the range and domain of are the positive integers. Since , there is a integer () such that .
Now if , then , which is impossible since by the range of , so we have is the only time when .
Now for the inductive step.
Assume that for all and these are the only times these values occur. We will prove that and that this is the only time this value occurs. Define the sequence similarly, except that , by the reasoning above, there is a such that , by the inductive assumption, this means that , we can repeat the inductive assumption to get that . This implies that . Thus, there is a such that .
Now for that , we have , which means that by the inductive assumption which implies since we must have , otherwise . So is the only time when
So the inductive step is complete. Therefore, by induction for all positive integers .