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

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

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

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

Выкажам здагадку, што патрабуецца ўсталяваць справядлівасць бясконцай паслядоўнасці сцвярджэнняў, занумараваных натуральнымі лікамі: P_1, P_2, \ldots, P_n, P_{n+1}, \ldots

Прымем, што

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

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

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

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

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

  1. Усталявана, што P_1 дакладна.
  2. Для любога натуральнага n даказана, што калі дакладныя ўсё P_1,P_2, P_3 \ldots P_n, то дакладна і P_{n+1}. (Гэтае сцвярджэнне завецца індукцыйным пераходам.)

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

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

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

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

1 + q + \cdots + q^n = \frac{1 - q^{n + 1}}{1  -q}.

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

База, n = 1:

1 + q = \frac{(1 - q)(1 + q)}{1 - q}=\frac{1 - q^{1 + 1}}{1 - q}.

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

1 + q + \cdots + q^n=\frac{1- q^{n + 1}}{1 - q},

тады

1+q+\cdots +q^n+q^{n+1}=\frac{1-q^{n+1}}{1-q}+q^{n+1}=
=\frac{1-q^{n+1}+(1-q)q^{n+1}}{1-q}=\frac{1-q^{n+1}+q^{n+1}-q^{(n+1)+1}}{1-q}=\frac{1-q^{(n+1)+1}}{1-q},

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

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

1+q+\cdots +q^n=\frac{1-q^{n+1}}{1-q}.

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

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