Применение метода математической индукции к решению задач на делимость натуральных чисел | Статья в журнале «Юный ученый»

Отправьте статью сегодня! Журнал выйдет 8 февраля, печатный экземпляр отправим 12 февраля.

Опубликовать статью в журнале

Автор:

Научный руководитель:

Рубрика: Математика: алгебра и начала анализа, геометрия

Опубликовано в Юный учёный №2 (2) май 2015 г.

Дата публикации: 02.05.2015

Статья просмотрена: 2535 раз

Библиографическое описание:

Баданин А. С., Сизова М. Ю. Применение метода математической индукции к решению задач на делимость натуральных чисел // Юный ученый. — 2015. — №2. — С. 84-86. — URL https://moluch.ru/young/archive/2/128/ (дата обращения: 26.01.2020).

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

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

Метод математической индукции мы находим в теории чисел. На заре теории чисел математики открыли многие факты индуктивным путем: Л. Эйлер и К. Гаусс рассматривали подчас тысячи примеров, прежде чем подметить числовую закономерность и поверить в нее. Но одновременно они понимали, сколь обманчивыми могут быть гипотезы, прошедшие «конечную» проверку. Для индуктивного перехода от утверждения, проверенного для конечного подмножества, к аналогичному утверждению для всего бесконечного множества необходимо доказательство. Такой способ предложил Блез Паскаль, который нашел общий алгоритм для нахождения признаков делимости любого целого числа на любое другое целое число (трактат «О характере делимости чисел).

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

Решение задач на доказательство истинности некоторого утверждения методом математической индукции состоит из четырех этапов (рис. 1):

mmi.png

Рис. 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 с.

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


Похожие статьи

Об использовании метода инварианта, основанного на идее...

Решения задач-головоломок с использованием четности и нечетности чисел отличаются логической

Решение задач на доказательство истинности некоторого утверждения методом математической

Для решения задачи вспомним признак делимости на 4 (25): если число...

Методические аспекты обучения доказательству студентов...

Поиски различных способов решения задач на доказательство формируют способность

Решение подобных задач в теории графов основано на общей схеме: по условию задачи

В связном плоском графе справедлива формула Эйлера: в — р + г = 2, где в — число вершин, р...

Оценки снизу для числа представлений в задачах аддитивной...

Число представлений натурального числа в виде суммы членов двух последовательностей, одна из которых является достаточно редкой, для большинства натуральных чисел в широком классе задач принимает лишь значение 0 и 1. Несмотря на это, как будет показано в данной...

Изложение теории делимости в УМК «Математика...»

Делимость — фундаментальное понятие алгебры, арифметики и теории чисел, связанное с операцией деления.

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

Построение формальной арифметики в рамках изучения...

Для любого натурального числа x существует другое натуральное число, обозначаемое x и называемое

В теории S можно ввести отношение порядка и понятие делимости.

Для доказательства непротиворечивости формальной арифметики помимо отношений W1(u, y) и...

Применение специальных задач для успешного выполнения...

Решение: По условию известно, что число имеет 6 делителей, следовательно, необходимо рассмотреть два случая

Запишите наименьшее натуральное число, которое при делении на 4, 9, 11, 25 дает в

Для решения задачи вспомним признак делимости на 4 (25): если число...

Элементы теории доказательств в курсе математической логики

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

К вопросу о реализации решения задачи открытого...

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

От Эвклида до Гёделя: аксиоматический метод в курсе...

Для любого натурального числа x существует другое натуральное число, обозначаемое x и называемое следующее за x.

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

Похожие статьи

Об использовании метода инварианта, основанного на идее...

Решения задач-головоломок с использованием четности и нечетности чисел отличаются логической

Решение задач на доказательство истинности некоторого утверждения методом математической

Для решения задачи вспомним признак делимости на 4 (25): если число...

Методические аспекты обучения доказательству студентов...

Поиски различных способов решения задач на доказательство формируют способность

Решение подобных задач в теории графов основано на общей схеме: по условию задачи

В связном плоском графе справедлива формула Эйлера: в — р + г = 2, где в — число вершин, р...

Оценки снизу для числа представлений в задачах аддитивной...

Число представлений натурального числа в виде суммы членов двух последовательностей, одна из которых является достаточно редкой, для большинства натуральных чисел в широком классе задач принимает лишь значение 0 и 1. Несмотря на это, как будет показано в данной...

Изложение теории делимости в УМК «Математика...»

Делимость — фундаментальное понятие алгебры, арифметики и теории чисел, связанное с операцией деления.

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

Построение формальной арифметики в рамках изучения...

Для любого натурального числа x существует другое натуральное число, обозначаемое x и называемое

В теории S можно ввести отношение порядка и понятие делимости.

Для доказательства непротиворечивости формальной арифметики помимо отношений W1(u, y) и...

Применение специальных задач для успешного выполнения...

Решение: По условию известно, что число имеет 6 делителей, следовательно, необходимо рассмотреть два случая

Запишите наименьшее натуральное число, которое при делении на 4, 9, 11, 25 дает в

Для решения задачи вспомним признак делимости на 4 (25): если число...

Элементы теории доказательств в курсе математической логики

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

К вопросу о реализации решения задачи открытого...

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

От Эвклида до Гёделя: аксиоматический метод в курсе...

Для любого натурального числа x существует другое натуральное число, обозначаемое x и называемое следующее за x.

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

Задать вопрос