Теоретические обоснования

В дискретной математике довольно часто встречаются утверждения, зависящие от целочисленных параметров. Во многих случаях их удается доказать методом математической индукции. Этот метод основан на принципе математической индукции, который состоит в следующем.

Пусть - некоторое утверждение, зависящее от натурального параметра . Это утверждение считается справедливым для всех значений , начиная с некоторого значения , если выполняются следующие условия:

1) утверждение справедливо для ;

2) из предположения, что справедливо при ( - любое натуральное число, большее или равное ) следует, что оно справедливо и при .

Доказательство справедливости утверждения методом математической индукции включает два этапа.

1) базис индукции, состоящий в проверке справедливости утверждения для некоторого начального значения (обычно , но это не обязательно);

2) индуктивный переход, состоящий в том, что, полагая справедливым утверждение (), доказывают справедливость утверждения .

Пример 10. Доказать методом математической индукции формулу бинома Ньютона

.

◄ 1. Базис индукции. При имеем . Поскольку , формула верна.

2. Индуктивный переход. Докажем, что из предположения о том, что верно равенство

,

следует, что верно равенство

,

полученное из формулы бинома Ньютона заменой на .

В самом деле, имеем

(при переходе, помеченном (), были использованы тождество и равенства , , , ).

Таким образом, формула бинома Ньютона справедлива для любого . ►

Приведенная формулировка принципа математической индукции допускает равносильные варианты. В некоторых случаях мы будем использовать вариант, в котором индуктивный переход состоит в предположении справедливости утверждения для и доказательстве его справедливости для .

Для доказательства комбинаторных соотношений также пользуются аппаратом математического анализа. Проиллюстрируем это на примере.

Пример 11.Доказать, что при любом натуральном выполняется равенство

.

◄ Воспользуемся тем, что при всех действительных значениях выполняется равенство . Заменим и их биномиальными разложениями:

.

Поскольку мы имеем тождество относительно , коэффициенты при одинаковых степенях в обеих его частях должны быть одинаковыми. Рассмотрим коэффициенты при . В левой части интересующий нас коэффициент равен . Чтобы понять, чему равен коэффициент при в правой части, перепишем ее, изменив порядок слагаемых во втором множителе:

.

Теперь видно, что слагаемые, содержащие , получаются при перемножении друг на друга первых, вторых, третьих и т.д. слагаемых, стоящих в скобках. Следовательно, верно равенство

.

Учитывая, что , окончательно получаем:

.►