Wp/rsk/Математична индукция

Математична индукция ше може нєформално илустровац зоз секвенциялним ефекторм падаюцих доминох

Математична индукция то способ математичного доказованя хтори ше найчастейше хаснує же би ше утвердзело чи виказ точни за шицки природни числа. То ше роби зоз:

1. Доказованьом же перши виказ у безконєчним шоре виказу точни
2. Доказованє же даяки виказ у безконєчним шоре виказох точни, вец точни виказ хтори шлїдзи после нього

Математичну индукцию нє треба похопиц як форму индукцийного заключованя, математична индукция то форма дедукцийного заключованя.

История

Найвчаснєйши шлїди математичней индукциї можу ше найсц у Еуклидовим доказу же исную безконєчно вельо прости числа, и Баскарней циклидней методи. Форма доказу зоз математичну индукцию ше зявює у кнїжки хтору написал Ал-Караджи коло 1000. року, хтори медзи иншим жадал доказац биномну теорему и Паскалов троугелнїк. Анї єден од тих старих математичарох експлицитно нє дал индуктивну гипотезу. Перше викладанє принципу индукциї дал Франческо Мауролико, у своїм дїлу Arithmeticorum libri duo 1575.року, хтори хасновал тоту технїку же би доказал же сума перших n нєпарних цалих числох єднака зоз $n^{2}$. Индукцию, тиж, нєзависно доказали Швайцарец Якоб Бернули и Французи Паскал и Ферма.

Формални опис

Найєдноставнєйша и найзвичайнєйша форма математичней индукциї хаснує ше за доказованє же даєден виказ важи за шицки природни числа n. Доказ ше состої зоз двох крочайох:

1. База-основа индукциї: указує же виказ важаци кед $n=0$.
2. Индукцийни крочай: указує же кед виказ важаци за $n=m$, вец исти виказ важи и за $n=m+1$.

Хаснованє слова кед ше у индукцийним крочаю наволує индуктивна гипотеза. У индукцийним крочаю, предпоставя ше же индуктивна гипотеза важи – важаца (точнєйше же виказ точни за $n=m$) и вец ше хаснує тота предпоставка же би ше доказал виказ за $n=m+1$.

Тота метода функционує на шлїдуюци способ:

Перше ше докаже же виказ точни за початну вредносц, а потим ше докаже же процес преходзеня зоз даякей вредносци на шлїдуюцу точни. Кед же обидва доказани, вец ше до точносци виказох за кажду вредносц може дойсц зоз повторйованьом того поступку. То мож спатрац як ефект доминох хтори приказани на слики. Кед маме длугоки шор доминох и кед важи же:

1. Перша домина може спаднуц
2. Гоч хтора домина кед спаднє, звалї и шлїдуюцу домину, теди можеме заключиц же шицки домини спадню, кед ше перша звалї.

Основна предпоставка лєбо аксиома индукциї (прилапює ше, нє доказує) написана зоз лоґичнима символами, $\forall P,(P(0)\land \forall k[P(k)\Rightarrow P(k+1)])\Rightarrow \forall nP(n)$ Дзе $P$ дати виказ, а $n$ природне число.

Крочай 1. доказац $P(0)$ - формула важи за цале число $0$.

Крочай 2. доказац же за кажде природне число $k$, $P(k)$ импликує $P(k+1)$. Же би ше тото спроведло, предпоставя ше же важи $P(k)$ и указує же зоз тей предпоставки шлїдзи же важи $P(k+1)$. То нє значи замена $(k+1)$ до $P(k)$ - тото барз часта гришка хтора ше состої зоз предпоставяня того цо би ше требало ище доказац.

Вєдно крочаї 1. и 2. импликую же $P(n)$ важи за кажде $n$ векше лєбо єднаке $0$. У общим случаю, кед же $P(s)$ доказане, дзе $s$ може буц негативне цале число (задумаме домини нумерисани од -20 та нависше), вец P важи за кажде n векше лєбо єднаке $s$.

Приклад

Предпоставяме же жадаме доказац виказ:

$1+2+3+\cdots +n={\frac {n(n+1)}{2}}$

За шицки природни числа n; означиме тот виказ як P(n). То формула за суму позитивних природних числох менших або єднакиx зоз числом n. Доказ же тот виказ точни за шицки природни числа n:

Преверме чи тот виказ точни за $n=1$. Сума самого числа $1$ то число $1$. А ${\frac {1(1+1)}{2}}=1$. Значи, же виказ точни за $n=1$. Доказали зме же P(1) важи.

Тераз мушиме указац же кед виказ важи кед $n=m$, вец то тиж важи и кед $n=m+1$. Тото мож доказац на шлїдуюци способ:

Предпоставиме же виказ точни за $n=m$, тє. $1+2+\cdots +m={\frac {m(m+1)}{2}}$

Зоз додавањом $m+1$ зоз обидвох бокох ше нє меня єднакосц

$1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)$.

Зоз алгебарску манипулацию, з правого боку доставаме $={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}={\frac {(m+1)(m+2)}{2}}={\frac {(m+1)((m+1)+1)}{2}}.$

И на концу:

$1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}$

Обачиме же тото еквивалентне зоз твердзеньом $P(m+1)$. Тот доказ кондиционални: Направели зме предпоставку же $P(m)$ точне, и зоз того зме виведли $P(m+1)$. Прето, значи же кед $P(m)$ точне та вец и $P(m+1)$ муши буц точне. Симболично, зме приказали же $P(m)\Rightarrow P(m+1).\,$

Тераз, кед бизме закончели, хаснуєме процес математичней индукциї:

1. Знаме же $P(1)$ точне.
2. Прето же $P(1)$ импликує $P(1+1)$, точне и $P(2)$.
3. Подобно, прето же $P(2)$ импликує $P(2+1)$, доставаме $P(3)$.
4. Зоз $P(3)$, доставаме $P(4)$.
5. Зоз $P(4)$, шлїдзи $P(5)$.
6. И так далєй. (Ту наступа аксиома математичней индукциї.)
7. Можеме заклюучиц же $P(n)$ важи за кажде природне число $n$.