MathDB
no of words of length n is equal to \frac{2^n +2\cdot (-1)^n}{3}

Source: Czech And Slovak Mathematical Olympiad, Round III, Category A 1999 p4

February 20, 2020
combinatorics

Problem Statement

In a certain language there are only two letters, AA and BB. We know that (i) There are no words of length 11, and the only words of length 22 are ABAB and BBBB. (ii) A segment of length n>2n > 2 is a word if and only if it can be obtained from a word of length less than nn by replacing each letter BB by some (not necessarily the same) word. Prove that the number of words of length nn is equal to 2n+2⋅(−1)n3\frac{2^n +2\cdot (-1)^n}{3}
Back to ProblemsView on AoPS