Þrepasönnun

Úr Wikipediu, frjálsa alfræðiritinu
(Endurbeint frá Þrepun)
Stökkva á: flakk, leita

Þ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:

  1. Sérhvert mengi náttúrulegra talna hefur minnsta stak
  2. 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:

  1. Sýna fram á að fullyrðingin standist fyrir n = 0
  2. Áætla að fullyrðingin sé sönn fyrir n = m
  3. 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[breyta | breyta frumkóða]

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[breyta | breyta frumkóða]

Skref 1[breyta | breyta frumkóða]

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[breyta | breyta frumkóða]

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[breyta | breyta frumkóða]

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:

P(m) \Rightarrow P(m + 1)

Við fáum niðurstöðu með því að sýna að þetta gildi fyrir allar náttúrlegar tölur n:

  1. Þar sem að P(0) er satt, gildir að P(1) sé einnig satt.
  2. Með P(1) leiðir P(2).
  3. ... o.s.frv.
\square þ.s.s.á.

Tenglar[breyta | breyta frumkóða]