Редукция и индукция

[situs]

Я рассматриваю редукцию слова длины $2n$ на алфавите $\{a_1, a_2, \dots, a_n \}$. При каждой операции редукции происходит удаление одной буквы из слова. Допустим, есть такое условное (конкретика на самом деле сейчас не важна) утверждение: если слово редуцируется до слова $w = (ab)$, тогда объект $S$ имеет вид $S = s_1 + s_2$. Интересует способ доказательства такого вида утверждения и его общая формулировка.

Назовем слово $w = (ab)$ минимальным. Я могу доказать, что для минимального слова утверждение справедливо. И могу показать, что добавление одной буквы к слову не меняет вид объекта $S$. То есть получается метод индукции.

Подскажите, пожалуйста, как мне этот метод перевернуть на редукцию слова? Ведь в утверждении говориться о редукции, т.е. сокращении слова любой длины до минимального, а в доказательстве по индукции я добавляю букву к слову, начиная с минимального. Понятно, что это взаимообратные операции. Не очень понятно, что мне для этого нужно сделать и как это аккуратно сформулировать. Буду благодарен за ссылку на книжный пример с рассуждением подобного рода.

[arseniiv]

Сами себя запутали, всё нормально с индукцией. Предположим, что для слов длины меньше некоторой утверждение справедливо — тут ваше добавление буквы даст, что оно справедливо и для слов длины на один больше, получили верный индукционный переход. Ну и доказательство для минимального слова будет базой индукции. Или я чего-то не понял.

-- Вс мар 10, 2019 17:42:27 --

Ах да, индукция по длине слова.

[situs]

arseniiv

Да вроде Вы правильно всё поняли. Большое спасибо!

Правильно ли я понял? Будем доказывать утверждение индукцией по длине слова. База: слово $w = (ab)$ длины $m = 2$ имеет вид $S$. Индуктивный переход: утверждение верно для слова длины $m + 1$. Предположим, что для слова длины $n - 1$ утверждение справедливо. Тогда оно верно и для слова длины $n = n - 1 + 1$.

[arseniiv]

Я бы сказал, переход такой: если утверждение верно для слова длины $n\geqslant m$, то оно верно для слова длины $n+1$. Отдельно про длину $m+1$ говорить не нужно.