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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Математическата индукция е метод за математическо доказателство, използван за доказване на свойства на естествените числа и на други множества, равномощни с множеството на естествените числа. Типична е употребата ѝ за доказване, че дадено твърдение е вярно за всички естествени числа. Това се прави, като се доказва, че първото твърдение от крайна редица от твърдения е вярно, и след това се доказва, че ако произволно твърдение от тази редица е вярно, то е вярно и следващото.

Този метод може да се обобщи за доказване на твърдения относно по-общи добре обосновани структури като дърветата - това обобщение е известно като структурна индукция и се използва в математическата логика и информатиката.

Доказателствата, базирани на математическата индукция, за дадено свойство на всички естествени числа n обикновено се свеждат до три стъпки:

  1. Тривиално доказателство на доказваното свойство за n = 1
  2. Индукционна хипотеза (ИХ): Допускане, че доказуемото свойство е валидно за n = k
  3. Индукционна стъпка (ИС): Доказателство на свойството за n = k + 1, в което се ползва като ever a доказана индукционната хипотеза.

Принципът на математическата индукция обикновено се приема като аксиома на естествените числа (вижте Аксиоми на Пеано).

По-общ вариант на доказателството чрез индукция, който може да се ползва за произволно множество, стига да се открие един от частичните му порядъци без безкрайно намаляващи вериги, представлява:

  1. Доказателство, че всички минимални елементи от множеството притежават свойството
  2. ИХ: Допускане, че свойството е валидно за всички n < m
  3. ИС: Доказателство на свойството за n = m.

(В случая на естествените числа този вариант може да се разглежда като специален случай на посочения по-горе.)

Ефектът на доминото като илюстрация на математическата индукция.

Методът на математическата индукция може успешно да се илюстрира с ефекта на доминото:

  1. Нека падне първата плочка.
  2. Когато падне една плочка, пада и следващата.

Заключението е, че ще паднат "всички" плочки на доминото, и този факт е безспорен.

Пример[редактиране | edit source]

Да докажем твърдението

1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}

за всички естествени числа n. Означаваме това твърдение с P(n). Това е елементарна формула за сума на положителни естествени числа, по-малки или равни на n. Доказателството, че това твърдение важи за всички естествени числа n, се провежда по следния начин:

Проверява се дали твърдението е вярно за n = 1. Тъй като 1(1 + 1) / 2 = 1, то P(1) e вярно. Сега трябва да покажем, че ако твърдението е изпълнено за n = m, то е изпълнено и за n = m + 1. Това може да се направи по следния начин:

Допускаме, че твърдението е вярно за n = m, т. е.

1 + 2 + \cdots + m = \frac{m(m + 1)}{2}.

Прибавяме m + 1 към двете страни, за да не се наруши равенството:


= \frac{m(m + 1)}{2} + \frac{2(m + 1)}{2}
= \frac{(m + 2)(m + 1)}{2}
= \frac{(m + 1)(m + 2)}{2}
= \frac{(m + 1)[(m + 1) + 1]}{2}.

Тогава имаме

1 + 2 + \cdots + (m + 1) = \frac{(m + 1)[(m + 1) + 1]}{2}

Това не е еквивалентно на твърдението P(m + 1) и доказателството е завършено. Символично показахме, че

P(m) \Rightarrow P(m + 1).\,

Източници[редактиране | edit source]


Вижте също[редактиране | edit source]

Естествено число