На этом шаге мы разберем, в чем суть этого метода и приведем пример его использования.

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

1. начальное условие (основание). Проверяется, что формула верна для наименьшего значения n, скажем, n = 0;

2. шаг индукции. Сначала предполагается, что формула верна для некоторого произвольного значения n. Это предположение называется гипотезой индукции. Затем на основании этого предположения доказывается, что формула верна и для n + 1.

    Если можно доказать истинность обоих шагов, то согласно индукции из этого следует, что утверждение справедливо для всех n >= n₀. Утверждение должно быть истинным для n₀, а затем - для n₀ + 1, n₀ + 2 и так далее для каждого следующего шага индукции.

    Рассмотрим ещё раз сумму первых n положительных чисел (1.4). Попробуем доказать справедливость следующего равенства (гипотеза индукции), содержащего квадратный полином:

           n            
    S(n) = ∑ i = n(n + 1) / 2    (1.12)
          i=1

    Начальное условие, очевидно, истинно, так как

    S(1) = 1(1 + 1)/2 = 1          . 

               n+1            
    S(n + 1) = ∑ i = (n + 1)(n + 2) / 2    (1.13)
               i=1

               n            
    S(n + 1) = ∑ i + (n + 1)    
               i=1

    Затем, считая, что имеет силу (1.12), заменим сумму полиномом:

    S(n + 1) = n(n + 1) / 2 + (n + 1) = (n + 1)(n / 2 + 1) = (n + 1)(n + 2) / 2   .

    Откуда видно, что (1.13) истинна, и на этом доказательство закончено.

    На следующем шаге мы рассмотрим рекурсивную убежденность.

Предыдущий шаг Содержание Следующий шаг