Метод математической индукции
ЛЕКЦИЯ В1
Введение
Законотворчество
Законотворчество –это деятельность законодательных органов государственной власти, направленное на создание, изменение и отмену законов.
Стадии законотворчества:
1. Подготовительный этап:
- принятие решения о разработке проекта акта;
- подготовка проекта;
- обсуждение, согласование и доработка проекта.
2. Нормотворческий этап (законотворческий):
- внесение проекта на обсуждение законотворческого органа;
- обсуждение проекта;
- принятие и опубликование закона.
Краткое содержание лекции
· Что такое метод математической индукции
· Примеры доказательств по методу математической индукции
Метод математической индукции – одно из мощных средств доказательства теорем.
Пусть P (n) - некоторое утверждение (формула, теорема), которое зависит от значения натурального n. Для некоторых n утверждение P (n) может быть ложным, для других – истинным. ММИ применяется для доказательства истинности P (n) для всех натуральных n, начиная, с некоторого n 0 ³ 1.
|
|
Примеры утверждений P (n).
Пример 1. Если а 1, …, ап > 0, то (среднее арифметическое п положительных вещественных чисел не меньше их среднего геометрического). Это утверждение верно для всех п ³ 1.
Пример 2. Среди любых п натуральных чисел обязательно найдутся 2, разность которых делится на 1000. Это утверждение верно для любого п ³ 1001.
Пример 3. Сумма 71 + 72 + … +7 п делится на 100.
Это утверждение верно для п = 4, 8, 12, …, 4 m, … и ложно для остальных п.
Утверждения 1 и 3 доказываются ММИ. Утверждение 2 доказывается с помощью принципа Дирихле.
Доказательство истинности P (n) для всех п ³ п 0 основано на принципе, который формулируется так.
Принцип индукции (классический принцип индукции). Пусть P(n) таково, что P(п0) - истинное утверждение и из истинности P(k) следует истинность P(k+1). Тогда P(n) истинно для всех п ³ п0.
Эквивалентная формулировка принципа индукции (расширенный принцип индукции):
1. Пусть P (n 0) – истинное утверждение.
2. Из истинности P (n) для всех n = п 0, п 0+1, п 0+2, …, k, следует истинность P (k +1).
Тогда P (n) истинно для всех n ³ п 0.
Доказательство по методу математической индукции проходит в три этапа
· База индукции. Доказывается истинность .
· Шаг индукции или индуктивное предположение.
Допускается истинность утверждения P (k) (или P (n) для всех n 0 £ п £ k).
· Вывод или индуктивный переход.
Доказывается истинность утверждения P (k +1), исходя из индуктивного предположения.
Замечание. Чаще всего база индукции начинается с n 0 = 1.
На рис.1 приведена схема доказательства по методу математической индукции (для простоты положим, что база индукции начинается с n = 1).
|
|
Рис. 1
Пример 1. Доказать при помощи метода математической индукции
.
Доказательство.