Maths Olympiad Prep

Library / /73 of 133

Algebra Difficulty 5.7 AIME, harder Prove it Saudi Arabia

Let f:NNf: \mathbb{N} \rightarrow \mathbb{N} be an injective function such that f(1)=2f(1)=2, f(2)=4f(2)=4 and
f(f(m)+f(n))=f(f(m))+f(n) f(f(m)+f(n))=f(f(m))+f(n)
for all m,nNm, n \in \mathbb{N}. Prove that f(n)=n+2f(n)=n+2 for all n2n \geq 2.

Solution

Taking n=1n=1, we obtain f(f(m)+2)=f(f(m))+2f(f(m)+2)=f(f(m))+2, for all mNm \in \mathbb{N}. Taking m=1m=1, we obtain f(2+f(n))=4+f(n)f(2+f(n))=4+f(n), for all nNn \in \mathbb{N}. Therefore
f(f(n))=f(n)+2,for all nN. f(f(n))=f(n)+2, \quad \text{for all } n \in \mathbb{N} .
Because f(2)=f(f(1))=f(1)+2=4f(2)=f(f(1))=f(1)+2=4, we prove by induction that
f(n)=n+2 f(n)=n+2
for all positive even integer n2n \geq 2.
Because the set {f(1)}{f(2),f(4),f(6),}\{f(1)\} \cup \{f(2), f(4), f(6), \ldots\} contains all even positive integers and because ff is an injective function, the image by ff of any odd number n3n \geq 3 is an odd number.
Let
k=min{f(n)f(n) is an odd integer } k=\min \{f(n) \mid f(n) \text{ is an odd integer }\}
and let f(n0)=kf\left(n_{0}\right)=k for some odd positive number n03n_{0} \geq 3. We prove by induction that
f(n)=n+2,for any odd number nk. f(n)=n+2, \quad \text{for any odd number } n \geq k .
Indeed, f(k)=f(f(n0))=f(n0)+2=k+2f(k)=f\left(f\left(n_{0}\right)\right)=f\left(n_{0}\right)+2=k+2. Assume that f(n)=n+2f(n)=n+2, for some odd number nkn \geq k. We deduce that f(n+2)=f(f(n))=f(n)+2=(n+2)+2f(n+2)=f(f(n))=f(n)+2= (n+2)+2.
Clearly, n0<kn_{0}<k, otherwise k=f(n0)=n0+2k+2k=f\left(n_{0}\right)=n_{0}+2 \geq k+2, which is impossible. Therefore,
{f(n0),f(k),f(k+2),f(k+4),}={k,k+2,k+4,k+6,} \left\{f\left(n_{0}\right), f(k), f(k+2), f(k+4), \ldots\right\}=\{k, k+2, k+4, k+6, \ldots\}
covers all possible odd values taken by ff. Because, ff is injective, and f(3),f(5)kf(3), f(5) \geq k are odd integers, we deduce that n0=3,k=5n_{0}=3, k=5 and
f(n)=n+2 f(n)=n+2
for all positive odd integer n2n \geq 2.

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 and solution reproduced as published; topic and difficulty added by this site.