Доказательство математической индукции: §8 Метод математической индукции

Содержание

НОУ ИНТУИТ | Лекция | Индукция и комбинаторика

< Лекция 1 || Лекция 2: 123 || Лекция 3 >

Аннотация: Метод математической индукции. Индукция по структуре объекта. Комбинаторика: число размещений, перестановок и сочетаний. Принцип включения и исключения

Ключевые слова: математическая индукция, доказательство, базис индукции, шаг индукции, неравенство, слово, индукция, дедукция, функция, список операций, глубина формулы, произвольное, комбинаторика, размещения, перестановки, сочетания, треугольник паскаля, биномиальные коэффициенты, бином Ньютона, принцип включения и исключения, тождество

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

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

Пусть P(n) — это некоторое утверждение, зависящее от целочисленного параметра n. Пусть, во-первых, утверждение P(n

0) справедливо и пусть, во-вторых, для любого k >= n₀ из справедливости P(k) следует справедливость P(k+1). Тогда утверждение P(n) справедливо для всех n >= n₀.

Таким образом доказательство «по индукции» состоит из двух этапов.

Базис (или основание) индукции состоит в доказательстве утверждения P(n₀) для некоторого начального значения n₀ ( обычно n₀=1, но это не обязательно).
Шаг индукции состоит в предположении справедливости P(n) при n=k >= n₀ и доказательстве из этого предположения справедливости утверждения P(k+1) .

Рассмотрим несколько примеров применения метода математической индукции.

Пример 1.

Доказать, что при n>= 1

Базис индукции. При n=1 имеем
.
Шаг индукции. Допустим, что при n=k
Докажем тогда, что при n=k+1
Действительно,
Таким образом, наше утверждение выполненопри всех n>= 1.

Пример 2. Доказать, что для любого , и натурального n>= 2 выполнено неравенство (1+x)ⁿ > 1 +nx (это неравенство называют неравенством Бернулли).

Базис индукции. При , учитывая, что , имеем (1+x)²=1 +2x +x² > 1+2x.
Шаг индукции. Допустим, что при n=k неравенство справедливо, т.е. (1+x)^k > 1 +kx. Покажем, что тогда оно выполнено и при n=k+1. Действительно, так как 1+x > 0, то умножив обе части на 1+x > 0, получим (1+x)^k(1+x)=(1+x)^k+1 > (1+kx)(1+x)=1+ (k+1)x +kx²> 1+(k+1)x, что и требовалось.

В обычном понимании слово «индукция» означает переход от частных случаев к некоторому общему утверждению, а «дедукция» — получение результатов для частных случаев из некоторых общих утверждений, законов. В этом смысле метод математической индукции является дедуктивным, с его помощью доказываются общие утверждения (равенства, неравенства и т.п.). Он не дает способа для выдвижения общей гипотезы или угадывания общего правила или формулы по наблюдениям за отдельными частными случаями. Но этот метод позволяет проверять выдвинутые гипотезы. Для неверной гипотезы проверка провалится на шаге индукции.

Отметим также, что приведенная формулировка принципа математической индукции допускает разные эквивалентные варианты. В ряде случаев мы будем использовать вариант, в котором шаг индукции состоит в предположении справедливости P(n) при всех n <= k и доказательстве из этого предположения справедливости утверждения P(k+1).

Такая формулировка будет использоваться, в частности, при доказательствах индукцией по построению объекта.

В дискретной математике и в информатике многие классы объектов определяются индуктивно. В таких определениях явно или неявно участвует некоторая функция, задающая «сложность» объекта, и индукция идет по значениям этой функции. На базисном шаге определяются объекты минимальной сложности (обычно они имеют сложность 0), а индукционный шаг определения заключается в том, что из объектов меньшей сложности с помощью некоторых операций (операторов, конструкций) строятся объекты большей сложности.

Для доказательства некоторого свойства объектов индуктивно определенного класса метод математической индукции применяется в следующем виде.

Базис индукции состоит в проверке требуемого свойства у объектов минимальной сложности.
Шаг индукции состоит в предположении справедливости доказываемого свойства
у всех объектов класса, имеющих сложность <= k, и проверке того, что все объекты большей сложности (обычно, сложности k+1 ), получаемые из них с помощью используемых при определении класса операций, также обладают требуемым свойством.

Рассмотрим эту схему на примере простых арифметических выражений.

Пример 2.1. Пусть V ={x, y, z} — множество переменных, O={+, -, *, / } — список операций. Определим индуктивно множество выражений ( слов) в объединенном алфавите , называемых арифметическими формулами. Одновременно будем определять меру сложности этих формул, назывемую их глубиной. Глубину формулы обозначим через .

Базис индукции. Каждая переменная является арифметической формулой глубины 0, т. е. и d(v)=0.
Шаг индукции. Пусть и — арифметические формулы глубины и , соответственно. Тогда выражения
- (а) ,
- (б) ,
- (в) ,
- (г) ,
также являются арифметическими формулами из и каждая из этих формул имеет глубину .

Пусть w=w₁w₂ … w_n — произвольное слово в алфавите Скажем, что скобки в w расставлены правильно, если для каждого i <= n число левых скобок в слове w⁽ⁱ⁾=w₁w₂ … w_i не меньше числа правых скобок, а во всем слове w число левых скобок равно числу правых.

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

Базис индукции. . Формула глубины 0 является переменной . В ней нет скобок и поэтому они расставлены правильно.
Шаг индукции. Пусть утверждение справедливо для всех формул из глубины <= k и — произвольная формула глубины . Тогда она имеет одну из четырех форм (а), (б), (в) или (г). Предположим, что . Тогда из определения глубины следует, что и , и по индукционному предположению в обеих формулах и скобки расставлены правильно. Покажем, что и в скобки расставлены правильно. Пусть и . Тогда , здесь M= m₁+m₂ +3 и все символы v_i, w_j принадлежат алфавиту Для каждого 1 < i <= m₁+1 число левых скобок в t₁ … t_i на 1 больше числа левых скобок в v₁… v_i-1, и следовательно, больше числа правых скобок в этом слове, так все они входят в v₁… v_i-1. Это же справедливо для слова t₁t₂ … t_m1+2, заканчивающегося символом +. При m₁+2 < i < M разница между числом левых и правых скобок в t₁ . .. t_i не меньше 1, так как t₁= (, а в и скобки расставлены правильно. Во всем слове число левых и правых скобок совпадает, так как к скобкам и добавилась одна левая и одна правая скобка. Таким образом, в скобки расставлены правильно. Случаи (б), (в) и (г) рассматриваются аналогично.

Задачи

Задача 2.1. Доказать, что

Задача 2.2. Доказать, что

Задача 2.3. Доказать, что

Задача 2.4. Доказать, что n различных прямых на плоскости разбивают ее на области, которые можно закрасить белой и черной красками так, что смежные области будут закрашены разными красками.

Задача 2.5. Найдите ошибку в следующем доказательстве «по индукции» утверждения:

ru/2010/edi»>для всех n >= 1 справедливо неравенство 3ⁿ > 3(n +1) +1 .

Доказательство Пусть для некоторого k >= 1 неравенство справедливо, т.е. 3^k > 3(k +1) +1 (*). Докажем, что оно верно и для n=k+1, т.е. 3^k+1 > 3(k+2) +1. Для этого заметим, что для любого k >= 1 верно неравенство 2 cdot 3^k > 3. Прибавив его левую и правую часть к соответствующим частям неравенства (*), получим 3^k + 2 x 3^k > 3(k +1) +1+3 или 3^k+1 > 3(k+2) +1, что и требовалось. Установите, при каких n справедливо неравенство 3ⁿ > 3(n +1)+1.

Дальше >>

< Лекция 1 || Лекция 2: 123 || Лекция 3 >

Математическая индукция. Большая российская энциклопедия

Научные методы исследования

Области знаний:: Рекурсия и алгоритмы

Математи́ческая инду́кция, метод доказательства математических утверждений, основанный на следующем принципе: утверждение A(x)A(x)A(x), зависящее от натурального параметра xxx, считается доказанным для всех натуральных xxx, если доказано утверждение A(1)A(1)A(1), и для любого натурального числа nnn из предположения, что верно утверждение A(n)A(n)A(n), следует, что верно также утверждение A(n+1)A(n+1)A(n+1). 2(N+1)2, то из справедливости (1) при n=Nn=Nn=N вытекает справедливость (1) при n=N+1n=N+ 1n=N+1 (каково бы ни было NNN), т. е. (1) справедливо при всех натуральных nnn.

Доказательство утверждения A(1)A(1)A(1) составляет первый шаг (базис) индукции, а доказательство утверждения A(n+1)A(n+1)A(n+1) в предположении, что верно A(n)A(n)A(n), называется шагом индукции или индукционным переходом. При этом nnn называется параметром индукции, а предположение A(n)A(n)A(n) при доказательстве утверждения A(n+1)A(n+1)A(n+1) называется индуктивным предположением.

Принцип математической индукции является также основанием для индуктивных определений. Простейшим примером такого определения является определение свойства «быть словом длины nnn в данном алфавите A={a1,a2,…,ak}\mathscr A=\{ a_1,a_2,…,a_k \}A={a1,a2,…,ak}». Базис индукции: каждая буква алфавита A\mathscr AA есть слово длины 111. Индукционный переход: если EEE – слово длины nnn в A\mathscr AA, то каждое слово EaiEa_iEai, где к слову EEE справа приписывается буква aia_iai, где 1⩽i⩽k1 ⩽ i ⩽ k1⩽i⩽k, есть также слово длины n+1n+ 1n+1 в A\mathscr AA. Индукция может начинаться с n=0n=0n=0, т. е. с пустого слова.

Математическая индукция может применяться для доказательства утверждений A(x)A(x)A(x), в которых параметр xxx пробегает то или иное множество, вполне упорядоченное по некоторому трансфинитному типу; в этом случае говорят о трансфинитной индукции.

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

Дата публикации: 27 декабря 2022 г. в 17:43 (GMT+3)

Brilliant Math & Science Wiki

Мурсалин Хабиб, Адитья Вирани, Кристофер Бу, и

способствовал

Содержимое

Заявление
Формулировка
Примеры — суммирование
Примеры — Неравенства
Примеры — Делимость
Примеры — рекуррентные отношения
Примеры — функциональные уравнения
Примеры — Дифференциация
Примеры — интеграция
Примеры — приложения комбинаторики
Решение проблем
Доказательство математической индукции
Смотрите также

Основная статья: Написание доказательства по индукции

Теперь, когда мы немного познакомились с идеей доказательства по индукции, давайте перепишем все, что мы узнали, более формально.

Доказательство по индукции
Шаг 1: Докажите базовый случай
В этой части вы доказываете, что \(P(k)\) верно, если \(k\) является начальным значением вашего утверждения. Базовый случай обычно показывает, что наше утверждение верно, когда \(n=k\).
Шаг 2: Индуктивный шаг
Здесь вы предполагаете, что \(P(x)\) верно для некоторого положительного целого числа \(x\). Это предположение называется индуктивной гипотезой . Затем вы показываете, что если \(P(x)\) истинно, то верно и \(P(x+1)\). Это индуктивный шаг .
Короче говоря, индуктивный шаг обычно означает показать, что \(P(x)\имеет P(x+1)\).
Обратите внимание на слово «обычно», которое означает, что это не всегда так. Вы узнаете, что существует много вариантов индукции, в которых шаг индукции отличается от этого, например, сильная индукция.

Вот и все. В начале лучше следовать стандартному формату, чтобы вы точно знали, что писать. Как только вы освоитесь с ним, вы можете еще больше упростить доказательство.

Иногда случаются ошибочные доказательства индукции.

Как всегда, лучше всего учиться на примерах. Итак, начнем!

Суммирование часто является первым примером, используемым для индукции. Часто легко проследить, что представляет собой дополнительный член и как его добавление к итоговой сумме повлияет на значение.

Докажите, что \(1+2+3+\cdots +n=\frac{n(n+1)}{2}\) для всех натуральных чисел \(n\).
Мы хотим что-то доказать для «всех положительных целых чисел \(n,\)», и индукция кажется хорошим способом начать.
Сначала мы проверяем базовый случай. Хотя здесь это кажется очевидным (базовый случай равен 1, потому что это первое положительное целое число), это важный шаг. Иногда отсутствие проверки базового случая может привести к ложным доказательствам.
Наше утверждение верно для \(n=1\) (наш базовый случай), потому что с \(n=1\) левая часть равна \(1\), а правая часть равна \(\frac{ 1(1+1)}{2},\), что также равно \(1\).
Теперь предположим, что утверждение верно для некоторого положительного целого числа \(k\). Это наша индукционная гипотеза. Если мы сможем показать, что утверждение верно для \(k+1\), наше доказательство завершено.
По нашему предположению индукции имеем
\[1+2+3+\cdots+ k=\frac{k(k+1)}{2}.\]
Теперь, если мы прибавим \(k+1\) к обеим частям, мы получим
\[\begin{массив} { л л } 1+2+3+\cdots +k+(k+1) & =\frac{k(k+1)}{2}+(k+1) \\ & = (k+1)\left( \frac{k}{2} + 1 \right) \\ & = \frac{ (k+1)(k+2)} { 2} \\ & = \frac{ (k+1)\big((k+1)+1\big)} { 2},\\ \end{массив} \] 9{к+2}-2.\]
Таким образом, если утверждение верно, когда \(n=k\), оно также верно и для \(n=k+1\). Следовательно, утверждение верно для всех положительных целых чисел \(n\).\(\ _\square\)

\[1(1!)+2(2!)+3(3!)+4(4!)+\cdots +2014(2014)! = n!-1\]

Чему равно \(n?\)

Индукцию также можно использовать для доказательства неравенств. Просто примените тот же метод, который мы использовали. Еще раз легко проследить, что такое дополнительный член и как он влияет на конечную сумму. 92 + 2k + 1 \\ &> (2k + 1) + 2k + 1&&\qquad \text{ (по нашему предположению)}\\ &= 4k + 2 \\ &= 2k + 2k + 2 \\ &\geq 2k + 10&&\qquad \text{ (поскольку мы определили } k \geq 4\text{)} \\ &> 2k + 3 \\ &= 2k + 2 + 1 \\ &= 2(k+1) + 1 \\ &= RHS,\end{align*}\]

, что означает \(LHS > RHS. \)

Таким образом, если утверждение верно, когда \(n=k \), оно также верно и для \(n=k+1\). Следовательно, утверждение верно в пределах условия \(n\geq 4\).\(\ _\square\) 9{к+1} — 1 . \)
Следовательно, индуктивный шаг верен, и результат следует. \(_\квадрат\)

Рассмотрим последовательность Фибоначчи, где \( F_0 = 0 , F_1 = 1 , F_n = F_{n-1} + F_{n-2} \) для всех положительных целых чисел \(n\). Докажите, что
\[ F_0 + F_1 + F_2 + \cdots + F_n = F_{n+2} -1 \]
для всех \( n \geq 0. \)
Базовый случай:
Пусть \(n=0\). Левая сторона равна \( F_0 = 0 \), а правая сторона равна \( F_2 — 1 = 0 \).
Шаг индукции:
Предположим, что утверждение истинно для \(n,\), т.е. \[ F_0 + F_1 + F_2 + \cdots + F_n = F_{n+2} -1. \] Затем \[ \begin{выравнивание} F_0 + F_1 + F_2 + \cdots + F_n + F_{n+1} &=& ( F_0 + F_1 + F_2 + \cdots + F_n) + F_{n+1} \\ &=& ( F_{n+2} -1 ) + F_{n+1} &\qquad \text{(по предположению)}\\ &=& ( F_{n+2} + F_{n+1} ) -1 \\ &=& F_{n+3} -1, \end{эквнаррай} \] что является утверждением для \( n+1 \). На этом индукция завершена. \(_\квадрат \) 9{n+2} \\ \конец{массив} \] Следовательно, индуктивный шаг верен, и результат следует. \(_\квадрат\)
Примечание. Почему мы использовали 2 базовых случая? Это потому, что на индукционном шаге мы должны использовать 2 уравнения.

Как видите, индукция — это мощный инструмент для проверки личности. Однако, если бы нам не дали закрытую форму, было бы сложнее доказать утверждение по индукции. Вместо этого нам нужно будет изучить линейные рекуррентные соотношения, чтобы понять, как их решать. 93.\]

Детали и предположения:

Например, \(b_{1,1} = 1, b_{2,3} = 2,\) и \(b_{5,6} = 5.\)

Изображение предоставлено Википедией Треугольник Паскаля

Следующая теорема является чрезвычайно важным фактом в функциональных уравнениях.

\(f\) — это вещественнозначная функция, определенная на рациональных числах, такая, что \(f(a+b)=f(a)+f(b)\) для всех рациональных значений \(a\) и \(b \). Тогда \(f(x)=xf(1)\) для всех рациональных значений \(x\).

Приведем набросок доказательства. Подробности оставляем читателю.
Сначала мы покажем по индукции, что \( f(na) = nf(a) \) для всех натуральных чисел \(n\).
Затем мы показываем, что \(f(0)=0, f(-na)=-nf(a)\), поэтому утверждение верно для всех целых чисел.
Подставляя \(a=1\) и \(n=n,\), мы получаем, что \(f(n) = nf(a) \) для всех целых чисел.
Мы подставляем \( a = \frac {m}{n}\) и \(n=n\), чтобы получить это
\[ m f(1) = f(m) = n f\left(\frac {m}{n}\right) \ подразумевает f\left(\frac {m}{n}\right) = \frac {m {n} f(1) \] 9{ n }{ x } \, dx },\]
, если \(I(5) = \frac {a\sqrt {b}} }{c} \), что такое \(a + b + c?\ )
Детали и предположения:
Вы можете использовать \(\int { \cos { ax } } \, dx =\frac { 1 }{a } \sin {ax } \).
\(a, b, c\) — натуральные числа, \( \gcd(a,c)=1,\) и \(b\) — целое число без квадратов.
А Б С А и Б А и С Б и С Все они Никто из них 9{s-1} \, dt\, ?\]
A. \(\ \) Интегрирование по частям
B. \(\ \) U-подстановка
C. \(\ \) Индукция
В стране есть \(n\) городов. Любые два города соединены дорогой с односторонним движением. Докажите, что через все города проходит маршрут.
Утверждение очевидно верно для \(n=1\) или \(n=2\). Итак, мы разобрались с «базовым отделом».
Но как показать индуктивный шаг, то есть, если мы знаем, что существует маршрут для страны с \(k\) городами, то как мы покажем, что существует маршрут для страны с \((k+1 )\) города?
Давайте запишем то, что мы уже знаем. Допустим, \(k\) городов — это \(C_1, C_2, C_3,\cdots, C_{k}\) и есть маршрут
\[C_{1}\rightarrow C_{2} \rightarrow C_{3} \rightarrow \cdots\rightarrow C_k\]
, который проходит через все из них. Это наша индукционная гипотеза. Теперь нам нужно показать индуктивный шаг. Другими словами, если у нас есть другой город \(C_{k+1}\), мы должны показать, что его можно вставить куда-нибудь в указанный выше маршрут.
Мы знаем, что каждые два города соединены дорогой с односторонним движением. Это означает, что между \(C_k\) и \(C_{k+1}\) есть дорога. Можем ли мы добавить \(C_{k+1}\) в конец маршрута вот так?
Нет, потому что дороги односторонние, поэтому очень вероятно, что дорога между \(C_k\) и \(C_{k+1}\) может пойти не в ту сторону. Мы не можем просто сказать, что наш маршрут
.
\[C_1 \стрелка вправо C_2 \стрелка вправо C_3 \стрелка вправо \cdots \стрелка вправо C_k \стрелка вправо C_{k+1}\]
и что с этим покончено. Это немного сложнее.
Однако надежда еще не потеряна. Помните, что любые два города соединены дорогой. Есть вероятность, что \(C_{k+1} \rightarrow C_1\). Если это так, мы закончили, потому что у нас есть маршрут
\[ C_{k+1} \стрелка вправо C_1 \стрелка вправо C_2\стрелка вправо C_3 \стрелка вправо \cdots \стрелка вправо C_k.\]
Если это не так, то существует \(i\) с \(1\leq i\leq k,\), такое что \(C_i \rightarrow C_{k+1}\).
Возьмем наибольшее такое \(i\). По определению у нас есть \(C_i\rightarrow C_{k+1}\rightarrow C_{i+1}\). Теперь мы можем вставить \(C_{k+1}\) между этими двумя городами, и у нас получится маршрут
.
\[C_1\стрелка вправо C_2\стрелка вправо \cdots C_i\стрелка вправо C_{k+1}\стрелка вправо C_{i+1}\стрелка вправо \cdots \стрелка вправо C_k,\]
, что завершает наше доказательство. \(_\квадрат\)
Примечание : есть вероятность, что \(C_{i+1}=C_{k+1}\). Это просто означает, что вам нужно пройти \(C_{k+1}\) до конца маршрута.
Для некоторых положительных целых чисел \(n\) существует полином от \(n\) переменных, образ которого является в точности множеством действительных положительных чисел (обратите внимание, что 0 не входит в это множество). Значения \(n\), подтверждающие это свойство, называются бременскими числами .
Найдите сумму всех бременских чисел меньших или равных 30.
Поставьте 0 в качестве ответа, если вы считаете, что не существует ни одного бременского числа меньшего или равного 30.
Вот несколько советов:
Знайте, когда индукция является хорошим подходом. Задачи, содержащие фразу «докажите для всех положительных целых чисел \(n\)», являются хорошими кандидатами на индукцию.
Никогда не пропускайте базовый вариант. Хотя в большинстве случаев базовый случай очевиден, доказательство не будет полным, если вы его не покажете. Отсутствие обоснования базового случая приводит к большому количеству ложных доказательств.
Если вы хотите использовать индукцию в задаче, убедитесь, что у вас есть хоть какое-то представление о том, как вы собираетесь связать \(P(k+1)\) с \(P(k).\)
Иногда проще доказать что-то сложное! См. «Сильнее» Индукция.
Иногда, начиная с меньшего базового варианта, расчет становится проще. Иногда, начиная с более крупного базового случая, шаг индукции становится проще. Индукцию также можно использовать на конечных дискретных множествах.
Вы не всегда индуцируете переменную \(n.\)
Если дается гипотеза, вопросы обычно проверяют вашу математическую способность манипулировать значениями.
Если предложение не дано, оно проверяет вашу способность осмысливать ряды и выявлять любые лежащие в их основе закономерности, имеющие решающее значение для решения.
Хотя индукция может установить истинность утверждения, она редко обеспечивает мотивацию/обоснование проблемы. Однако это может обеспечить более простое решение.
Рассмотрим квадратную сетку 8 на 8, из которой удалена 1 случайная плитка. Покажите, что оставшуюся площадь можно полностью замостить 21 L-образным тримино. 9n \text{ квадратная сетка с удаленной }1\text{ случайной плиткой может быть полностью замощена L-образными тримино}. \]
Попробуйте!
Пусть \(S\) будет набором натуральных чисел со следующими свойствами:
(1) Целое число 1 принадлежит множеству.
(2) Всякий раз, когда целое число \(k\) находится в \(S\), следующее целое число \(k+1\) также должно быть в \(S\).
Тогда \(S\) есть множество всех положительных целых чисел.
Это утверждение кажется почти очевидным. Доказательство приведено для полноты, но не является существенным для понимания индукции.
Докажем эту теорему от противного.
Пусть \(T\) — множество всех положительных целых чисел, не принадлежащих \(S\). К предположение, \(T\) непусто. Следовательно, согласно принципу упорядоченности, он должен содержать наименьший элемент, который мы будем обозначать через \(\alpha\).
По (1), \(0 < \alpha-1 < \alpha\). Поскольку \( \alpha\) является наименьшим целым числом в \(T\), это означает, что \( \alpha-1 \not\in T \ подразумевает (\alpha-1)\in S \).
Согласно (2), \(S\) также должен содержать \( (\alpha-1)+1=\alpha\). Это противоречит предположению, что \(\alpha\in\) \(T\).
Следовательно, множество \(T\) пусто, а множество \(S\) содержит все положительные целые числа. \(_\квадрат \)
Дефектные индукционные доказательства
Цитировать как: Индукция. Brilliant.org . Извлекаются из https://brilliant.org/wiki/induction/
Без названия
Без названия
Индукция
Предметы для изучения
первый принцип математической индукции
базовый шаг
гипотеза индукции
индукция
Содержимое
Как мы видели в рекурсии , множество натуральных чисел может быть определено рекурсивно, и его элементы могут быть сгенерированы один за другим, начиная с 0 путем добавления 1 . Таким образом, множество натуральных чисел можно полностью описать, указав базис элемент ( 0 ) и процесс создания элемента из известного элемента в наборе.
Воспользовавшись этим, можно доказать, что натуральные числа обладают определенными свойствами. следующим образом :
Сначала доказано что базовый элемент, то есть 0 , имеет рассматриваемое свойство ( базовый шаг ). Затем доказывается, что если произвольное натуральное число, обозначим его n , обладает рассматриваемым свойством, то следующий элемент, т.е. n + 1 , обладает этим свойством ( индуктивный шаг ).
Когда эти два доказаны, то следует, что все природные числа обладают этим свойством. Поскольку 0 обладает свойством базисного шага, то следующий за ним элемент, т.е. 1 , обладает тем же свойством по индукционному шагу. Тогда, поскольку 1 имеет свойство, элемент рядом с ним, который 2 , снова обладает тем же свойством на шаге индукции. Действуя аналогичным образом, можно показать, что любое натуральное число имеет недвижимость. Этот процесс в чем-то аналогичен опрокидыванию ряда доминошек с опрокидыванием первой костяшки. соответствующий базовый шаг.
Более общие математические выражения, включающие натуральные числа n , такие как 1 + 2 + … + n = n( n + 1 )/2 можно доказать с помощью математической индукции по тому же признаку.
Чтобы доказать, что утверждение P ( n ) верно для всех натуральных чисел, где является натуральным числом, мы продолжаем следующим образом :
Базовый этап : Докажите, что P ( ) верно.
Индукция : Докажите, что для любого целого числа, если P ( k ) верно (называемая гипотезой индукции ), то P ( k + 1 ) верно.
Первый принцип математической индукции утверждает, что если базисный шаг и индуктивный шаг доказаны, то P ( n ) верно для всех натуральных чисел .
В качестве первого шага для доказательства по индукции часто рекомендуется переформулировать Р ( к + 1 ) в пересчете на Р ( к ) так что можно использовать P ( k ) , которое предполагается верным.
Пример:
Докажите, что для любого натурального числа n , 0 + 1 + … + n = n( n + 1 )/2 .
Доказательство:
Базовый шаг: Если n = 0 , тогда слева = 0 и справа = 0 * (0 + 1) = 0 .
Следовательно, слева = справа .
Индукция : Предположим, что для произвольного натурального числа п , 0 + 1 + … + п = н( н + 1 )/2 . ——— Гипотеза индукции
Чтобы доказать это для n + 1 , сначала попробуйте выразить LHS для n + 1 в пересчете на LHS для n , и каким-то образом использовать гипотезу индукции.
No related posts.