Без названия

1.

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

2.

Немного о смысле
• Мы привыкли, что натуральные числа – это числа, которые мы используем для счета: 1, 2, 3, 4, 5 и так далее. Но
как бы долго мы ни считали, вряд ли хватит усердия дойти до 1’000’000, и даже до 1’000.
• Tем не менее мы часто встречаем задачи, где надо доказать утверждение для всех натуральных чисел

3.

Немного о смысле
• Мы привыкли, что натуральные числа – это числа, которые мы используем для счета: 1, 2, 3, 4, 5 и так далее. Но
как бы долго мы ни считали, вряд ли хватит усердия дойти до 1’000’000, и даже до 1’000.
• Tем не менее мы часто встречаем задачи, где надо доказать утверждение для всех натуральных чисел
Как же быть?

4.

Немного о смысле
• Мы привыкли, что натуральные числа – это числа, которые мы используем для счета: 1, 2, 3, 4, 5 и так далее. Но
как бы долго мы ни считали, вряд ли хватит усердия дойти до 1’000’000, и даже до 1’000.
• Tем не менее мы часто встречаем задачи, где надо доказать утверждение для всех натуральных чисел
Как же быть?
• Рассмотрим небольшой пример из жизни

5.

Как построить дом?
• Для начала надо научиться строить первый этаж,
на чем-то же дом должен стоять

6.

Как построить дом?
• Для начала надо научиться строить первый этаж,
на чем-то же дом должен стоять
• Потом нам нужна инструкция о том, как построить второй

7.

Как построить дом?
• Для начала надо научиться строить первый этаж,
на чем-то же дом должен стоять
• Потом нам нужна инструкция о том, как построить второй
• Затем инструкция для третьего

8.

Как построить дом?
• Для начала надо научиться строить первый этаж,
на чем-то же дом должен стоять
• Потом нам нужна инструкция о том, как построить второй
• Затем инструкция для третьего
• Четвертого

9.

Как построить дом?
• Для начала надо научиться строить первый этаж,
на чем-то же дом должен стоять
• Потом нам нужна инструкция о том, как построить второй
• Затем инструкция для третьего
• Четвертого
• Пятого

10.

Как построить дом?
• Для начала надо научиться строить первый этаж,
на чем-то же дом должен стоять
• Потом нам нужна инструкция о том, как построить второй
• Затем инструкция для третьего
• Четвертого
• Пятого
• …..

11.

Как построить дом?
Какой же огромной и неудобной будет инструкция?
А вдруг надо построить небоскреб и кто-то ошибся на 100-й странице?

12.

Решим проблему
Давайте вместо отдельных инструкций к каждому этажу сделаем всего две!
• Как построить первый этаж?
• Как к уже построенный этажам добавить еще один?

13.

Так и работает индукция!
База: доказать утверждение для числа 1
Переход: придумать алгоритм, который позволит перейти от доказательства для числа k к
доказательству для числа k+1

14.

Пример
Докажите, что

15.

Решение

16.

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

17.

Решение

18.

Осталось ли что-то непонятным?
• План?
• База?
• Переход?

19.

Ссылки, где можно почитать еще

20.

Давайте решать!