Матэматычная індукцыя — у матэматыцы — адзін з метадаў доказу. Звычайна выкарыстоўваецца, каб даказаць нейкае сцвярджэнне для ўсіх натуральных лікаў. Для гэтага даказваецца «першае сцвярджэнне» — база індукцыі, і затым даказваецца, што калі любое сцвярджэнне ў бясконцай паслядоўнасці сцвярджэнняў дакладна, то дакладна і наступнае — крок індукцыі.
Дакладнае апісанне
Хай патрабуецца ўсталяваць справядлівасць бясконцай паслядоўнасці сцвярджэнняў, занумараваных натуральнымі лікамі:
Прымем, што Усталявана, што дакладна. (Гэтае сцвярджэнне завецца базай індукцыі.) Для любога натуральнага даказана, што калі дакладна , то дакладна . (Гэтае сцвярджэнне завецца індукцыйным пераходам.) Тады ўсе сцвярджэнні нашай паслядоўнасці дакладныя.
Пэўнасць гэтага метаду доказу выцякае з так званай аксіёмы індукцыі, пятай з аксіём Пеана, якія вызначаюць натуральныя лікі.
Пэўнасць гэтага метаду доказу эквівалентная таму, што ў любым падмностве натуральных лікаў існуе мінімальны элемент.
Існуе таксама варыяцыя, так званы прынцып поўнай матэматычнай індукцыі. Вось яго строгая фармулёўка.
Хай маецца паслядоўнасць сцвярджэнняў . Прымем, што Усталявана, што дакладна. Для любога натуральнага даказана, што калі дакладныя ўсе , то дакладна і . (Гэтае сцвярджэнне завецца індукцыйным пераходам.) Тады ўсе сцвярджэнні ў гэтай паслядоўнасці дакладныя.
Прынцып поўнай матэматычнай індукцыі таксама выцякае з аксіёмы індукцыі і яму эквівалентны, гэта значыць, яго можна ўзяць замест аксіёмы індукцыі ў аксіёмах Пеана.
Прыклады Задача. Даказаць, што, якое б ні было натуральнае n і сапраўднае q, адрозненае ад адзінкі, выконваецца роўнасць
Доказ. Індукцыя па n.
База, n = 1:
Пераход: выкажам здагадку, што
тады
, што і патрабавалася даказаць.
Каментар: пэўнасць сцвярджэння у гэтым доказе — тое ж, што пэўнасць роўнасці
Гл. таксама доказ аднаколернасці ўсіх коней.
Варыяцыі і абагульненні Трансфінітная індукцыя Структурная індукцыя
Літаратура
Н. Я. Виленкин. Индукция. Комбинаторика. Пособие для учителей. М., Просвещение, 1976. — 48 с. Л. И. Головина, И. М. Яглом. Индукция в геометрии // Популярные лекции по математике, выпуск 21. М.: Физматгиз, 1961. — 100 с. Р. Курант, Г. Роббинс. Что такое математика? Глава I, § 2. И. С. Соминский. Метод математической индукции // Популярные лекции по математике, выпуск 3. М.: Наука, 1965. — 58 с.
Катэгорыя:Матэматычная логіка