IMO 1992 LL FRG18

Fibonacci numbers are defined as follows: F1 = F2 = 1, Fn+2 =

imolonglistmathematicsolympiad

IMO 1992 LL FRG18

Origin: FRG

Problem

Fibonacci numbers are defined as follows: F1 = F2 = 1, Fn+2 = Fn+1+Fn, n \geq1. Let an be the number of words that consist of n letters 0 or 1 and contain no two letters 1 at distance two from each other. Express an in terms of Fibonacci numbers.