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

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

Хай патрабуецца ўсталяваць справядлівасць бясконцай паслядоўнасці сцвярджэнняў, занумараваных натуральнымі лікамі: ${\displaystyle P_{1},P_{2},\ldots ,P_{n},P_{n+1},\ldots }$

Прымем, што

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

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

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

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

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

Хай маецца паслядоўнасць сцвярджэнняў ${\displaystyle P_{1},P_{2},P_{3},\ldots }$. Прымем, што

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

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

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

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

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

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

База, n = 1:

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

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

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

тады

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

${\displaystyle ={\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}}}$,

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

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

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

• Гл. таксама доказ аднаколернасці ўсіх коней.

• Трансфінітная індукцыя
• Структурная індукцыя

• Н. Я. Виленкин. Индукция. Комбинаторика. Пособие для учителей. М., Просвещение, 1976. — 48 с.
• Л. И. Головина, И. М. Яглом. Индукция в геометрии // Популярные лекции по математике, выпуск 21. М.: Физматгиз, 1961. — 100 с.
• Р. Курант, Г. Роббинс. Что такое математика? Глава I, § 2.
• И. С. Соминский. Метод математической индукции // Популярные лекции по математике, выпуск 3. М.: Наука, 1965. — 58 с.