Математическа индукция
From Wikipedia, the free encyclopedia
Математическата индукция е метод за математическо доказателство, използван за доказване на свойства на естествените числа и на други множества, равномощни с множеството на естествените числа. Типична е употребата ѝ за доказване, че дадено твърдение е вярно за всички естествени числа. Това се прави, като се проверява, че твърдението е вярно за числото 1, след което се доказва, че ако твърдението е вярно за някое естествено число, то е вярно и за следващото естествено число.
По-формално казано, всяко доказателство чрез математическа индукция съдържа два етапа:
- База: Твърдението се проверява за n = 1.
- Индуктивна стъпка: Предполагаме, че твърдението е вярно за n = k (това е т. нар. индуктивно предположение), и оттук доказваме, че твърдението е вярно за n = k + 1 (това е т. нар. индуктивно заключение).
Принципът на математическата индукция обикновено се приема като аксиома на естествените числа (вж. аксиомите на Пеано).
По-общ вариант на доказателството чрез индукция, който може да се ползва за произволно множество, стига да се открие един от частичните му порядъци без безкрайно намаляващи вериги:
- Доказваме, че всички минимални елементи от множеството притежават свойството
- Предполагаме, че свойството е валидно за всички n < m
- Доказваме свойството за n = m.
(В случая на естествените числа тази схема се свежда до описаната по-горе.)
Методът на математическата индукция може да се обобщи за доказване на твърдения относно индуктивни структури — графи, дървета, масиви и т.н. Това обобщение е известно като структурна индукция и се използва в математическата логика и в информатиката.
Ефектът на доминото е нагледно представяне на доказателството чрез математическа индукция:
- Бутаме първата плочка.
- Всяка паднала плочка бута следващата.
Следователно ще паднат всички плочки на доминото.