Þrepasönnun
Þrepasönnun eða þrepun er stærðfræðileg sönnunartækni sem notuð er til þess að sýna fram á að tiltekin fullyrðing sé sönn fyrir allar náttúrlegar tölur. Við þrepasönnun er notast við tvo grunneiginleika náttúrulegra talna:
- Sérhvert mengi náttúrulegra talna hefur minnsta stak
- Ef gefin yrðing P(n) er sönn fyrir eina tölu n er hún einnig sönn fyrir n+1.
Þrepasönnun er unnin í þremur skrefum:
- Sýna fram á að fullyrðingin standist fyrir n = 0
- Áætla að fullyrðingin sé sönn fyrir n = m
- Sýna fram á að það sama gildi fyrir n = m + 1
Gott er að líkja þessu við domino rallý. Ef að við sýnum fram á að fyrsti dominóinn detti, þá getum við áætlað að sá næsti muni falla, og þá getum við sýnt fram á að þeir muni allir detta.
Dæmi
breytaGerum ráð fyrir því að við viljum sanna yrðinguna:
fyrir allar náttúrlegar tölur n. Köllum rökyrðinguna , og getur hún skilað sönnu eða ósönnu gildi.
Sönnun
breytaSkref 1
breytaSönnum að þetta gildi fyrir .
Þar sem að summa fyrstu 0 náttúrlegu talnanna er 0, og , telst þetta sannað.
P(0) = satt
Þó er umdeilt hvort 0 sé tekin með í mengi náttúrulegra talna en á sama hátt og ofan má sýna fram á að yrðingin gildir um .
Skref 2
breytaVið áætlum nú að yrðingin sé sönn fyrir n = m, þ.e.
Skref 3
breytaEf að við leggjum við báðar hliðar fáum við:
Með algebrulegum umreikningi fæst:
þar af leiðir
sem er yrðingin fyrir . ATH að þetta hefur ekki verið sannað, heldur eingöngu hefur verið lögð fram fullyrðingin að P(m) = satt, og að þar af leiði að P(m+1) = satt. Við höfum með öðrum orðum sýnt fram á að yrðingin P(m+1) hljóti að standast ef að yrðingin P(m) stenst:
Við fáum niðurstöðu með því að sýna að þetta gildi fyrir allar náttúrlegar tölur n:
- Þar sem að P(0) er satt, gildir að P(1) sé einnig satt.
- Með P(1) leiðir P(2).
- ... o.s.frv.