В математических олимпиадах часто встречаются достаточно трудные задачи на доказательство делимости натуральных чисел. Перед школьниками возникает проблема: как найти универсальный математический метод, позволяющий решать подобные задачи?
Оказывается, большинство задач на доказательство делимости можно решать методом математической индукции, но в школьных учебниках уделяется очень мало внимания этому методу, чаще всего приводится краткое теоретическое описание и разбирается несколько задач.
Метод математической индукции мы находим в теории чисел. На заре теории чисел математики открыли многие факты индуктивным путем: Л. Эйлер и К. Гаусс рассматривали подчас тысячи примеров, прежде чем подметить числовую закономерность и поверить в нее. Но одновременно они понимали, сколь обманчивыми могут быть гипотезы, прошедшие «конечную» проверку. Для индуктивного перехода от утверждения, проверенного для конечного подмножества, к аналогичному утверждению для всего бесконечного множества необходимо доказательство. Такой способ предложил Блез Паскаль, который нашел общий алгоритм для нахождения признаков делимости любого целого числа на любое другое целое число (трактат «О характере делимости чисел).
Метод математической индукции используется, чтобы доказать путем рассуждений истинность некоего утверждения для всех натуральных чисел или истинность утверждения начиная с некоторого числа n.
Решение задач на доказательство истинности некоторого утверждения методом математической индукции состоит из четырех этапов (рис. 1):
Рис. 1. Схема решения задачи
1. Базис индукции. Проверяют справедливость утверждения для наименьшего из натуральных чисел, при котором утверждение имеет смысл.
2. Индукционное предположение. Предполагаем, что утверждение верно для некоторого значения k.
3. Индукционный переход. Доказываем, что утверждение справедливо для k+1.
4. Вывод. Если такое доказательство удалось довести до конца, то, на основе принципа математической индукции можно утверждать, что утверждение верно для любого натурального числа n.
Рассмотрим применение метода математической индукции к решению задач на доказательство делимости натуральных чисел.
Пример 1. Доказать, что число 5
кратно 19, где n — натуральное число.
Доказательство:
1) Проверим, что эта формула верна при n = 1: число 
=19 кратно 19.
2) Пусть эта формула верна для n = k, т. е. число 
кратно 19.
3) Докажем, что формула верна и для n = k + 1, т. е.
кратно 19. Действительно, первое слагаемое делится на 19 в силу предположения (2); второе слагаемое тоже делится на 19, потому что содержит множитель 19.
4) Оба условия принципа математической индукции выполнены, следовательно, предложение истинно при всех значениях n.
Пример 2. Доказать, что сумма кубов трех последовательных натуральных чисел делится на 9.
Доказательство:
Докажем утверждение: «Для любого натурального числа n выражение n3+(n+1)3+(n+2)3 кратно 9.
1) Проверим, что эта формула верна при n = 1: 13+23+33=1+8+27=36 кратно 9.
2) Пусть эта формула верна для n = k, т. е. k3+(k+1)3+(k+2)3 кратно 9.
3) Докажем, что формула верна и для n = k + 1, т. е. (k+1)3+(k+2)3+(k+3)3 кратно 9. (k+1)3+(k+2)3+(k+3)3=(k+1)3+(k+2)3+ k3+ 9k2+27 k+ 27=(k3+(k+1)3+(k+2)3)+9(k2+3k+ 3).
Полученное выражение содержит два слагаемых, каждое из которых делится на 9, таким образом, сумма делится на 9.
4) Оба условия принципа математической индукции выполнены, следовательно, предложение истинно при всех значениях n.
Пример 3. Доказать, что при любом натуральном n число 32n+1+2n+2 делится на 7.
Доказательство:
1) Проверим, что эта формула верна при n = 1: 32*1+1+21+2 = 33+23=35, 35 кратно 7.
2) Пусть эта формула верна для n = k, т. е. 32k+1+2k+2 делится на 7.
3) Докажем, что формула верна и для n = k + 1, т. е.
32(k+1)+1+2(k+1)+2=32k+1·32+2k+2·21=32k+1·9+2k+2·2=32k+1·9+2k+2·(9–7)=(32k+1+2k+2)·9–7·2k+2.Т. к. (32k+1+2k+2)·9 делится на 7 и 7·2k+2 делится на 7, то и их разность делится на 7.
4) Оба условия принципа математической индукции выполнены, следовательно, предложение истинно при всех значениях n.
Многие задачи на доказательство в теории делимости натуральных чисел удобно решать с применением метода математической индукции, можно даже сказать, что решение задач данным методом вполне алгоритмизировано, достаточно выполнить 4 основных действия. Но универсальным этот метод назвать нельзя, т. к. присутствуют и недостатки: во-первых, доказывать можно только на множестве натуральных чисел, а во-вторых, доказывать можно только для одной переменной.
Для развития логического мышления, математической культуры этот метод является необходимым инструментом, ведь ещё великий русский математик А. Н. Колмогоров говорил: «Понимание и умение правильно применять принцип математической индукции, является хорошим критерием логической зрелости, которая совершенно необходима математику».
Литература:
1. Виленкин Н. Я. Индукция. Комбинаторика. — М.: Просвещение, 1976. — 48 с.
2. Генкин Л. О математической индукции. — М., 1962. — 36 с.
3. Соломинский И. С. Метод математической индукции. — М.: Наука, 1974. — 63с.
4. Шарыгин И. Ф. Факультативный курс по математике: Решение задач: Учеб.пособие для 10 кл. сред.шк. — М.: Просвещение, 1989. — 252 с.
5. Шень А. Математическая индукция. — М.: МЦНМО,2007.- 32 с.
