wd wp Пошук: ⬜

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

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

Дакладнае апісанне

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

, … ,

n + 1

, …

{\displaystyle P_{1},P_{2},\ldots ,P_{n},P_{n+1},\ldots }

$\{\displaystyle P_\{1\},P_\{2\},\ldots ,P_\{n\},P_\{n+1\},\ldots \}$

Прымем, што

Усталявана, што

{\displaystyle P_{1}}

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

{\displaystyle P_{n}}

$\{\displaystyle P_\{n\}\}$ , то дакладна

n + 1

{\displaystyle P_{n+1}}

$\{\displaystyle P_\{n+1\}\}$ . (Гэтае сцвярджэнне завецца індукцыйным пераходам.)

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

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

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

Хай маецца паслядоўнасць сцвярджэнняў

…

{\displaystyle P_{1},P_{2},P_{3}\ldots }

$\{\displaystyle P_\{1\},P_\{2\},P_\{3\}\ldots \}$ . Прымем, што

Усталявана, што

{\displaystyle P_{1}}

$\{\displaystyle P_\{1\}\}$ дакладна. 2. Для любога натуральнага

{\displaystyle n}

$\{\displaystyle n\}$ даказана, што калі дакладныя ўсё

…

{\displaystyle P_{1},P_{2},P_{3}\ldots P_{n}}

$\{\displaystyle P_\{1\},P_\{2\},P_\{3\}\ldots P_\{n\}\}$ , то дакладна і

n + 1

{\displaystyle P_{n+1}}

$\{\displaystyle P_\{n+1\}\}$ . (Гэтае сцвярджэнне завецца індукцыйным пераходам.)

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

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

Прыклады

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

1 + q + ⋯ +

1 −

n + 1

1 − q

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

$\{\displaystyle 1+q+\cdots +q^\{n\}=\{\frac \{1-q^\{n+1\}\}\{1-q\}\}.\}$ Доказ. Індукцыя па n.

База, n = 1:

1 + q

( 1 − q ) ( 1 + q )

1 − q

1 −

1 + 1

1 − q

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

$\{\displaystyle 1+q=\{\frac \{(1-q)(1+q)\}\{1-q\}\}=\{\frac \{1-q^\{1+1\}\}\{1-q\}\}.\}$ Пераход: выкажам здагадку, што

1 + q + ⋯ +

1 −

n + 1

1 − q

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

$\{\displaystyle 1+q+\cdots +q^\{n\}=\{\frac \{1-q^\{n+1\}\}\{1-q\}\},\}$ тады

1 + q + ⋯ +

n + 1

1 −

n + 1

1 − q

n + 1

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

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

1 −

n + 1

( 1 − q )

n + 1

1 − q

1 −

n + 1

−

( n + 1 ) + 1

1 − q

1 −

( n + 1 ) + 1

1 − q

{\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 =\{\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 P_\{n\}\}$ у гэтым доказе — тое ж, што пэўнасць роўнасці

1 + q + ⋯ +

1 −

n + 1

1 − q

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

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

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

Варыяцыі і абагульненні

Літаратура

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

Тэмы гэтай старонкі (1):
Катэгорыя·Матэматычная логіка