IMO 1974 SL 12

Problem

II 6 (USS 1) In a certain language words are formed using an alphabet of three letters. Some words of two or more letters are not allowed, and any two such distinct words are of different lengths. Prove that one can form a word of arbitrary length that does not contain any nonallowed word.

Solution

We say that a word is good if it doesn’t contain any nonallowed word. Let an be the number of good words of length n. If we prolong any good word of length n by adding one letter to its end (there are 3an words that can be so obtained), we get either (i) a good word of length n + 1, or (ii) an (n + 1)-letter word of the form XY , where X is a good word and Y a nonallowed word. The number of words of type (ii) with word Y of length k is exactly an+1−k; hence the total number of words of kind (ii) doesn’t exceed an−1+ \cdot \cdot \cdot + a1 + a0 (where a0 = 1). Hence an+1 \geq3an −(an−1 + \cdot \cdot \cdot + a1 + a0), a0 = 1, a1 = 3. (1)

We prove by induction that an+1 > 2an for all n. For n = 1 the claim is trivial. If it holds for i \leqn, then ai \leq2i−nan; thus we obtain from (1) an+1 > an  3 −1 2 −1 22 −\cdot \cdot \cdot −1 2n 

2an. Therefore an \geq2n for all n (moreover, one can show from (1) that an \geq (n + 2)2n−1); hence there exist good words of length n. Remark. If there are two nonallowed words (instead of one) of each length greater than 1, the statement of the problem need not remain true.