Sólin Sólin Rís 10:26 • sest 16:02 í Reykjavík
Tunglið Tunglið Rís 01:04 • Sest 15:19 í Reykjavík
Flóð Flóð Árdegis: 01:05 • Síðdegis: 13:31 í Reykjavík
Fjaran Fjara Árdegis: 07:12 • Síðdegis: 20:04 í Reykjavík
Sólin Sólin Rís 10:26 • sest 16:02 í Reykjavík
Tunglið Tunglið Rís 01:04 • Sest 15:19 í Reykjavík
Flóð Flóð Árdegis: 01:05 • Síðdegis: 13:31 í Reykjavík
Fjaran Fjara Árdegis: 07:12 • Síðdegis: 20:04 í Reykjavík
LeiðbeiningarTil baka

Sendu inn spurningu

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=
Forsíða Náttúruvísindi og verkfræði Stærðfræði Hver er skilgreiningin á þrepasönnun?

Flokkun:

8.1.2007
Náttúruvísindi og verkfræði Stærðfræði

Hver er skilgreiningin á þrepasönnun?

Kristín Halla Jónsdóttir

Spyrjandi bætir við:

Má þrepasanna án þess að vera með gildi sitt hvoru megin við jafnaðarmerki? Er hægt að þrepasanna í orðum?

Sönnun með þrepun, þrepasönnun, er ákveðin gerð stærðfræðisönnunar sem þráfaldlega er notuð til að sýna fram á að fullyrðing sé sönn (eða regla gildi) fyrir allar náttúrlegar tölur, það er að segja tölurnar 1, 2, 3, 4, 5, …

Dæmi um fullyrðingu um náttúrlegar tölur sem auðvelt er að sanna með þrepun er:

Summa n fyrstu náttúrlegu talnanna er jöfn tölunni \(\frac{1}{2}\cdot n(n+1)\).

Sönnun þessarar staðhæfingar er meðal fyrstu sannana í námsefni allra nemenda um víða veröld sem kynnast þrepasönnun. Sé summa n fyrstu náttúrlegu talnanna táknuð með „Sum(n)“ má setja regluna fram þannig:

\(Sum(n)=\frac{1}{2}\cdot n(n+1)\)

Hana má nota til að reikna út summu náttúrlegra talna á mun fljótvirkari hátt heldur en með því að leggja tölurnar saman eina af annarri. Samkvæmt reglunni er til dæmis summa fyrstu 1000 náttúrlegu talnanna ½ · 1000 · 1001 = 500 · 1001 = 500500. Að finna svarið þannig er mun fljótlegra heldur en að leggja saman 1 + 2 + 3 + 4 + 5 + … + 998 + 999 + 1000.

Annað dæmi um fullyrðingu sem auðvelt er að sanna með þrepun hljóðar svo:

Summa n fyrstu oddatalnanna er jöfn tölunni n2.

Í sönnuninni kemur gagnkvæm samsvörun milli náttúrlegu talnanna og oddatalnanna við sögu; til náttúrlegu tölunnar n svarar oddatalan 2n – 1. Sé til dæmis n = 9 er samsvarandi oddatala 2 · 9 – 1 = 17, það er 17 er níunda oddatalan: 1, 3, 5, 7, 9, 11, 13, 15, 17.

Sönnun með þrepun er grundvallarlögmál fyrir náttúrlegar tölur. Það er jafngilt öðru grundvallarlögmáli um sömu tölur, velröðunarlögmálinu, sem snýr að því að náttúrlegu tölurnar raðist eftir stærð. Að segja að þessi tvö lögmál séu stærðfræðilega jafngild þýðir að sé gengið út frá því að annað þeirra gildi má sanna að hitt gildi líka.

Lögmálið um þrepun:

Ef P(n) er fullyrðing um náttúrlega tölu n (hverja sem er) og eftirfarandi skilyrði eru uppfyllt:

  1. Fullyrðingin P(1) er sönn.

  2. Ef fullyrðingin P(n) er sönn þá er fullyrðingin P(n + 1) líka sönn.

Þá er fullyrðingin P(n) sönn fyrir allar náttúrlegar tölur n.

Velröðunarlögmálið:

Ef A er hlutmengi (sem ekki er tómt) úr náttúrlegu tölunum þá er til minnsta stak í A.

Í stað 1. skilyrðis í lögmálinu um þrepun er stundum beitt því fráviki að sanna að fullyrðingin gildi fyrir einhverja tiltekna tölu hærri en 1. Niðurstaðan úr þrepasönnuninni verður þá að fullyrðingin sé sönn fyrir allar náttúrlegar tölur frá og með þeirri tölu.

2. skilyrði í lögmálinu kallast þrepunarskref og í mörgum þrepasönnunum er það þar sem hnífurinn stendur í kúnni. Þá þarf að sanna að sé gengið út frá að fullyrðingin gildi fyrir einhverja náttúrlega tölu n þá hljóti hún einnig að gilda fyrir næstu tölu á eftir, það er að segja töluna n + 1.

Þrepasönnun hefur verið útvíkkuð til að nota á öðrum sviðum stærðfræðinnar en talnafræði. Í sinni upphaflegu mynd, þegar hún er notuð til að sanna fullyrðingar um náttúrlegar tölur, koma þó ávallt talnagildi og jöfnur (eða ójöfnur) við sögu.


Þrepasönnun má líkja við dómínókubba: Nóg er að fella þann fyrsta til að þeir falli allir.

Til að varpa ljósi á sönnun með þrepun hefur henni stundum verið líkt við það að fella óendanlega röð af dómínókubbum með því einu að ýta við fyrsta kubbinum. Um þetta skrifar Simon Singh í bók sinni Síðasta setning Fermats (og þar koma hvorki talnagildi né jafnaðarmerki við sögu):

Sönnun með þrepun er því í eðli sínu tveggja skrefa aðferð:

  1. Að sanna að fullyrðingin sé sönn í fyrsta tilfellinu.

  2. Að sanna að sé fullyrðingin sönn í einhverju tilfelli þá hljóti hún að vera sönn í næsta tilfelli þar á eftir.

Ein leið til að fá tilfinningu fyrir sönnun með þrepun er að hugsa sér hin óendanlega mörgu tilfelli sem röð af óendanlega mörgum dómínókubbum. Til að sanna hvert einstakt tilfelli yrði að finna leið til þess að fella tilsvarandi kubb. Það að fella kubbana einn af öðrum tæki hins vegar óendanlega langan tíma og væri endalaust strit, en sönnun með þrepun færir stærðfræðingum það vopn í hendur að fella þá alla með því að fella aðeins þann fyrsta. Sé dómínókubbunum raðað haganlega upp þá mun sá fyrsti sem fellur fella þann næsta sem aftur á móti fellir þann þriðja og svo koll af kolli, endalaust. Sönnun með þrepun skírskotar til þessa áhrifamáttar dómínókubbanna. Hin stærðfræðilega útgáfa af því hvernig dómínókubbar falla einn af öðrum er þess megnug að sanna óendanlega mörg tilfelli með því einu að sanna fyrsta tilfellið, þrepunarskrefið sér svo um afganginn.

Lítum að endingu á dæmi um sönnun með þrepun:

\(Sum(n)=\frac{1}{2}\cdot n(n+1)\)

Fyrsta skrefið er að sýna að formúlan gildi í tilfellinu n = 1 og er það auðvelt því vitað er að „summa“ einnar tölu er talan sjálf, og sé talan 1 sett inn í formúluna í stað n fæst sama svar úr báðum hliðum jöfnunnar: \(Sum(1)=\frac{1}{2}\cdot 1\cdot (1+1)\), það er að segja 1 = 1.

Næsta skref er að sýna að sé formúlan sönn fyrir eitthvert gildi n þá hljóti hún einnig að vera sönn fyrir gildið n + 1. Við gerum því ráð fyrir að formúlan gildi fyrir n: \(Sum(n)=\frac{1}{2}\cdot n(n+1)\) og reiknum því næst út Sum(n + 1):

\(Sum(n+1)=Sum(n)+(n+1)=\frac{1}{2}\cdot n(n+1)+(n+1)\)

Með því að reikna út úr hægri hliðinni og raða liðum á ákjósanlegan hátt fæst:

\(Sum(n+1)=\frac{1}{2}\cdot (n+1)[(n+1)+1]\)

Form þessarar nýju jöfnu er nákvæmlega hið sama og upphaflegu jöfnunnar, það eina sem hefur breyst er að alls staðar er komin talan (n + 1) í stað tölunnar n. Með öðrum orðum, ef formúlan gildir fyrir n þá gildir hún líka fyrir n + 1. Sönnun með þrepun er lokið.

Heimildir

  • Elementary Number Theory. Höf: G. A. Jones og J. M. Jones. Útg. Springer 1999.
  • Síðasta setning Fermats. Höf. S. Singh. Útg. Hið íslenzka bókmenntafélag 2006.

Frekara lesefni á Vísindavefnum og mynd

Höfundur

Kristín Halla Jónsdóttir

dósent í stærðfræði við KHÍ

Útgáfudagur

8.1.2007

Spyrjandi

Sigrún Þöll Þorsteinsdóttir

Efnisorð

Tilvísun

Kristín Halla Jónsdóttir. „Hver er skilgreiningin á þrepasönnun?“ Vísindavefurinn, 8. janúar 2007, sótt 24. nóvember 2024, https://visindavefur.is/svar.php?id=6455.

Kristín Halla Jónsdóttir. (2007, 8. janúar). Hver er skilgreiningin á þrepasönnun? Vísindavefurinn. https://visindavefur.is/svar.php?id=6455

Kristín Halla Jónsdóttir. „Hver er skilgreiningin á þrepasönnun?“ Vísindavefurinn. 8. jan. 2007. Vefsíða. 24. nóv. 2024. <https://visindavefur.is/svar.php?id=6455>.

Chicago | APA | MLA

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki

Senda grein til vinar

=

Hver er skilgreiningin á þrepasönnun?
Spyrjandi bætir við:

Má þrepasanna án þess að vera með gildi sitt hvoru megin við jafnaðarmerki? Er hægt að þrepasanna í orðum?

Sönnun með þrepun, þrepasönnun, er ákveðin gerð stærðfræðisönnunar sem þráfaldlega er notuð til að sýna fram á að fullyrðing sé sönn (eða regla gildi) fyrir allar náttúrlegar tölur, það er að segja tölurnar 1, 2, 3, 4, 5, …

Dæmi um fullyrðingu um náttúrlegar tölur sem auðvelt er að sanna með þrepun er:

Summa n fyrstu náttúrlegu talnanna er jöfn tölunni \(\frac{1}{2}\cdot n(n+1)\).

Sönnun þessarar staðhæfingar er meðal fyrstu sannana í námsefni allra nemenda um víða veröld sem kynnast þrepasönnun. Sé summa n fyrstu náttúrlegu talnanna táknuð með „Sum(n)“ má setja regluna fram þannig:

\(Sum(n)=\frac{1}{2}\cdot n(n+1)\)

Hana má nota til að reikna út summu náttúrlegra talna á mun fljótvirkari hátt heldur en með því að leggja tölurnar saman eina af annarri. Samkvæmt reglunni er til dæmis summa fyrstu 1000 náttúrlegu talnanna ½ · 1000 · 1001 = 500 · 1001 = 500500. Að finna svarið þannig er mun fljótlegra heldur en að leggja saman 1 + 2 + 3 + 4 + 5 + … + 998 + 999 + 1000.

Annað dæmi um fullyrðingu sem auðvelt er að sanna með þrepun hljóðar svo:

Summa n fyrstu oddatalnanna er jöfn tölunni n2.

Í sönnuninni kemur gagnkvæm samsvörun milli náttúrlegu talnanna og oddatalnanna við sögu; til náttúrlegu tölunnar n svarar oddatalan 2n – 1. Sé til dæmis n = 9 er samsvarandi oddatala 2 · 9 – 1 = 17, það er 17 er níunda oddatalan: 1, 3, 5, 7, 9, 11, 13, 15, 17.

Sönnun með þrepun er grundvallarlögmál fyrir náttúrlegar tölur. Það er jafngilt öðru grundvallarlögmáli um sömu tölur, velröðunarlögmálinu, sem snýr að því að náttúrlegu tölurnar raðist eftir stærð. Að segja að þessi tvö lögmál séu stærðfræðilega jafngild þýðir að sé gengið út frá því að annað þeirra gildi má sanna að hitt gildi líka.

Lögmálið um þrepun:

Ef P(n) er fullyrðing um náttúrlega tölu n (hverja sem er) og eftirfarandi skilyrði eru uppfyllt:

  1. Fullyrðingin P(1) er sönn.

  2. Ef fullyrðingin P(n) er sönn þá er fullyrðingin P(n + 1) líka sönn.

Þá er fullyrðingin P(n) sönn fyrir allar náttúrlegar tölur n.

Velröðunarlögmálið:

Ef A er hlutmengi (sem ekki er tómt) úr náttúrlegu tölunum þá er til minnsta stak í A.

Í stað 1. skilyrðis í lögmálinu um þrepun er stundum beitt því fráviki að sanna að fullyrðingin gildi fyrir einhverja tiltekna tölu hærri en 1. Niðurstaðan úr þrepasönnuninni verður þá að fullyrðingin sé sönn fyrir allar náttúrlegar tölur frá og með þeirri tölu.

2. skilyrði í lögmálinu kallast þrepunarskref og í mörgum þrepasönnunum er það þar sem hnífurinn stendur í kúnni. Þá þarf að sanna að sé gengið út frá að fullyrðingin gildi fyrir einhverja náttúrlega tölu n þá hljóti hún einnig að gilda fyrir næstu tölu á eftir, það er að segja töluna n + 1.

Þrepasönnun hefur verið útvíkkuð til að nota á öðrum sviðum stærðfræðinnar en talnafræði. Í sinni upphaflegu mynd, þegar hún er notuð til að sanna fullyrðingar um náttúrlegar tölur, koma þó ávallt talnagildi og jöfnur (eða ójöfnur) við sögu.


Þrepasönnun má líkja við dómínókubba: Nóg er að fella þann fyrsta til að þeir falli allir.

Til að varpa ljósi á sönnun með þrepun hefur henni stundum verið líkt við það að fella óendanlega röð af dómínókubbum með því einu að ýta við fyrsta kubbinum. Um þetta skrifar Simon Singh í bók sinni Síðasta setning Fermats (og þar koma hvorki talnagildi né jafnaðarmerki við sögu):

Sönnun með þrepun er því í eðli sínu tveggja skrefa aðferð:

  1. Að sanna að fullyrðingin sé sönn í fyrsta tilfellinu.

  2. Að sanna að sé fullyrðingin sönn í einhverju tilfelli þá hljóti hún að vera sönn í næsta tilfelli þar á eftir.

Ein leið til að fá tilfinningu fyrir sönnun með þrepun er að hugsa sér hin óendanlega mörgu tilfelli sem röð af óendanlega mörgum dómínókubbum. Til að sanna hvert einstakt tilfelli yrði að finna leið til þess að fella tilsvarandi kubb. Það að fella kubbana einn af öðrum tæki hins vegar óendanlega langan tíma og væri endalaust strit, en sönnun með þrepun færir stærðfræðingum það vopn í hendur að fella þá alla með því að fella aðeins þann fyrsta. Sé dómínókubbunum raðað haganlega upp þá mun sá fyrsti sem fellur fella þann næsta sem aftur á móti fellir þann þriðja og svo koll af kolli, endalaust. Sönnun með þrepun skírskotar til þessa áhrifamáttar dómínókubbanna. Hin stærðfræðilega útgáfa af því hvernig dómínókubbar falla einn af öðrum er þess megnug að sanna óendanlega mörg tilfelli með því einu að sanna fyrsta tilfellið, þrepunarskrefið sér svo um afganginn.

Lítum að endingu á dæmi um sönnun með þrepun:

\(Sum(n)=\frac{1}{2}\cdot n(n+1)\)

Fyrsta skrefið er að sýna að formúlan gildi í tilfellinu n = 1 og er það auðvelt því vitað er að „summa“ einnar tölu er talan sjálf, og sé talan 1 sett inn í formúluna í stað n fæst sama svar úr báðum hliðum jöfnunnar: \(Sum(1)=\frac{1}{2}\cdot 1\cdot (1+1)\), það er að segja 1 = 1.

Næsta skref er að sýna að sé formúlan sönn fyrir eitthvert gildi n þá hljóti hún einnig að vera sönn fyrir gildið n + 1. Við gerum því ráð fyrir að formúlan gildi fyrir n: \(Sum(n)=\frac{1}{2}\cdot n(n+1)\) og reiknum því næst út Sum(n + 1):

\(Sum(n+1)=Sum(n)+(n+1)=\frac{1}{2}\cdot n(n+1)+(n+1)\)

Með því að reikna út úr hægri hliðinni og raða liðum á ákjósanlegan hátt fæst:

\(Sum(n+1)=\frac{1}{2}\cdot (n+1)[(n+1)+1]\)

Form þessarar nýju jöfnu er nákvæmlega hið sama og upphaflegu jöfnunnar, það eina sem hefur breyst er að alls staðar er komin talan (n + 1) í stað tölunnar n. Með öðrum orðum, ef formúlan gildir fyrir n þá gildir hún líka fyrir n + 1. Sönnun með þrepun er lokið.

Heimildir

  • Elementary Number Theory. Höf: G. A. Jones og J. M. Jones. Útg. Springer 1999.
  • Síðasta setning Fermats. Höf. S. Singh. Útg. Hið íslenzka bókmenntafélag 2006.

Frekara lesefni á Vísindavefnum og mynd

...