Advanced book on Mathematics Olympiad

332 Methods of Proof

We do so by induction onn. The inductive argument will assume the property to be true
forn=k−1 andn=k, and prove it forn=k+1. Thus the base case consists of
n=0,Fm+ 1 =Fm+ 1 ; andn=1,Fm+ 2 =Fm+ 1 +Fm—both of which are true.
Assuming thatFm+k=Fm+ 1 Fk+FmFk− 1 andFm+k+ 1 =Fm+ 1 Fk+ 1 +FmFk,we
obtain by addition,

Fm+k+Fm+k+ 1 =Fm+ 1 (Fk+Fk+ 1 )+Fm(Fk− 1 +Fk),

which is, in fact, the same asFm+k+ 2 =Fm+ 1 Fk+ 2 +FmFk+ 1. This completes the
induction. Form=n, we obtain the identity in the statement.

25.Inspired by the previous problem, we generalize the identity to

Fm+n+p=Fm+ 1 Fn+ 1 Fp+ 1 +FmFnFp−Fm− 1 Fn− 1 Fp− 1 ,

which should hold form, n, p≥1. In fact, we can augment the Fibonacci sequence by
F− 1 =1 (so that the recurrence relation still holds), and then the above formula makes
sense form, n, p ≥0. We prove it by induction onp. Again for the base case we
considerp=0, with the corresponding identity

Fm+n=Fm+ 1 Fn+ 1 −Fm− 1 Fn− 1 ,

andp=1, with the corresponding identity

Fm+n+ 1 =Fm+ 1 Fn+ 1 +FmFn.

Of the two, the second was proved in the solution to the previous problem. And the
first identity is just a consequence of the second, obtained by subtractingFm+n− 1 =
FmFn+Fm− 1 Fn− 1 fromFm+n+ 1 =Fm+ 1 Fn+ 1 +FmFn. So the base case is verified. Now
we assume that the identity holds forp=k−1 andp=k, and prove it forp=k+1.
Indeed, adding

Fm+n+k− 1 =Fm+ 1 Fn+ 1 Fk+FmFnFk− 1 −Fm− 1 Fn− 1 Fk− 2

and

Fm+n+k=Fm+ 1 Fn+ 1 Fk+ 1 +FmFnFk−Fm− 1 Fn− 1 Fk− 1 ,

we obtain

Fm+n+k+ 1 =Fm+n+k− 1 +Fm+n+k

=Fm+ 1 Fn+ 1 (Fk+Fk+ 1 )+FmFn(Fk− 1 +Fk)−Fm− 1 Fn− 1 (Fk− 2 +Fk− 1 )

=Fm+ 1 Fn+ 1 Fk+ 2 +FmFnFk+ 1 −Fm− 1 Fn− 1 Fk.