1. Полная и неполная индукция

Определения и обозначения

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

База индукции — проверка утверждения для начального значения натурального параметра. Она подтверждает первое звено рассуждения, например случай n = 1, без которого переходы не образуют доказанную цепочку.

Индукционное предположение — допущение, что утверждение верно для произвольного значения n = k. Это не итог доказательства, а временное условие, которое используют внутри одного шага рассуждения.

Индукционный переход — доказательство истинности утверждения для n = k + 1 из предположения для n = k. Он показывает, почему верность одного звена приводит к верности следующего.

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

Как это устроено

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

В полной индукции база показывает, что цепочка начинается с верного утверждения. Индукционный переход обеспечивает движение от каждого звена к следующему: из истинности для k следует истинность для k + 1. Если оба шага выполнены, утверждение верно для всех значений, начиная с базы.

В переходе исходное n заменяют на произвольное k, потому что нужно рассмотреть не один конкретный случай, а любое звено цепочки. Сначала формулируют предположение для k, затем преобразуют выражение или условие для k + 1. Полученный вывод относится к любому допустимому k и потому охватывает все переходы.

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

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

Сравнение полной и неполной индукции

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

Проверка нескольких примеров может быть первым этапом работы, но её следует отличать от полной индукции. Для доказательства ищите две обязательные части: базу и переход от k к k + 1.

Разбор задач

Задача 1. Сумма первых натуральных чисел

Докажем, что 1 + 2 + 3 + ... + n = n(n + 1)/2 для любого натурального n. Формула должна быть верна не для нескольких выбранных чисел, а для каждого n. Поэтому применим полную индукцию.

1. При n = 1 левая часть равна 1, а правая — 1 · 2/2 = 1, значит, база выполнена.
2. Предположим, что 1 + 2 + ... + k = k(k + 1)/2. Для следующего значения получаем 1 + 2 + ... + k + (k + 1) = k(k + 1)/2 + k + 1.
3. Вынесем k + 1: (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2. Это и есть формула для n = k + 1.

Ответ: равенство доказано для любого натурального n.

Задача 2. Делимость выражения

Докажем, что 8ⁿ − 1 делится на 7 для любого натурального n. Основа перехода — представить выражение для k + 1 через выражение для k. Тогда известную делимость можно использовать напрямую.

1. При n = 1 имеем 8 − 1 = 7, число делится на 7.
2. Пусть 8ᵏ − 1 делится на 7. Представим 8ᵏ⁺¹ − 1 = 8(8ᵏ − 1) + 7.
3. Оба слагаемых делятся на 7: первое по предположению, второе очевидно. Значит, делимость сохраняется для k + 1.

Ответ: 8ⁿ − 1 делится на 7 при любом натуральном n.

Задача 3. Проверка гипотезы

Рассмотрим утверждение: n² + n + 41 — простое число для всех натуральных n. Первые значения действительно могут создать впечатление закономерности. Однако это неполная индукция, поэтому проверим случай, который нарушает утверждение.

1. При n = 1 получаем 43, при n = 2 — 47, а при n = 3 — 53; эти числа простые.
2. Возьмём n = 40: 40² + 40 + 41 = 1681.
3. Так как 1681 = 41², получено составное число. Значит, одного контрпримера достаточно для опровержения утверждения.

Ответ: гипотеза неверна; проверка первых случаев не заменила доказательство.

Типичные ошибки

Проверять только первые значения. Так получают неполную индукцию, а не доказательство для всех n. Проверьте, есть ли рассуждение для произвольного k и перехода к k + 1.

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

Не использовать предположение для k. Самостоятельное вычисление случая k + 1 ещё не показывает связь соседних случаев. Найдите в решении место, где явно применяется утверждение для k.

Считать предположение доказанным фактом. Оно временно принимается для произвольного k и служит условием перехода. После него всё равно нужны база и вывод о верности утверждения для всех значений.

Связь с другими темами

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

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

Тема связана с логикой: проверка примеров, гипотеза и доказательство имеют разный статус. Умение различать их помогает не делать необоснованных общих выводов.

Что запомнить

• Полная индукция состоит из базы и индукционного перехода.
• В базе проверяют утверждение для начального значения.
• В индукционном переходе доказывают переход от k к k + 1.
• Индукционное предположение принимают для произвольного k.
• Проверка первых нескольких случаев не заменяет доказательство.
• Неполная индукция помогает находить закономерности и выдвигать гипотезы.
• Контрпример опровергает общее утверждение.