Лекция: Теорема 1.

Над алфавитом мощностью m можно создать ровно mn слов длиною n.

Доказательство:

Воспользуемся методом полной математической индукции. Пусть — элементы (буквы) алфавита мощностью. Из этого алфавита можно создать слов длиной 1. Такими словами будут буквы этого алфавита. Для данное утверждение является правильным .

Допустим, что данное утверждение является правильным для, и покажем, что тогда оно выполняется и для. Предположим, число длины равняется. Чтобы создать все возможные слова длины, достаточно к каждому слову длины добавить в его конце последовательно каждую из букв алфавита. Таким образом, из каждого слова длины образуется разных слов длины. Таким образом, получаем все возможные слова длиною. Поскольку слов длиной является, то общее количество слов длиной будет. Таким образом, предположив истинность утверждения для, доказано, что оно является правильным для. Теорема доказана.