Куликова Н.С.

Теоретическая составляющая темы «Метод

математической индукции»

Саратов

 2017

Определение 1. Под простым высказыванием понимается предложение, утверждающее что-то о чем-либо. Рассматривая простое высказывание в определенных условиях времени и места, мы можем сказать истинно или ложно, другими словами, что его логическое значение есть «истина» или «ложь» [2].

Определение 2. Отрицанием высказывания  называется новое высказывание, обозначаемое символом  (читается: «неверно, что » или, короче, «не »), которое считается истинным, если   ложно, и ложным, если  истинно [2].

Определение 3. Конъюнкцией двух высказываний  называется новое высказывание, обозначаемое символом  (читается: «»), которое считается истинным, если оба высказывания  истинны, и ложным, если хотя бы одно из них ложно [2].

Определение 4. Дизъюнкцией двух высказываний  называется новое высказывание, обозначаемое символом  (читается: «»), которое считается истинным, если хотя бы одно из высказываний  истинно, и ложным, если оба они ложны [2].

Определение 5. Импликацией двух высказываний  называется новое высказывание, обозначаемое символически  (читается: «»), которое считается ложным, если  ложно, и истинным при всех других логических значениях высказываний   [2].

Определение 6. Эквивалентностью двух высказываний  называется новое высказывание, обозначаемое символом  (читается.: «» или, короче: «» ), которое считается истинным, когда, оба высказывания  либо истинны, либо ложны, и ложным в остальных случаях [2].

Определение 7.  Множество – совокупность каких–либо предметов или объектов произвольной природы, обладающих некоторым общим свойством. Множества обозначаются заглавными буквами латинского алфавита.

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

Замечание 1. Основное отношение между элементом a и содержащим его множеством  обозначается так   (a есть элемент множества ; или a принадлежит  , или   содержит a). 

Определение 9.  Два множества   называются равными, если они состоят из одних и тех же элементов, т. е. если каждый элемент множества   принадлежит   и, обратно, каждый элемент  принадлежит . Тогда пишут  .

Определение 10. Пересечением двух множеств   (обозначается  ) называется новое множество, состоящее из элементов принадлежащих  одновременно. Распространяется на 3 и более множеств.

Определение 11. Объединением двух множеств  (обозначается  ) называется новое множество, состоящее из элементов принадлежащих хотя бы одному из множеств. Распространяется на 3 и более множеств.

Определение 12. Разностью множеств  (обозначается ) называется новое множество, состоящее из элементов, принадлежащих множеству  и не принадлежащих множеству .

Определение 13. Пусть   - часть множества . Дополнением множества  относительно  называется множество элементов из , не принадлежащих к   т. е.    [5].

Определение 14. Множество  называется подмножеством множества  (), если .

Определение 15. Выражение «существует» называется квантором существования, обозначается ∃. Выражение «для всех» или «для любых» называется квантором общности и обозначается ∀.

Определение 16. Множество  называется индуктивным, если                .

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

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

Теорема 1. (Метод математической индукции). В основе метода математической индукции лежит принцип математической индукции, заключающийся в следующем: Утверждение справедливо для всякого натурального , если:

1. Оно справедливо для  .
2. Из справедливости утверждения для какого-либо произвольного натурального   следует его справедливость для .

Доказательство. Предположим противное, т.е. предположим, что утверждение справедливо не для всякого натурального  . Тогда существует такое натуральное  , что

1. Утверждение для   несправедливо.
2. Для всякого , меньше , утверждение справедливо (иными словами,  есть первое натуральное число, для которого утверждение несправедливо).

Очевидно, что , так как для  утверждение справедливо (условие 1). Следовательно,  – натуральное число. Выходит, что для натурального числа  утверждение справедливо, а для следующего натурального числа m оно не справедливо. Это противоречит условию 2 .Что и требовалось доказать [4].

Замечание 2. Часто первый пункт метода математической индукции носит название база индукции, а второй пункт метода математической индукции носит название индуктивный переход.

Замечание 3. Доказательство, основанное на принципе математической индукции, называется доказательством методом математической индукции. Такое доказательство должно состоять из двух частей, из доказательства двух самостоятельных теорем: Утверждение справедливо для  . Утверждение справедливо для , если оно справедливо для , где  – произвольное натуральное число. Если обе эти теоремы доказаны, то на основании принципа математической индукции утверждение справедливо для всякого натурального   [4].

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

Теорема 2. Всякое натуральное число равно следующему за ним натуральному числу.

Доказательство. Доказательство проведем методом математической индукции. Предположим, что

                                                                                               (1)

Докажем, что

.                                                                                        (2)

Действительно, прибавив к каждой части равенства (1) по 1, получим равенство (2). Выходит, что если утверждение справедливо для , то оно справедливо и для  . Теорема доказана [4].

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

Определение 22. Числовую последовательность, каждый член которой, начиная со второго, равен сумме предыдущего члена и одного и того же числа , называют арифметической прогрессией, а число  – разностью арифметической прогрессии.

Определение 23. Числовую последовательность, все члены которой отличны от 0 и каждый член, начиная со второго, получается из предыдущего члена умножением на одно и то же число , называют геометрической прогрессией, а число  – знаменателем геометрической прогрессии.

Теорема 7. Формула общего члена арифметической прогрессии  такова:

Доказательство. Докажем это пользуясь методом математической индукции. Если  , то равенство, полученное при подстановке верно. Пусть данная формула верна для . Докажем ее справедливость для . Имеем . Теорема доказана.

Теорема 8. -й член арифметической прогрессии может быть вычислен по формуле , где   – первый член прогрессии.

Доказательство. Если , то равенство, полученное при подстановке верно.  Пусть данная формула верна для , т. е. . Докажем ее справедливость для . Имеем . Действительно, . Теорема доказана.

Теорема 9. Сумму  членов арифметической прогрессии можно вычислить по формуле  

Доказательство. Если , то . Равенство верно. Пусть данная формула верна для , т. е. . Докажем ее справедливость для . Имеем . Действительно,  =  =   +  =  +  +  =  +  +  +  = . Теорема доказана.

Теорема 10. -член геометрической прогрессии может быть вычислен по формуле

Доказательство. Если , то - верное тождество.  Пусть данная формула верна для , т. е. . Докажем ее справедливость для . Имеем . Действительно, = =  = . Теорема доказана.

Теорема 11. Сумму  членов геометрической прогрессии можно найти по формуле .

Доказательство. Если , то  - верное тождество. Пусть данная формула верна для , т. е. . Действительно, =

. Терема доказана.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Виленкин, Н. Я. Индукция. Комбинаторика / Н. Я. Виленкин. Москва : Изд-во «Просвещение», 1976. 48 с.
2. Пензов, Ю. Е. Элементы математической логики и теории множеств / Ю. Е. Пензов. Саратов : Изд-во Саратовского университета, 1968. 144 с.
3. Завало, С. Т. Элементарная алгебра / С. Т. Завало. М. : Изд-во «Просвещение», 1964. 304 с.
4. Соминский, И. С. О математической индукции / И. С. Соминский, Л. И. Головина, И. М. Яглом. М. : Изд-во «Наука», 1967.  144 с.
5. Бурбаки, Н. Теория множеств / Н. Бурбаки. Москва : Изд-во «Мир», 1963. 144 с.