Учебники

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

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

Определение

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

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

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

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

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

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

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

Проблема 1

3n1 является кратным 2 для n = 1, 2, …

Решение

Шаг 1 – для n=1,311=31=2, который кратен 2

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

Мы должны доказать, что 3k+11 также кратно 2

3k+11=3 раз3k1=(2 раза3k)+(3k1)

Первая часть (2 times3k) наверняка будет кратна 2, а вторая часть (3k1) также верна, как наше предыдущее предположение.

Следовательно, 3k+11 кратно 2.

Итак, доказано, что 3n1 кратно 2.

Проблема 2

1+3+5+...+(2n1)=n2 для n=1,2, dots

Решение

Шаг 1 – для n=1,1=12, следовательно, шаг 1 выполняется.

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

Следовательно, 1+3+5+ dots+(2k1)=k2 верно (это предположение)

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

1+3+5+ dots+(2(k+1)1)

=1+3+5+ dots+(2k+21)

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

=1+3+5+ dots+(2k1)+(2k+1)

=k2+(2k+1)

=(k+1)2

Итак, выполняется 1+3+5+ dots+(2(k+1)1)=(k+1)2, что удовлетворяет шагу 2.

Следовательно, 1+3+5+ dots+(2n1)=n2 доказано.

Проблема 3

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

Решение

Шаг 1 – Для n=1(ab)1=a1b1=ab, следовательно, шаг 1 выполняется.

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

Мы должны доказать, что (ab)k+1=ak+1bk+1 также имеет место

Учитывая, (ab)k=akbk

Или, (ab)k(ab)=(akbk)(ab) [Умножение обеих сторон на ‘ab’]

Или (ab)k+1=(aak)(bbk)

Или (ab)k+1=(ak+1bk+1)

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

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

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

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

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

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