Назовем слова, которые можно получить, достижимыми. Всего существует различных слов длины поэтому достаточно доказать, что количество достижимых слов длины равно Докажем это утверждение по индукции.

База индукции. Для и это легко проверяется: А АА, А АБ.

Шаг индукции. Пусть для всех длин, не превосходящих утверждение верно. Посмотрим, как можно получить слово длины

1.

из слова длины применив операцию а): W АW

2.

из слова длины применив операцию б): W WБ

3.

из слова длины применив операцию в): W БWА

Слов 1-го и 2-го типа по а слов 3-го типа При этом слова 3-го типа не могут совпадать со словами 1-го и 2-го типа. А вот множества слов 1-го и 2-го типа пересекаются. Их общие слова имеют вид АБ. Докажем, что слова (которые находятся между буквами А и Б) — это все достижимые слова длины Понятно, что если — достижимое слово, то за две операции из него можно получить АБ. С другой стороны, если слово Б достижимое, то посмотрим, как оно было получено. Если проделать все те же операции, но пропустить приписывание последней буквы Б, то будет получено слово значит, оно достижимое.

Таким образом, общих слов 1-го и 2-го типа столько же, сколько достижимых слов длины то есть Следовательно, количество слов длины равно что и требовалось доказать.