Принцип домино
Существует такое понятие, как принцип домино. Представьте, что рядом стоят несколько косточек, мы толкаем одну из них, она, падая, толкает вторую, та – третью и т. д. (см. рис. 1). Существуют даже специальные турниры по падающему домино – команды часами собирают конструкции из домино с тем, чтобы насладиться их красивым падением.
Рис. 1. Принцип домино
Для того чтобы сработала такая цепная реакция, необходимо:
- уронить первую косточку домино;
- расставить косточки так, чтобы падение предыдущей косточки влекло за собой падение следующей.
Похожий принцип лежит в основе важного метода, который используют в математике. Этот метод называется математической индукцией. Метод математической индукции является важным способом доказательства утверждений при любом натуральном значении переменной.
Рассмотрим, в чем состоит данный метод, разобрав конкретный пример.
Задача 1
Докажите, что сумма натуральных чисел от 1 до n равна 
.
Доказать: 
.
Доказательство
Согласно методу индукции, во-первых, необходимо доказать базу индукции, то есть проверить выполнение данного в условии утверждения для первого значения n.
База:
Так как в левой части утверждения записана сумма всех натуральных чисел от 1 до n ,то число 
отражает число слагаемых в левой части. Следовательно, докажем:
Таким образом, база доказана.
Далее необходимо доказать индукционный переход. Предположим, что данное в условии утверждение уже доказано для 
, то есть нам известно, что:
Суть метода математической индукции на примере задачи 1
Метод математической индукции состоит в следующем
Какое-либо утверждение, зависящее от натурального числа n, справедливо для любого натурального n если:
- утверждение является истинным при ;
- утверждение остается истинным, если n увеличить на единицу.
Задача 2
Докажите, что выражение 
делится на 5 для любого натурального n.
Доказать: 
Доказательство
- База индукции:
Проверяем данное утверждение для :
Принцип математической индукции
Представьте себе робота, который умеет делать две вещи: подходить к лестнице и забираться на одну ступеньку вверх (причем неважно, на какой ступеньке он до этого находился). Может ли этот робот забраться с первого этажа на второй? Конечно. Для этого ему надо подойти к лестнице, а затем применить вторую операцию – забраться на ступеньку. Потом снова применить вторую операцию – подъем на ступеньку. И так применять второе действие столько раз, сколько есть ступенек. При этом если роботу дать команду: поднимись на второй этаж, он не поймет, так как умеет выполнять только две операции – подходить к лестнице и забираться на одну ступеньку.
Так же работает метод математической индукции. База индукции – это подход к лестнице (утверждение для ). Переход индукции – это подъем на одну ступеньку вверх (робот не уточняет, каким образом он оказался на очередной ступеньке, а просто делает действие, переходя с предыдущей ступеньки на следующую). То есть, если мы доказали утверждение для k, то оно верно для k+1 и т. д.
