Advanced book on Mathematics Olympiad

246 5 Number Theory

We pursue the track off( 0 )=0 first. We have

2 f( 12 + 02 )=(f ( 1 ))^2 +(f ( 0 ))^2 ,

so 2f( 1 ) =f( 1 )^2 , and hencef( 1 ) =0orf( 1 ) =2. Let us see what happens if
f( 1 )=2, since this is the most interesting situation. We find immediately

2 f( 2 )= 2 f( 12 + 12 )=(f ( 1 ))^2 +(f ( 1 ))^2 = 8 ,

sof( 2 )=4, and then

2 f( 4 )= 2 f( 22 + 02 )=(f ( 2 ))^2 +(f ( 0 ))^2 = 16 ,

2 f( 5 )= 2 f( 22 + 12 )=(f ( 2 ))^2 +(f ( 1 ))^2 = 20 ,

2 f( 8 )= 2 f( 22 + 22 )=(f ( 2 ))^2 +(f ( 2 ))^2 = 32.

Sof( 4 )=8,f( 5 )=10,f( 8 )=16. In fact,f (n)= 2 nforn≤10, but as we will see
below, the proof is more involved. Indeed,

100 =(f ( 5 ))^2 +(f ( 0 ))^2 = 2 f( 52 )= 2 f( 32 + 42 )=(f ( 3 ))^2 +(f ( 4 ))^2

=(f ( 3 ))^2 + 64 ,

hencef( 3 )=6. Then immediately

2 f( 9 )= 2 f( 32 + 02 )=(f ( 3 ))^2 +(f ( 0 ))^2 = 36 ,

2 f( 10 )= 2 f( 32 + 12 )=(f ( 3 ))^2 +(f ( 1 ))^2 = 40 ,

sof( 9 )=18,f( 10 )=20.
Applying an idea used before, we have

400 =(f ( 10 ))^2 +(f ( 0 ))^2 = 2 f( 102 )= 2 f( 62 + 82 )=(f ( 6 ))^2 +(f ( 8 ))^2

=(f ( 6 ))^2 + 256 ,

from which we obtainf( 6 )=12. Forf( 7 )we use the fact that 7^2 + 12 = 52 + 52 and
the equality

(f ( 7 ))^2 +(f ( 1 ))^2 =(f ( 5 ))^2 +(f ( 5 ))^2

to obtainf( 7 )=14.
We want to prove thatf (n)= 2 nforn>10 using strong induction. The argument
is based on the identities

( 5 k+ 1 )^2 + 22 =( 4 k+ 2 )^2 +( 3 k− 1 )^2 ,