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

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

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

1. База: Твърдението се проверява за n = 1.
2. Индуктивна стъпка: Предполагаме, че твърдението е вярно за n = k (това е т. нар. индуктивно предположение), и оттук доказваме, че твърдението е вярно за n = k + 1 (това е т. нар. индуктивно заключение).

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

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

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

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

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

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

Ефектът на доминото е нагледно представяне на доказателството чрез математическа индукция:

1. Бутаме първата плочка.
2. Всяка паднала плочка бута следващата.

Следователно ще паднат всички плочки на доминото.

Пример

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

$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).\,$

Вижте също

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