Метод математической индукции — это мощный инструмент для доказательства утверждений, которые зависят от натуральных чисел. Он состоит из двух основных шагов:

Базовый случай: Проверяем утверждение для начального значения (обычно для n = 1 или n = 0).Индуктивный шаг: Предполагаем, что утверждение верно для некоторого натурального числа k (индуктивное предположение), и показываем, что оно также верно для k + 1.

Рассмотрим пример неочевидного комбинаторного тождества:

[
\sum_{i=0}^{n} \binom{n}{i} = 2^n
]

Это тождество утверждает, что сумма биномиальных коэффициентов по фиксированному n равна 2 в степени n.

1. Базовый случай

Проверим базовый случай для n = 0:

[
\sum_{i=0}^{0} \binom{0}{i} = \binom{0}{0} = 1
]
С другой стороны, (2^0 = 1).

Таким образом, база индукции выполняется, так как обе стороны равны.

2. Индуктивный шаг

Теперь предположим, что утверждение верно для n = k, т.е.

[
\sum_{i=0}^{k} \binom{k}{i} = 2^k.
]

Необходимо показать, что это верно и для n = k + 1:

[
\sum_{i=0}^{k+1} \binom{k+1}{i} = 2^{k+1}.
]

Используем формулу Паскаля для биномиальных коэффициентов:

[
\binom{k+1}{i} = \binom{k}{i} + \binom{k}{i-1}.
]

Тогда мы можем разложить сумму:

[
\sum{i=0}^{k+1} \binom{k+1}{i} = \sum{i=0}^{k} \binom{k}{i} + \sum_{i=0}^{k} \binom{k}{i-1}.
]

Обратите внимание, что в первой сумме (i) принимает значения от 0 до k, и во второй сумме (i) принимает значения от 1 до k + 1, что можно переписать как:

[
\sum{i=0}^{k+1} \binom{k+1}{i} = \sum{i=0}^{k} \binom{k}{i} + \sum{j=0}^{k} \binom{k}{j} \text{ (где j = i - 1)} = 2 \sum{i=0}^{k} \binom{k}{i}.
]

По индуктивному предположению мы знаем, что (\sum_{i=0}^{k} \binom{k}{i} = 2^k). Подставим это в уравнение:

[
\sum_{i=0}^{k+1} \binom{k+1}{i} = 2 \cdot 2^k = 2^{k+1}.
]

Таким образом, индуктивный шаг завершается, и мы показываем, что утверждение верно для n = k + 1.

Заключение

Таким образом, с помощью метода математической индукции мы доказали, что:

[
\sum_{i=0}^{n} \binom{n}{i} = 2^n
]

верно для всех натуральных n.