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

На любое натуральное число можно смотреть с двух точек зрения. Например, 3-три (количество), 3-третий (порядок). В курсе алгебры изучают порядковую теорию натуральных чисел. На множестве ℕ вводится отношение '(штрих) - “непосредственно следовать за”. Например, а' - элемент, непосредственно следующий за а.

Определение 54. Непустое множество ℕ с определённым на нём отношением ' (“непосредственно следующий за”) называется натуральным рядом чисел, а его элементы - натуральными числами, если выполняются следующие аксиомы, называемые аксиомами Пеано:

Р1: существует натуральное число, обозначаемое 1, которое непосредственно не следует ни за одним натуральным числом, то есть а'≠1, .

Р2: для любого натурального числа существует единственное натуральное число, непосредственно следующее за ним, то есть если а = b, то а' = b'.

Р3: любое натуральное число непосредственно следует не более чем за одним натуральным числом, то есть если а' =b ', то а =b.

Р4: пусть М⊆ℕ. Если 1М и из аМ всегда следует, что а'М, то М=ℕаксиома индукции.

Лемма 4. аа' ≠ а.

Доказательство. Пусть М – множество всех натуральных чисел а, для которых а'а => М ℕ. Покажем, что 1 М. По аксиоме (Р1): 1'≠1=> 1М. Пусть аМ =>а' ≠ а => (по (Р3)) (а')'а’’ => а'М. Таким образом, по аксиоме (Р4) М =ℕ => а' ≠ а, ℕ.

Лемма доказана.

Теорема 6 (теорема Евклида).Множество всех натуральных чисел бесконечно.

Теорема 7 (основная форма метода математической индукции).

Пусть утверждение Т истинно при n=1 и из истинности утверждения Т при n=k следует истинность утверждения Т при n=k+1. Тогда утверждение Т истинно для любого nℕ.

Доказательство. Пусть М - множество всех натуральных чисел, для которых утверждение Т истинно. Покажем, что М=ℕ. По заданному М: Мℕ. Так как Т истинно при n=1, то 1М. По условию теоремы Т истинно при n=k. Тогда по условию Т истинно при n=k+1=k' =>k'М. По Р4: М=ℕ => Т - истинно ℕ.

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

Теорема 8 (Обобщение первой формы метода математической индукции).

Пусть утверждение Т истинно при n=n0 и из истинности утверждения Т при n=k следует истинность утверждения Т при n=k+1. Тогда утверждение Т истинно для любого n .

Теорема 9 (вторая форма метода математической индукции).

Пусть утверждение Т истинно при n=1 и из истинности утверждения Т для любого натурального числа, меньшего k, следует истинность утверждения Т для k. Тогда утверждение Т истинно для любого nℕ.

Теорема 10 (обобщение второй формы метода математической индукции).

Пусть утверждение Т истинно при и из истинности утверждения Т для любого натурального числа, меньшего k и большего либо равного , следует истинность утверждения Т для k. Тогда утверждение Т истинно для любого n .

Замечание 11. Доказательство утверждений методом математической индукции состоит из трёх этапов:

1. Базис индукции. Проверим, что утверждение верно при n= 1 ()

2. Индукционное предположение. Предположим, что утверждение верно при n=k (для основной формы).

3. Индукционное доказательство. Докажем, что утверждение верно при n=k+1.