Матэматычная індукцыя

З пляцоўкі Вікіпедыя
Перайсці да: рух, знайсці

Матэматычная індукцыя — у матэматыцы — адзін з метадаў доказу. Звычайна выкарыстоўваецца, дзеля доказу нейкага сцвярджэння для ўсіх натуральных лікаў. Для гэтага, даказваецца «першае сцвярджэнне» — база індукцыі, і затым, даказваючы, што калі любое сцвярджэнне ў бясконцай паслядоўнасці сцвярджэнняў дакладна, то дакладна і наступнае — крок індукцыі.

Дакладнае апісанне[правіць | правіць зыходнік]

Выкажам здагадку, што патрабуецца ўсталяваць справядлівасць бясконцай паслядоўнасці сцвярджэнняў, занумараваных натуральнымі лікамі:

Прымем, што

  1. Усталявана, што дакладна. (Гэтае сцвярджэнне завецца базай індукцыі.)
  2. Для любога n даказана, што калі дакладна , то дакладна . (Гэтае сцвярджэнне завецца індукцыйным пераходам.)

Тады ўсё сцвярджэнні нашай паслядоўнасці дакладныя.

Пэўнасць гэтага метаду доказу выцякае з так званай аксіёмы індукцыі, пятай з аксіём Пеана, якія вызначаюць натуральныя лікі.

Пэўнасць гэтага метаду доказу эквівалентная таму, што ў любым падмностве натуральных лікаў існуе мінімальны элемент. Існуе таксама варыяцыя, так званы прынцып поўнай матэматычнай індукцыі. Вось яго строгая фармулёўка:

Хай маецца паслядоўнасць сцвярджэнняў . Прымем, што

  1. Усталявана, што дакладна.
  2. Для любога натуральнага даказана, што калі дакладныя ўсё , то дакладна і . (Гэтае сцвярджэнне завецца індукцыйным пераходам.)

Тады ўсё сцвярджэнні ў гэтай паслядоўнасці дакладныя.

Прынцып поўнай матэматычнай індукцыі таксама выцякае з аксіёмы індукцыі і яму эквівалентны, гэта значыць яго можна ўзяць замест аксіёмы індукцыі ў аксіёмах Пеана.

Прыклады[правіць | правіць зыходнік]

Задача. Даказаць, што, якое б ні было натуральнае n і сапраўднае q, адрозненае ад адзінкі, выконваецца роўнасць

Доказ. Індукцыя па n.

База, n = 1:

Пераход: выкажам здагадку, што

тады

,

што і патрабавалася даказаць.

Каментар: пэўнасць сцвярджэння у гэтым доказе — тое ж, што пэўнасць роўнасці

Варыяцыі і абагульненні[правіць | правіць зыходнік]

Літаратура[правіць | правіць зыходнік]