IMO 2009 Q3

Let f: \mathbb N^+ \to \mathbb N^+ be a strictly increasing function, such that f(f(n)) and f(f(n)+1) are both arithmetic progressions in n. Show that f(n) itself is an arithmetic progression.

Let f(f(n))=an+b, f(f(n)+1)=cn+d.

Consider set M= \{m| \exists n\in \mathbb N^+,f(n+1)-f(n)=m\}. We claim that this set is bounded, thus finite.

It is bounded below by 1 by the strict monotonicity. If it was not bounded from above, we have \exists n\in \mathbb N^+, f(n+1)-f(n) >a. Now, since f(f(n))=an+b, and that f is strictly increasing, f(f(n)+1)\ge f(f(n))+1, f(f(n)+2) \ge f(f(n)+1) +1...... Thus f(f(n)+(f(n+1)-f(n)))\ge f(f(n))+f(n+1)-f(n)>f(f(n))+a. This is impossible because f(f(n+1))=f(f(n))+a. Thus M is bounded, and thus finite.

We claim that a=c. If a>c, for n large enough, we must have an+b > cn+d, which contradicts the monotonicity of f(n). If a<c, we then have f(f(n)+1)-f(f(n))=(c-a)n+d-b which is unbounded for n\to \infty. But we know that (c-a)n+(b-d) \in M which is bounded. This is a contradiction. Thus a=c.

Apply f(n) to both sides of f(f(n))=an+b, we have f(an+b)=f(f(f(n)))=af(n)+b.

Consider the minimal element of M, let it be \mu, attained at n=\eta. Let n=\eta and \eta +1 in f(an+b)=af(n)+b, we thus have $f(a\eta +a+b)=af(\eta+1)+b=af(\eta)+a\mu+b.$

Because \mu is the minimal element of M, it is thus necessary that f(a\eta + b+k)\ge k\mu +f(a\eta +b)=k\mu +af(\eta)+b. In particular, the equality is attained if and only if f(a\eta + b + j+1)-f(a\eta + b +j)=\mu, \forall 0\le j \le k-1. Let k=a, f(a\eta +b +a) \ge a\mu + af(\eta)+b=f(a\eta +b +a). Thus equality IS attained and we must have f(a\eta+b+1)-f(a\eta+b)=\mu.

Recall that a\eta+b=f(f(\eta)), letting n=f(\eta) in the problem’s condition gives f(a\eta+b)=f(f(f(\eta)))=af(\eta)+b, and f(a\eta +b +1)=f(f(f(\eta))+1)=af(\eta)+d. Since f(a\eta + b +1)-f(a\eta+b)=\mu, that implies d-b=\mu.

Let the maximal element of M be \nu, and repeat the same argument above, we would also have d-b = \nu. Thus M is a single-element set, or, the difference f(n+1)-f(n) is a constant for all n\in \mathbb N^+. This proves the statement.


Comment: Superficial investigation can only lead one to a=c and af(n)+b = f(an+b), and it becomes difficult to move on from here as one has to disentangle the iteration of the function. The problem only gives very limited information about the values attained by f, and the information accumulate near the range of the iteration. We see that this range is in general not the same as \mathbb N^+, and thus we have to find an argument to integrate the scattered local information. The definition of \mu and \nu plays this role by interacting directly with the function values elsewhere (considering f(a\eta + b +k)'s values and differences between two consecutive terms, where the ‘equality of the global inequality implies all local equalities’ is really the fruit of the global consideration in defining \mu).

After knowing that f(y+1)-f(y)=\mu implies f(ay+b+1)-f(ay+b)=\mu, iterating the linear function to try to give a full description of the set of positive integers on which the consecutive difference is minimalised is a natural idea — but turns out uneconomical: it is not clear how to force the subset that minimalise the consecutive difference and the subset that maximises the difference to intersect in that manner. In fact if that could be done the second problem condition becomes unused in deriving the solution–uncommon for Olympiad problems. Thus we seek to show that the subset of \mathbb N^+ on which the consecutive difference is minimised (maximised) intersects the image of f instead, which is already done.

I reckon this problem is quite nice (except its original formulation in terms of sequences which uses sub-sub-scripts which is painful to read), as one does not have access to any function value at any point (thus avoiding some ad hoc phenomena) but instead requires conceptual consideration. It is impossible to gauge the consideration of the function with any non-trivial solution, as there isn’t any.

When the functional equation acts on integer sets, it is almost always (practically, the ‘almost’ is redundant in Olympiads) important to consider properties characteristic of integers (extremal elements, number theory, discreteness, etc.) as if a solution without these considerations is possible the problem proposer would just define it on a wider domain. Because direct comparison of values maybe impossible, it might also be useful to consider asymptotic behaviours of certain auxiliary functions to gain information about parameters (here the proof that a=c.)

The problem is proposed by Gabriel Carroll, USA, and appeared in the IMO 2009 as Q3.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s