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

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

Определение

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

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

Шаг 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$.