Метод математической индукции: теоретические аспекты
проект по математике (10 класс) на тему

Д. Е. Чернецов

МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ: ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ

Методическое пособие

Саратов, 2016

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

Определение 1. Высказывание – это повествовательное предложение, о котором можно говорить, что оно истинно или ложно. Они обозначаются заглавными латинскими буквами.

Определение 2. Отрицанием высказывания А называется новое высказывание, истинное тогда и только тогда, когда А ложно. Обозначается . Читается как «не А», «неверно, что А».

Определение 3. Конъюнкцией высказываний А и В называется новое высказывание, истинное тогда и только тогда, когда оба высказывания А и В истинны. Обозначается . Читается как «А и В».

Определение 4. Дизъюнкцией высказываний А и В называется новое высказывание, истинное тогда и только тогда, когда хотя бы одно из высказываний А или В истинно. Обозначается . Читается как «А или В».

Определение 5. Импликацией высказываний А и В называется новое высказывание, ложное тогда и только тогда, когда А – истинно, а В – ложно. Обозначается . Читается как «из А следует В», «А влечёт за собой В», «из А вытекает В».

Определение 6. Эквиваленцией высказываний А и В называется новое высказывание, истинное тогда и только тогда, когда высказывания А и В имеют одинаковое истинностное значение. Обозначается АВ. Читается как «А эквивалентно В», «А тогда и только тогда, когда В», «А в том и только в том случае, когда В» [2].

Определение 7. Множество – это совокупность объектов одной природы. Они обозначаются большими латинскими буквами. Элементы множества обозначаются малыми латинскими буквами.

Замечание 1. Высказывание «элемент а принадлежит множеству А» или «а – элемент множества А» символически записывается так:  [3].

Определение 8. Объединением множеств А1, А2, …, Аn называется новое множество, состоящее из всех элементов, принадлежащих какому-либо из данных множеств А1, А2, …, Аn и обозначаемое .

Определение 9. Пересечением множеств А1, А2, …, Аn называется новое множество, состоящее из всех элементов, принадлежащих одновременно всем данным множествам А1, А2, …, Аn и обозначаемое  [4].

Определение 10. Множества А и В называются равными, если они состоят из одних и тех же элементов, т. е.     .

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

Теорема 1. А = В  А    В.

Доказательство. А = В      А    В. Что и требовалось доказать.

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

Определение 13. Множество E ⊂ R называется индуктивным, если                x ∈ E  x + 1 ∈ E.

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

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

Теорема 2. (Принцип математической индукции). Пусть E ⊂ N удовлетворяет условиям: 1) 1 ∈ E; 2) n ∈ E ⇒ n + 1 ∈ E. Тогда E = N.

Доказательство. Из условия следует, что E индуктивно, следовательно, N ⊂ E. Отсюда N = E.

Замечание 2. Принцип математической индукции формулируют часто следующим образом. Пусть некоторое свойство P(x) выполнено для x = 1, и из условия, что P(x) выполнено, следует, что P(x + 1) тоже выполнено. Тогда P(x) справедливо для ∀ x ∈ N [5].

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

Замечание 3. Такое доказательство необходимо должно состоять из двух частей, из доказательства двух самостоятельных теорем.

1. Утверждение справедливо для n = 1.
2. Если утверждение справедливо для n = k, то оно справедливо и для n = k + 1, ∀ k ∈ N.

Если обе теоремы доказаны, то на основании принципа математической индукции утверждение справедливо ∀ n ∈ N [6].

В качестве примера докажем некоторые теоремы элементарной алгебры и комбинаторики.

Теорема 3. Квадрат многочлена равен сумме квадратов всех его членов, сложенной со всевозможными их удвоенными произведениями, т. е.   ()2 =  + 2(a1a2 + a1a3 + … + an-1an).                                               (1)

Доказательство. 

1. Для n = 2 данная формула примет вид (a1 + a2)2 = . Данная формула, известная ещё из школьного курса математики седьмого класса, называется квадратом суммы. Именно поэтому она очевидна.
2. Допустим, что для n = k – 1 формула (1) верна, т. е.                    ()2 =  + 2S, где S – сумма всевозможных попарных произведений, составленных из a1, a2, …, ak-1. Докажем, что формула (1) верна для n = k, т. е. ()2 =  + 2S1, где S1 – сумма всевозможных попарных произведений, составленных из a1, a2, …, ak. Несложно заметить, что S1 = S + (a1 + a2 + … + ak-1)ak. Действительно, ()2 = [(a1 + a2 + … + ak-1) + + ak)2 = (a1 + a2 + … + ak-1)2 + 2(a1 + a2 + … + ak-1)ak +  =  + 2S + + + 2(a1 + a2 + … + ak-1)ak =  + 2S1.

Таким образом, доказаны две теоремы, а значит имеет место равенство ()2 =  + 2(a1a2 + a1a3 + … + an-1an). Что и требовалось доказать.

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

Определение 16. Если ∀ по какому-либо правилу f ставится в соответствие , то указанное соответствие называется функцией , заданной на множестве Х.

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

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

Теорема 4. n-й член арифметической прогрессии может быть вычислен по формуле an = a1 + (n – 1)d, где а1 – первый член прогрессии.

Доказательство.

1. При n = 1 получаем верное тождество: а1 = а1. Следовательно для     n = 1 формула верна.
2. Предположим, что формула верна для n = k, т. е. ak = a1 + (k – 1)d. Теперь пусть n = k + 1. Тогда необходимо доказать, что ak+1 = a1 + kd. Действительно, ak+1 = ak + d = a1 + (k – 1)d + d = a1 + kd. Что и требовалось доказать.

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

Доказательство.

1. Пусть n = 1. S1 =  = . Получили верное равенство.
2. Пусть данная формула верна для n = k, т. е. Sk = . Тогда докажем, что Sk+1 = . В самом деле,  =                     =  =  = Sk +  = Sk +  +  = Sk +  +  + d = Sk +  + d = Sk +  = Sk+1. Что и требовалось доказать.

Замечание 4. Пользуясь теоремами 4 и 5, несложно убедиться в том, что Sn =

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

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

Доказательство.

1. Пусть n = 1. Тогда получаем верное тождество: b1 = b1.
2. Пусть данная формула верна для n = k: . Докажем эту формулу для    n = k + 1, т. е. необходимо доказать, что . Действительно, = bkq =  = . Что и требовалось доказать.

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

Доказательство.

1. Пусть n = 1. Тогда . Очевидно.
2. Предположим, что формула имеет место для n = k. Тогда докажем, что . В самом деле, =        . Что и требовалось доказать.

Докажем методом математической индукции теоремы, связанные с нахождением числа размещений, перестановок, сочетаний [8].

Определение 20. Размещением из n элементов по k элементам называется упорядоченное подмножество данного n множества, содержащее k элементов. Число всех возможных размещений из n элементов по k элементам обозначается .

Определение 21. Факториал числа n – это произведение всех натуральных чисел от 1 до n включительно, т. е. . По договорённости 0! = 1.

Теорема 8. Число всех возможных размещений из n элементов по k элементам можно вычислить по формуле

Доказательство.

Докажем данную теорему индукцией по k.

1. Несложно заметить, что , и тогда формула верна при k = 1.
2. Предположим, что . Нам нужно доказать, что . Действительно, для получения всех размещений из n элементов по m + 1 элементу достаточно взять все размещения из n элементов по m элементам и к каждому из них приписать в конце каждый из оставшихся n – m элементов. Выходит, что .

Замечание 5. Также число всех возможных размещений из n элементов по k элементам можно вычислить по формуле .

Определение 22. Перестановкой из n элементов называется размещение из n элементов по n элементам. Число всех возможных перестановок из n элементов обозначается Pn.

Теорема 9. Число всех возможных перестановок из n можно вычислить по формуле Pn = n!

Доказательство.

1. Несложно заметить, что P1 = 1, а значит для n = 1 формула верна.
2. Пусть данная формула верна при n = k. Тогда докажем, что              Pk+1 = (k + 1)! Из данных k + 1 элементов a1, a2, …, ak, ak+1 возьмём только первые k элементов и составим из них все возможные перестановки. По предположению индукции таких перестановок будет k! В каждой из этих перестановок поставим элемент ak+1 последовательно перед 1-м элементом, потом перед 2-м элементом, …, перед k-м элементом, после k-ого элемента. Этим путём мы из одной перестановки из k элементов получим k + 1 перестановок из k + 1 элементов. Тогда всего имеем: Pk+1 = k!(k + 1) =  (k + 1)!

Замечание 6. В целом, для доказательства теоремы 9 можно было воспользоваться определением 22: Pn =

Определение 23. Сочетанием из n элементов по k элементам называется подмножество данного n множества, содержащее k элементов. Число всех возможных сочетаний из n элементов по k элементам обозначается .

Теорема 10. Число всех возможных сочетаний из n элементов по k элементам .

Доказательство.

1. Пусть k = 1.  Справедливость формулы, таким образом, доказана.
2. Для продолжения доказательства произведём тождественные преобразования над данной формулой. Пусть формула верна для k = m. Докажем, что данная формула также верная и для k = m + 1. Нам нужно доказать, что . Действительно, .

Замечание 7. На практике для нахождения числа всех возможных сочетаний из n элементов по k элементам удобно пользоваться формулой .

Теорема 11 (Бином Ньютона).

Доказательство.

1. Так как любое число, отличное от нуля, в нулевой степени равно 1, то (a + b)0 = 1 = . Таким образом, формула верна.
2. Пусть . Тогда

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