До­ка­жем ме­то­дом ма­те­ма­ти­че­ской ин­дук­ции. При   — оче­вид­но. В про­из­воль­ном слове w от n + 1 буквы рас­смот­рим первую слева букву, назовём её a, если она боль­ше не встре­ча­ет­ся в w, остав­ша­я­ся часть w яв­ля­ет­ся сло­вом от n букв и по пред­по­ло­же­нию ин­дук­ции имеет длину не боль­ше Общая длина w при этом не пре­вос­хо­дит

Если a встре­ча­ет­ся в w ещё хотя бы раз, то под­сло­ва, на ко­то­рые a раз­би­ва­ет w, не имеют общих букв. Иначе, убрав всё, кроме пер­вой a, буквы b, встре­ча­ю­щей­ся в раз­ных под­сло­вах и вто­рой буквы a, сто­я­щей между этими b, по­лу­чим слово abab, за­прещённое усло­ви­ем. Пусть всего w со­дер­жит k вхож­де­ний a, оно раз­би­ва­ет w на k (если по­след­няя буква w не a) или k − 1 (если по­след­няя буква w равна a) под­слов, каж­дое из ко­то­рых ис­поль­зу­ет не­пе­ре­се­ка­ю­ще­е­ся с дру­ги­ми мно­же­ство букв. Длина каж­до­го под­сло­ва оце­ни­ва­ет­ся по ин­дук­ции как удво­ен­ное число ис­поль­зо­ван­ных в нём раз­лич­ных букв, умень­шен­ное на 1. Всего в этих сло­вах за­дей­ство­ван­но n букв, по­это­му общая сум­мар­ная длина всех под­слов не пре­вос­хо­дит До­бав­ля­ем сюда k вхож­де­ний a, по­лу­чим, что длина w не пре­вос­хо­дит   — шаг ин­дук­ции до­ка­зан.

Ответ: