The second condition implies that for all a,b∈N the triangle inequalities hold:
f(a)+f(b)f(a)+f(a+b−1)f(b)+f(a+b−1)>f(a+b−1),>f(b),>f(a).
First, consider a=b=2. It then follows from the first condition that f(4)=f(2)2, and the second condition implies that 2f(2)>f(3).
Now, let a=3, b=2. The second condition then implies that f(2)+f(3)>f(4). So,
f(2)2=f(4)<f(2)+f(3)<f(2)+2f(2)=3f(2)⟹f(2)(3−f(2))>0.
Since f(2) is a positive integer there are only two possibilities: f(2)=1 and f(2)=2. We consider the two cases separately:
* If f(2)=1, then let a=2, b=1. The second condition implies that 2f(2)>f(1), so f(1)=1. We can now use induction to show that f(n)=1 for all n. This is true for the base case. Now, assume that f(n)=1 for some n≥2. Using a=n, b=2 in the second condition we get
f(n+1)<f(n)+f(2)=2⟹f(n+1)=1.
This gives us the solution f(n)=1 for all n∈N.
* If f(2)=2, then f(4)=f(2)2=4. What is more, for all k∈N the induction on the first condition implies that
f(2k)=f(2)f(2k−1)=⋯=f(2)k=2k.
We know from before that f(4)−f(2)<f(3)<2f(2), which implies that f(3)=3.
We now use induction to show that f(n)=n for all n≥2. The base case is obvious. Now, assume that the induction hypothesis holds for 2,3,…,n−1. Using a=n−1, b=2 we get
f(n)<f(n−1)+f(2)=n+1⟹f(n)≤n.
Let 2r be the greatest power of 2, such that 2r≤n. If 2r=n, then the induction step is concluded because f(2r)=2r. Otherwise let n=2r+s, where 1≤s<2r.
We will use a=n=2r+s, b=2r−s+1 with the second condition. Since 2r−s+1≥2 the induction hypothesis implies that f(2r−s+1)=2r−s+1. So,
f(n)+f(2r−s+1)⟹f(n)⟹f(n)>f(2r+s+2r−s+1−1)=f(2r+1)>f(2r+1)−f(2r−s+1)=2r+s−1=n−1≥n.
We have shown that f(n)=n which concludes the induction step. All that remains is to determine f(1). The only condition is that f(1)<2f(2)=4. So, f(1) can be either 1, 2 or 3.
We have obtained the solutions f(n)=1 for all n and f(n)=n for n≥2 with f(1)∈{1,2,3}. It is easy to check that all of these satisfy the conditions of the problem.