Maths Olympiad Prep

Library / /155 of 397

Algebra Difficulty 5.6 AIME, harder Prove it Taiwan

Let NN denote the set of all positive integers. Find all functions f:NNf : N \to N such that for every positive integer nn,
1f(1)f(2)+1f(2)f(3)++1f(n)f(n+1)=f(f(n))f(n+1). \frac{1}{f(1)f(2)} + \frac{1}{f(2)f(3)} + \dots + \frac{1}{f(n)f(n+1)} = \frac{f(f(n))}{f(n+1)}.

Solution

Since
112+123++1n(n+1)=nn+1, \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1},
we guess that f(n)=nf(n) = n is the unique solution satisfying the given condition.
Substituting n=1n = 1, we get f(f(1))f(1)=1f(f(1))f(1) = 1, so f(1)=1f(1) = 1.
Substituting n+1n+1 for nn in the given condition, we get
f(f(n))f(n+1)+1f(n+1)f(n+2)=f(f(n+1))f(n+2). \frac{f(f(n))}{f(n+1)} + \frac{1}{f(n+1)f(n+2)} = \frac{f(f(n+1))}{f(n+2)}.
The above is equivalent to
f(f(n))f(n+2)+1=f(f(n+1))f(n+1). f(f(n))f(n+2) + 1 = f(f(n+1))f(n+1).
Note: f(n+1)=1f(f(n+1))=1f(n+1) = 1 \Rightarrow f(f(n+1)) = 1. Therefore, f(f(n))f(n+2)=0f(f(n))f(n+2) = 0 cannot occur. Hence f(n)>1,n>1f(n) > 1, \forall n > 1.
Using mathematical induction, we prove: f(f(n))<f(n+1)f(f(n)) < f(n+1).
When n=1n = 1, f(2)>1=f(f(1))f(2) > 1 = f(f(1)) holds.
If f(n+1)>f(f(n))f(n+1) > f(f(n)) then f(n+1)f(f(n))+1f(n+1) \ge f(f(n)) + 1. Therefore
f(f(n))f(n+2)+1f(f(n+1))f(f(n))+f(f(n+1)). f(f(n))f(n+2) + 1 \ge f(f(n+1))f(f(n)) + f(f(n+1)).
Since n+1>1n+1 > 1, we have f(n+1)>1f(n+1) > 1. That is, f(f(n+1))>1f(f(n+1)) > 1. From this we can deduce
f(n+2)>f(f(n+1)). f(n+2) > f(f(n+1)).

f(n+1)>f(f(n)),nN.f(n + 1) > f(f(n)), \forall n \in N.
Below we prove that the function satisfying (1) is f(n)=n,nN. \text{Below we prove that the function satisfying (1) is } f(n) = n, \forall n \in N.
Let the set S={f(f(1)),f(2),f(f(2)),f(2),,f(f(n1)),f(n),f(f(n)),f(n+1),}S = \{f(f(1)), f(2), f(f(2)), f(2), \dots, f(f(n-1)), f(n), f(f(n)), f(n+1), \dots\}, then the set SS has a smallest element f(n0)f(n_0), for some positive integer n0n_0. By (1), we can obtain f(n0)=1f(n_0) = 1. Below we prove: n0=1n_0 = 1.
Suppose n0>1n_0 > 1 then 1=f(n0)>f(f(n01))1 = f(n_0) > f(f(n_0 - 1)), which is a contradiction! Therefore f(1)=1f(1) = 1 and f(n)>1f(n) > 1 for n>1n > 1.
Consider f:{n2}{n2}f: \{n \ge 2\} \to \{n \ge 2\}, similarly we can obtain: f(2)=2f(2) = 2 and f(n)>2f(n) > 2 for n>2n > 2. By mathematical induction we can prove:
f(k)=k, and f(n)>k, for n>k, f(k) = k, \text{ and } f(n) > k, \text{ for } n > k,
therefore the unique solution satisfying the problem is f(n)=n,nNf(n) = n, \forall n \in N.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.