.15 Последовательности. Индукция.

Ошибка здесь состоит в том, что мы проверили базу для , но при доказательстве шага индукции от к мы явно пользуемся тем, что в множестве , для которого мы все доказываем, хотя бы три элемента, то есть что .

Действительно, смотрите внимательно, для того, чтобы в нашем доказательстве сделать вывод о том,

было необходимо, чтобы множества

и

зацеплялись хотя бы по элементу .

Но если , то в шаге индукции от к у нас будет два множества

и

и мы не сможем столь виртуозно сделать шаг, несмотря на то, что базу-то мы доказали.

Действительно, из того, что все элементы в множестве равны между собой (а там просто-напросто один элемент) и все элементы в множестве равны между собой, еще никак не следует, что все элементы в множестве

равны между собой.

Таким образом, мы не можем, обладая только базой индукции, и сделанным нами шагом индукции, доказать утверждение теоремы для множества из двух элементов мы не можем.

Вывод. Всегда нужно аккуратно следить, достаточно ли мы доказали в базе индукции. Это можно проверить очень легко. Если, обладая базой индукции и индукционным переходом, мы действительно можем сделать этот индукционный переход для любого , значит всё чисто и наше доказательство верное. А вот если мы неявно предполагаем что-то про в индукционном переходе (например, что или даёт остаток при делении на ), а при этом в базе индукции это никак не учтено, то такое доказательство по индукции будет неправильным.