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

от Уикипедия, свободната енциклопедия

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

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

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

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

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

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

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