Индуктивный переход

Индуктивное предположение.

База индукции.

При n = 5 верно неравенство

т. е. 32 > 25.

Допустим, что при n = k верно неравенство .

Пусть n = k + 1, нужно доказать, что

. Но

так как если что и требовалось доказать.

Пример 4.

На плоскости даны n прямых. Доказать, что куски плоскости, на которые эти прямые её разбивают, можно так покрасить белой и черной краской, чтобы никакие два участка, имеющие хотя бы одно общее ребро, не были покрашены в один и тот же цвет. Такая раскраска называется правильной.

Решение. Если у правильно раскрашенной плоскости поменять цвета на противоположные, раскраска останется правильной.

1. При n = 1 плоскость можно правильно раскрасить.

2. Предположим, что при n = k плоскость можно правильно раскрасить.

3. Пусть на плоскости проведены (k + 1)прямых.

Временно удалим произвольную прямую, оставив k прямых. По индуктивному предположению правильная раскраска существует. Теперь добавим удалённую прямую. Она делит плоскость на две полуплоскости, каждая из которых раскрашена правильно. И только участки, которые разделила добавленная прямая, окрашены в один цвет. Поменяем в любой из полуплоскостей цвета на противоположные, раскраска останется правильной, а нарушения исчезнут.

Пример 5. Найти ошибку в рассуждении.

Докажем, что любые п натуральных чисел равны друг другу.

1. Одно число, очевидно, равно себе самому.

2. Пусть любые k натуральных чисел равны друг другу.

3. Рассмотрим (k +1) натуральных чисел. Удалим из этого множества чисел любое число. Оставшиеся k чисел равны друг другу в силу индуктивного предположения. Добавим удаленное число и удалим любое из k чисел, равных между собой. В силу индуктивного предположения данные k чисел равны друг другу. Следовательно, все (k + 1) чисел равны между собой, утверждение доказано.

Решение. База индукции должна начинаться с п = 2, два произвольных натуральных числа не обязаны быть равными.