Problem 5

Determine all functions

f

from the set of positive integers to the set of positive integers such that, for all positive integers

a

and

b

, there exists a non-degenerate triangle with sides of lengths

a

f(b)

and

f(b+f(a)-1)

. (A triangle is non-degenerate if its vertices are not collinear.)

Step 3 of 4: Induct to make f fully arithmetic

Previous step Next step

f(n)=1+(n-1)\Delta\ \text{ for every } n\ge1

Detailed analysis

We show by induction that $f(n)=1+(n-1)\Delta$ for all $n\ge1$ ; this holds for $n=1$ (as $f(1)=1$ ) and $n=2$ (by definition of $\Delta$ ). Suppose it holds up to some $n\ge2$ . Then $f(n-1)=1+(n-2)\Delta\ne1+n\Delta=f(n)+\Delta$ (they differ by $2\Delta\ne0$ ), so the alternative " $f(n-1)=f(n)+\Delta$ " from Step 2 is impossible; hence $f(n+1)=f(n)+\Delta=1+n\Delta=1+((n+1)-1)\Delta$ , completing the induction.