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