Þ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

Gerum ráð fyrir því að við viljum sanna yrðinguna:

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

fyrir allar náttúrlegar tölur n. Köllum rökyrðinguna $P(n)$ , og getur hún skilað sönnu eða ósönnu gildi.

Sönnun

Skref 1

Sönnum að þetta gildi fyrir $n=0$ .

Þar sem að summa fyrstu 0 náttúrlegu talnanna er 0, og ${\frac {0(0+1)}{2}}=0$ , 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 $n=1$ .

Skref 2

Við áætlum nú að yrðingin sé sönn fyrir n = m, þ.e.

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

Skref 3

Ef að við leggjum $m+1$ við báðar hliðar fáum við:

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

Með algebrulegum umreikningi fæst:

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

þar af leiðir

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

sem er yrðingin fyrir $n=m+1$ . 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: