Wat is volledige inductie?Imp.
3-11-2001
Volledige inductie:
Te bewijzen: E(n)
- Zoek een waarde k waarvoor geldt dat E(k) waar is.
- Bewijs het volgende: als E(n) waar is, dan is E(n + 1) ook waar.
- Nu kun je met zekerheid zeggen: E(n) is waar voor alle n >= k.
Je kunt deze bewijsmethode vergelijken met een oneindig lange dominobaan, waarin de n-de steen omvalt als bewering E(n) waar is. Steen k is de eerste steen die je aantikt (immers: k is het door jou zelf gekozen getal waarvoor geldt dat de bewering waar is).
Omdat we bewezen hebben dat wanneer E(k) waar is E(k + 1) ook waar moet zijn (stap 2 uit de bovenstaande methode), valt steen k + 1 ook.
Maar als steen k + 1 valt, dan valt steen k + 2 ook om en vervolgens steen k + 3 enz.
Het moge duidelijk zijn dat op deze manier alle stenen van de oneindige dominobaan met een nummer hoger dan k om zullen vallen.
Zie het dominoprincipe of hier voor meer voorbeelden!
WvR
3-11-2001
#514 - Bewijzen - Iets anders