Difference between revisions of "1977 IMO Problems/Problem 6"
Umtympswede (talk | contribs) (Created page with "= Problem = Let <math>f(n)</math> be a function <math>f: \mathbb{N}^{+}\to\mathbb{N}^{+}</math>. Prove that if <cmath> f(n+1) > f(f(n)) </cmath> for each positive integer <mat...") |
|||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
− | = Problem = | + | ==Problem== |
Let <math>f(n)</math> be a function <math>f: \mathbb{N}^{+}\to\mathbb{N}^{+}</math>. Prove that if <cmath> f(n+1) > f(f(n)) </cmath> for each positive integer <math>n</math>, then <math>f(n)=n</math>. | Let <math>f(n)</math> be a function <math>f: \mathbb{N}^{+}\to\mathbb{N}^{+}</math>. Prove that if <cmath> f(n+1) > f(f(n)) </cmath> for each positive integer <math>n</math>, then <math>f(n)=n</math>. | ||
− | = Solution = | + | ==Solution== |
We will prove this via induction. First we will prove there is a <math>t</math> such that <math>f(t)=1</math> and then that <math>t=1</math> is the only such solution. | We will prove this via induction. First we will prove there is a <math>t</math> such that <math>f(t)=1</math> and then that <math>t=1</math> is the only such solution. | ||
Line 16: | Line 16: | ||
So the inductive step is complete. Therefore, by induction <math>f(n)=n</math> for all positive integers <math>n</math>. | So the inductive step is complete. Therefore, by induction <math>f(n)=n</math> for all positive integers <math>n</math>. | ||
+ | |||
+ | == See Also == {{IMO box|year=1977|num-b=5|after=Last Question}} |
Latest revision as of 15:49, 29 January 2021
Problem
Let be a function . Prove that if for each positive integer , then .
Solution
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 .
See Also
1977 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Question |
All IMO Problems and Solutions |