Methods of Proof 331It is straightforward to check that thegandhconstructed this way satisfy the required
condition.
(Kvant(Quantum))
22.We prove the property by induction onn. Forn=2, any number of the formn= 2 t^2 ,
tan integer, would work.
Let us assume that forn=kthere is a numbermwith the property from the statement,
and let us find a numberm′that fulfills the requirement forn=k+1. We assume in
addition thatm≥7; thus we strengthen somewhat the conclusion of the problem.
We need the fact that every integerp≥2 can be represented asa^2 +b^2 −c^2 , where
a, b, care positive integers. Indeed, ifpis even, sayp= 2 q, then
p= 2 q=( 3 q)^2 +( 4 q− 1 )^2 −( 5 q− 1 )^2 ,while ifpis odd,p= 2 q+1, then
p= 2 q+ 1 =( 3 q− 1 )^2 +( 4 q− 4 )^2 −( 5 q− 4 )^2 ,ifq>1, while ifq=1, thenp= 3 = 42 + 52 − 62.
Returning to the inductive argument, let
m=a^21 +a 22 =b^21 +b 22 +b^23 = ··· =l 12 +l 22 +···+l^2 k,and alsom=a^2 +b^2 −c^2. Takingm′=m+c^2 we have
m′=a^2 +b^2 =a 12 +a^22 +c^2 =b^21 +b 2 +c^2 = ··· =l 12 +l^22 +···+l^2 k+c^2.This completes the induction.
(Gazeta Matematica ̆(Mathematics Gazette, Bucharest), 1980, proposed by M. Cava-
chi)
23.The property can be checked easily for small integers, which will constitute the base
case. Assuming the property true for all integers less thann, letFkbe the largest term
of the Fibonacci sequence that does not exceedn. The numbern−Fkis strictly less
thann, so by the induction hypothesis it can be written as a sum of distinct terms of the
Fibonacci sequence, sayn−Fk=
∑
jFij. The assumption on the maximality ofFk
implies thatn−Fk<Fk(this becauseFk+ 1 =Fk+Fk− 1 < 2 Fkfork≥2). It follows
thatFk =Fij, for allj. We obtainn=
∑
jFij+Fk, which gives a way of writingnas
a sum of distinct terms of the Fibonacci sequence.
24.We will prove a more general identity, namely,
Fm+n+ 1 =Fm+ 1 Fn+ 1 +FmFn, form, n≥ 0.