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

Метод математической индукции – это способ доказательства справедливости утверждения на множестве чисел

Пример утверждения
Представьте себе множество, допустим N – натуральных чисел (0, 1, 2, 3,… и т.д.) (! Ноль не принадлежит множеству N)
Вот вам такое простое утверждение:
1+2+…+n = ((1+n)/2)n
Эта формула справедлива и нужна для того, чтобы быстро считать конечные последовательности чисел вида, например (1+2+3+4), или, например (1+2+3+4+5+6). Здесь важно, чтобы цифры не пропускались. Выражение, к примеру (1+3+6) с помощью данной формулы посчитать нельзя.
Буквой n в формуле обозначается последний элемент такой последовательности

Для того, чтобы доказать что-либо методом математической индукции, вам потребуется доказать
БАЗУ ИНДУКЦИИ
ШАГ ИНДУКЦИИ
Вообще, хотелось бы для начала знать, что это и зачем это нужно

База индукции - это число, начиная с которого вы хотите доказывать верность утверждения. Например здесь, это число 1, в случае с другой формулой (утверждением) базой могло бы послужить другое число

Давайте же докажем базу индукции. Применим нашу формулу для 1. Здесь n=1 так как наша конечная последовательность состоит из всего 1 числа
Итак, подставим в равенство.
1 = ((1+1)/2)*1
Можете убедиться, что равенство верное, базу индукции в данном примере мы доказали

Шаг индукции, простыми словами - это доказательство верности утверждения для числа K, опираясь на предположение, что утверждение верно для числа (K-1)
Шаг индукции нужен, чтобы вручную не перебирать 100500 чисел, проверяя, верна ли формула для них

Итак, предполагая, что для n = (k - 1) наше утверждение верное, докажем, что утверждение верно для n = k
([1+(k-1)]/2)*(k-1) – так выглядит формула для n = (k - 1)
Это тоже самое, что 1+2+3+…+(k - 1)
рассмотрим последовательность почти такую же, но до k, а не (k-1)
1+2+3+…+(k-1)+k
левую часть заменим (в прямоугольнике) на нашу уже известную формулу, так как мы предположили утверждение верным для (k -1)
В итоге имеем ([1+(k-1)]/2)*(k-1)+k

((1+(k-1))/2)*(k-1)+k Преобразуем это выражение
(k/2)*(k-1)+k
((k*k)/2)-(k/2))+k
k*k/2+k/2
(1/2)(k*k+k)
(1/2)k(k+1)
((1+k)/2)*k – вот мы и пришли к тому, как должна выглядеть формула для n = k
База индукции доказана.
Утверждение верно для всех последовательностей, начиная от последовательности из одной единицы, до любой конечной последовательности

После этого может всё равно остаться вопрос, типо, почему это работает?
Для устранения этого непонимания я приведу вам простое объяснение (доказательство) того, что метод математической индукции действительно работает
Представим, что есть некое утверждение, (предикат, если математическим языком), обозначим его «P»
Так как это увтерждение для какого-то конкретного числа (как в примере было n), это утверждение зависящее от n. Поэтому обозначается «P(n)»
Итак, пусть соблюдены 2 условия: Доказана база индукции и шаг индукции, ОДНАКО, ОТ ПРОТИВНОГО, пусть УТВЕРЖДЕНИЕ ГДЕ-ТО ОКАЗАЛОСЬ ЛОЖНЫМ
Если оно где-то ложно, значит обязательно есть какой-то конечный набор чисел, для которых утверждение ложное. Давайте возьмём минимальное число из этого набора. Обозначим его за « i »

P(i) ложное (утверждение для n = i не работает)
Тогда поступим следующим образом: Так как i меньшее из тех чисел, для которых P ложно, то откатившись на шаг назад (рассмотрев утверждение P(i-1)) мы увидим, что оно истинно
Проведем шаг индукции для P(i-1), и так как шаг индукции доказан, имеем что P((i-1)+1) истинно. Шаг индукции ведь доказывает верность последующего, опираясь на верность текущего.
Выходит что P(i-1+1), равное P(i) истинно, а мы его взяли из множества, для которых утверждение ложно. Противоречие. Такими противоречиями (но куда более строгими, и зачастую не понятными новичкам) доказываются утверждения. Предполагаем выполнение чего-либо, и приходим к полнейшему математическому абсурду. Раз пришли к абсурду, значит и предположение было ложным.

В качестве хорошего материала для практического понимания могу предложить этот видеоролик. Мне в своё время он очень пригодился
https://youtu.be/X_KXgYFCmz0