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

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

Определение

Математическая индукция - это математический метод, который используется для доказательства того, что утверждение, формула или теорема верны для каждого натурального числа.

Техника состоит из двух шагов, чтобы доказать утверждение, как указано ниже -

Шаг 1 (Базовый шаг) - Это доказывает, что утверждение верно для начального значения.

Шаг 2 (Индуктивный шаг) - Это доказывает, что если утверждение верно для n- й итерации (или числа n ), то оно также верно для (n + 1) итерации (или числа n + 1 ).

Как это сделать

Шаг 1 - Рассмотрим начальное значение, для которого утверждение верно. Следует показать, что утверждение верно для n = начального значения.

Шаг 2 - Предположим, что утверждение верно для любого значения n = k . Затем докажите, что утверждение верно для n = k + 1 . Мы фактически разбиваем n = k + 1 на две части, одна часть - n = k (что уже доказано), и пытаемся доказать другую часть.

Проблема 1

$ 3 ^ n-1 $ является кратным 2 для n = 1, 2, ...

Решение

Шаг 1 - для $ n = 1, 3 ^ 1-1 = 3-1 = 2 $, который кратен 2

Шаг 2. Предположим, что $ 3 ^ n-1 $ верно для $ n = k $, следовательно, $ 3 ^ k -1 $ верно (это предположение)

Мы должны доказать, что $ 3 ^ {k + 1} -1 $ также кратно 2

$ 3 ^ {k + 1} - 1 = 3 \ раз 3 ^ k - 1 = (2 \ раза 3 ^ k) + (3 ^ k - 1) $

Первая часть $ (2 \ times 3k) $ наверняка будет кратна 2, а вторая часть $ (3k -1) $ также верна, как наше предыдущее предположение.

Следовательно, $ 3 ^ {k + 1} - 1 $ кратно 2.

Итак, доказано, что $ 3 ^ n - 1 $ кратно 2.

Проблема 2

$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ для $ n = 1, 2, \ dots $

Решение

Шаг 1 - для $ n = 1, 1 = 1 ^ 2 $, следовательно, шаг 1 выполняется.

Шаг 2. Предположим, что утверждение верно для $ n = k $.

Следовательно, $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ верно (это предположение)

Мы должны доказать, что $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ также имеет место

$ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) $

$ = 1 + 3 + 5 + \ dots + (2k + 2 - 1) $

$ = 1 + 3 + 5 + \ dots + (2k + 1) $

$ = 1 + 3 + 5 + \ dots + (2k - 1) + (2k + 1) $

$ = k ^ 2 + (2k + 1) $

$ = (k + 1) ^ 2 $

Итак, $ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2 $, что удовлетворяет шагу 2.

Следовательно, $ 1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2 $ доказано.

Проблема 3

Докажите, что $ (ab) ^ n = a ^ nb ^ n $ верно для каждого натурального числа $ n $

Решение

Шаг 1 - Для $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $, следовательно, шаг 1 выполняется.

Шаг 2 - Предположим, что утверждение верно для $ n = k $, следовательно, $ (ab) ^ k = a ^ kb ^ k $ верно (это предположение).

Мы должны доказать, что $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ также имеет место

Учитывая, $ (ab) ^ k = a ^ kb ^ k $

Или, $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Умножение обеих сторон на 'ab']

Или $ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $

Или $ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $

Следовательно, шаг 2 доказан.

Таким образом, $ (ab) ^ n = a ^ nb ^ n $ верно для каждого натурального числа n.

Сильная Индукция

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

  • Шаг 1 (Базовый шаг) - Это доказывает, что начальное предложение $ P (1) $ верно.

  • Шаг 2 (Индуктивный шаг) - Доказывается, что условное утверждение $ [P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1) $ верно для натуральных чисел $ k $.