Снова считаем подмножества

Доказывая теорему 5.1. мы неявно пользовались методом математической индукции. Теперь пришло время применить его явно. Итак, мы подозреваем, что число всех подмножеств множества из n элементов равно . Если n = 1, то . То есть мы имеем пустое подмножество и подмножество, состоящее только из одного элемента – результат получился верный. Допустим, что множество состоит из n – 1 элементов, тогда общее количество подмножеств равно . Полагаем это утверждение истинным.

Добавление еще одного элемента в исходное множество приведет к тому, что появятся новые подмножества. Всего таких новых подмножеств будет , поскольку мы можем добавить новый элемент в каждое «старое» подмножество (в том числе, и в пустое множество). В результате получим, что общее количество подмножеств дополненного множества равно:

.

Таким образом, наш результат подтверждает теорему 5.1.