Advanced book on Mathematics Olympiad

8 1 Methods of Proof

Example.Letf :N→Nbe a strictly increasing function such thatf( 2 )=2 and
f (mn)=f (m)f (n)for every relatively prime pair of positive integersmandn. Prove
thatf (n)=nfor every positive integern.

Solution.The proof is of course by induction onn. Monotonicity implies right away
thatf( 1 )=1. However, the base case is not the givenf( 2 )=2, butf( 2 )=2 and
f( 3 )=3.
So let us findf( 3 ). Becausefis strictly increasing,f( 3 )f ( 5 )=f( 15 )<f( 18 )=
f( 2 )f ( 9 ). Hencef( 3 )f ( 5 )< 2 f( 9 )andf( 9 )<f( 10 ) = f( 2 )f ( 5 ) = 2 f( 5 ).
Combiningthese inequalities, we obtainf( 3 )f ( 5 )< 4 f( 5 ),sof( 3 )<4. But we know
thatf( 3 )>f( 2 )=2, which means thatf( 3 )can only be equal to 3.
The base case was the difficult part of the problem; the induction step is rather
straightforward. Letk>3 and assume thatf(j)=jforj<k. Consider 2r( 2 m+ 1 )
to be the smallest even integer greater than or equal tokthat is not a power of 2. This
number is equal to eitherk,k+1,k+2, ork+3, and sincek>3, both 2rand 2m+ 1
are strictly less thank. From the induction hypothesis, we obtainf( 2 r( 2 m+ 1 ))=
f( 2 r)f ( 2 m+ 1 )= 2 r( 2 m+ 1 ). Monotonicity, combined with the fact that there are at
most 2r( 2 m+ 1 )values that the function can take in the interval[ 1 , 2 r( 2 m+ 1 )], implies
thatf(l)=lforl≤ 2 r( 2 m+ 1 ). In particular,f(k)=k. We conclude thatf (n)=n
for all positive integersn. 

A functionf :N→Cwith the property thatf( 1 )=1 andf (mn)=f (m)f (n)
whenevermandnare coprime is called a multiplicative function. Examples include
the Euler totient function and the Möbius function. In the case of our problem, the
multiplicative function is also strictly increasing. A more general result of P. Erdos shows ̋
that any increasing multiplicative function that is not constant is of the formf (n)=nα
for someα>0.

23.Show that every positive integer can be written as a sum of distinct terms of the

Fibonacci sequence. (The Fibonacci sequence(Fn)nis defined byF 0 =0,F 1 =1,

andFn+ 1 =Fn+Fn− 1 ,n≥1.)

24.Prove that the Fibonacci sequence satisfies the identity

F 2 n+ 1 =Fn^2 + 1 +Fn^2 , forn≥ 0.

25.Prove that the Fibonacci sequence satisfies the identity

F 3 n=Fn^3 + 1 +Fn^3 −Fn^3 − 1 , forn≥ 0.

26.Show that an isosceles triangle with one angle of 120◦can be dissected inton≥ 4

triangles similar to it.