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

Mathematical induction, это метод доказательства результатов или создания утверждений для натуральных чисел. В этой части метод иллюстрируется на множестве примеров.

Определение

Mathematical Induction представляет собой математический метод, который используется для доказательства того, что утверждение, формула или теорема верны для любого натурального числа.

Техника включает в себя два шага для доказательства утверждения, как указано ниже:

Step 1(Base step) - Доказывает, что утверждение верно для начального значения.

Step 2(Inductive step)- Доказывает, что если утверждение верно для n- ^й итерации (или числа n ), то оно также верно для (n + 1) ^-й итерации (или числа n + 1 ).

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

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

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

Проблема 1

$ 3 ^ n-1 $ делится на 2 для n = 1, 2, ...

Solution

Step 1 - Для $ n = 1, 3 ^ 1-1 = 3-1 = 2 $, что кратно 2

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

Нам нужно доказать, что $ 3 ^ {k + 1} -1 $ также делится на 2

$ 3 ^ {k + 1} - 1 = 3 \ times 3 ^ k - 1 = (2 \ times 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 $

Solution

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

Step 2 - Предположим, утверждение верно для $ n = k $.

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

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

$ 1 + 3 + 5 + \ точки + (2 (k + 1) - 1) $

$ = 1 + 3 + 5 + \ точки + (2k + 2 - 1) $

$ = 1 + 3 + 5 + \ точки + (2k + 1) $

$ = 1 + 3 + 5 + \ точки + (2k - 1) + (2k + 1) $

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

$ = (к + 1) ^ 2 $

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

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

Проблема 3

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

Solution

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

Step 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 $, используя следующие шаги:

• Step 1(Base step) - Это доказывает, что первоначальное предложение $ P (1) $ верно.

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