Математическа индукция
от Уикипедия, свободната енциклопедия
Математическата индукция е метод за математическо доказателство, използван за доказване на свойства на естествените числа и на други множества, равномощни с множеството на естествените числа.
Доказателство, базирано на математическата индукция, за дадено свойство на всички естествени числа n, обикновено се свежда до три стъпки:
- Тривиално доказателство на доказуемото свойство за n=1
- Индукционна хипотеза (ИХ): Допускане, че доказуемото свойство е валидно за n=k
- Индукционна стъпка (ИС): Доказателство на свойството за n=k+1, в което се ползва като доказана индукционната хипотеза.
Принципът на математическата индукция обикновено се приема като аксиома на естествените числа (вижте Аксиоми на Пеано).
По-общ вариант на доказателството чрез индукция, който може да се ползва за произволно множество, стига да се открие един от частичните му порядъци без безкрайно намаляващи вериги представлява:
- Доказателство, че всички минимални елементи от множеството притежават свойството
- ИХ: Допускане, че свойството е валидно за всички n<m
- ИС: Доказателство на свойството за n=m.
(В случая на естествените числа, този вариант може да се разглежда като специален случай на посочения по-горе.)
