5.1 Integer-Valued Sequences and Functions 247( 5 k+ 2 )^2 + 12 =( 4 k+ 1 )^2 +( 3 k+ 2 )^2 ,
( 5 k+ 3 )^2 + 12 =( 4 k+ 3 )^2 +( 3 k+ 1 )^2 ,
( 5 k+ 4 )^2 + 22 =( 4 k+ 2 )^2 +( 3 k+ 4 )^2 ,
( 5 k+ 5 )^2 + 02 =( 4 k+ 4 )^2 +( 3 k+ 3 )^2.Note that ifk≥2, then the first term on the left is strictly greater then any of the two terms
on the right, and this makes the induction possible. Assume thatf (m)= 2 mform<n
and let us provef (n)= 2 n. Letn= 5 k+j,1≤j≤5, and use the corresponding
identity to writen^2 +m^21 =m^22 +m^23 , wherem 1 ,m 2 ,m 3 are positive integers less than
n. We then have
(f (n))^2 +(f (m 1 ))^2 = 2 f(n^2 +m^21 )= 2 f(m^22 +m^23 )=(f (m 2 ))^2 +(f (m 3 ))^2.This then gives
(f (n))^2 =( 2 m 2 )^2 +( 2 m 3 )^2 −( 2 m 1 )^2 = 4 (m^22 +m^23 −m^21 )= 4 n^2.Hencef (n)= 2 n, completing the inductive argument. And indeed, this function satisfies
the equation from the statement.
If we start with the assumptionf( 1 )=0, the exact same reasoning applied mutatis
mutandis shows thatf (n)=0,n ≥0. And the story repeats iff( 0 )=1, giving
f (n)=1,n≥0. Thus the functional equation has three solutions:f (n)= 2 n,n≥0,
and the constant solutionsf (n)=0,n≥0, andf (n)=1,n≥0.
With the additional hypothesisf(m^2 )≥f(n^2 )ifm≥n, this problem appeared at the
1998 Korean Mathematical Olympiad. The solution presented above was communicated
to us by B.J. Venkatachala.
699.Letkbe a positive integer. The sequence(an)nis defined bya 1 =1, and forn≥2,
anis thenth positive integer greater thanan− 1 that is congruent tonmodulok. Find
anin closed form.
700.Three infinite arithmetic progressions are given, whose terms are positive integers.
Assuming that each of the numbers 1, 2 , 3 , 4 , 5 , 6 , 7 ,8 occurs in at least one of these
progressions, show that 1980 necessarily occurs in one of them.
701.Find all functionsf:N→Nsatisfying
f (n)+ 2 f (f (n))= 3 n+ 5 , for alln∈N.702.Find all functionsf:Z→Zwith the property that
2 f(f(x))− 3 f(x)+x= 0 , for allx∈Z.