Прейдз на змист

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

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

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

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

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

История

[ушориц | ушор жридло]

Найвчаснєйши шлїди математичней индукциї можу ше найсц у Еуклидовим доказу же исную безконєчно вельо прости числа, и Баскарней циклидней методи. Форма доказу зоз математичну индукцию ше зявює у кнїжки хтору написал Ал-Караджи коло 1000. року, хтори медзи иншим жадал доказац биномну теорему и Паскалов троугелнїк. Анї єден од тих старих математичарох експлицитно нє дал индуктивну гипотезу. Перше викладанє принципу индукциї дал Франческо Мауролико, у своїм дїлу Arithmeticorum libri duo 1575.року, хтори хасновал тоту технїку же би доказал же сума перших n нєпарних цалих числох єднака зоз Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n^2} . Индукцию, тиж, нєзависно доказали Швайцарец Якоб Бернули и Французи Паскал и Ферма.

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

[ушориц | ушор жридло]

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

  1. База-основа индукциї: указує же виказ важаци кед Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = 0} .
  2. Индукцийни крочай: указує же кед виказ важаци за Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = m} , вец исти виказ важи и за Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = m + 1} .

Хаснованє слова кед ше у индукцийним крочаю наволує индуктивна гипотеза. У индукцийним крочаю, предпоставя ше же индуктивна гипотеза важи – важаца (точнєйше же виказ точни за Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = m} ) и вец ше хаснує тота предпоставка же би ше доказал виказ за Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = m + 1} .

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

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

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

Основна предпоставка лєбо аксиома индукциї (прилапює ше, нє доказує) написана зоз лоґичнима символами, Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle \forall P, (P(0) \land \forall k [P(k) \Rightarrow P(k+1)]) \Rightarrow \forall n P(n) } Дзе Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P} дати виказ, а Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n} природне число.

Крочай 1. доказац Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(0)} - формула важи за цале число Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle 0} .

Крочай 2. доказац же за кажде природне число Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle k} , Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(k)} импликує Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(k+1)} . Же би ше тото спроведло, предпоставя ше же важи Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(k)} и указує же зоз тей предпоставки шлїдзи же важи Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(k+1)} . То нє значи замена Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle (k+1)} до Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(k)} - тото барз часта гришка хтора ше состої зоз предпоставяня того цо би ше требало ище доказац.

Вєдно крочаї 1. и 2. импликую же Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(n)} важи за кажде Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n} векше лєбо єднаке Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle 0} . У общим случаю, кед же Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(s)} доказане, дзе Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle s} може буц негативне цале число (задумаме домини нумерисани од -20 та нависше), вец P важи за кажде n векше лєбо єднаке Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle s} .

Приклад

[ушориц | ушор жридло]

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

Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}}

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

Преверме чи тот виказ точни за Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = 1} . Сума самого числа Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle 1} то число Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle 1} . А Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle \frac{1(1 + 1)}{2} =1} . Значи, же виказ точни за Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = 1} . Доказали зме же P(1) важи.

Тераз мушиме указац же кед виказ важи кед Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = m} , вец то тиж важи и кед Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = m+1} . Тото мож доказац на шлїдуюци способ:

Предпоставиме же виказ точни за Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n = m} , тє. Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle 1 + 2 + \cdots + m = \frac{m(m + 1)}{2}}

Зоз додавањом Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle m + 1} зоз обидвох бокох ше нє меня єднакосц

Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle 1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1)} .

Зоз алгебарску манипулацию, з правого боку доставаме Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle = \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}. }

И на концу:

Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle 1 + 2 + \cdots + (m + 1) = \frac{(m + 1)((m + 1) + 1)}{2} }

Обачиме же тото еквивалентне зоз твердзеньом Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(m + 1)} . Тот доказ кондиционални: Направели зме предпоставку же Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(m)} точне, и зоз того зме виведли Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(m + 1)} . Прето, значи же кед Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(m)} точне та вец и Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(m + 1)} муши буц точне. Симболично, зме приказали же Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(m) \Rightarrow P(m + 1).\,}

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

  1. Знаме же Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(1)} точне.
  2. Прето же Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(1)} импликує Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(1 + 1)} , точне и Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(2)} .
  3. Подобно, прето же Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(2)} импликує Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(2 + 1)} , доставаме Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(3)} .
  4. Зоз Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(3)} , доставаме Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(4)} .
  5. Зоз Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(4)} , шлїдзи Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(5)} .
  6. И так далєй. (Ту наступа аксиома математичней индукциї.)
  7. Можеме заклюучиц же Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle P(n)} важи за кажде природне число Рашчлањивање није успело (SVG (MathML се може укључити преко плугина за прегледач): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/rsk.wikipedia.org/v1/":): {\displaystyle n} .


Превьате зоз "https://rsk.wikipedia.org/w/index.php?title=Математична_индукция&oldid=2871"