\require{AMSmath}

De formule van de Toren van Hanoi

Beste mensen van wisfaq. Ik moet de formule: T(n)=2ⁿ-1 bewijzen met volledige inductie.

Ik dacht dat ik het nu had bewezen met volledige inductie maar mijn leraar zegt dat het niet klopt. Wat heb ik verkeerd gedaan en hoe moet de formule bewezen worden met volledige inductie? Ik heb al op de site gekeken naar de andere vragen maar ik snapte het nog steeds niet.
Bij voorbaat mijn hartelijke dank.

rohan
Leerling bovenbouw havo-vwo - donderdag 30 juni 2005

Antwoord

Hallo,

We willen dus bewijzen dat het aantal nodige stappen voor n schijven gelijk is aan: t(n) = 2ⁿ-1.

Bij een bewijs per inductie ga je niet zomaar een willekeurig getal nemen (zoals jij deed met 123), dan heb je het immers bewezen voor dát specifieke geval, maar nog niet voor alle gevallen (in het algemeen).
De strategie is dat we het eerst bewijzen voor de kleinste n, hier 1. Als dat voldaan is veronderstellen we dat het ook voldaan is voor een bepaalde waarde n = k. Met die veronderstelling proberen we dan te bewijzen dat het ook voor de volgende geldt, namelijk n = k+1

Bewijs voor n = 1
Het aantal nodige stappen is dan: t(1) = 2¹-1 = 1 - klopt!

Veronderstel voldaan voor n = k
Het aantal nodige stappen voor k schijven is: t(k) = 2^k-1

Bewijs voor n = k+1
Aantal nodige stappen zou dan zijn:
t(k+1) = 2^k+1-1
= 2*2^k-1
= 2*2^k-2 + 1
= 2(2^k-1) + 1
= 2(2^k-1) + 1
= 2(t(k)) + 1

We vinden dus dat het aantal stappen nodig voor een k+1 schijven gelijk is aan het dubbel van het aantal nodige stappen voor k schijven, +1. Zou dit kunnen kloppen? We redeneren even verder:

Om k+1 schijven te verplaatsen van stapel 1 naar stapel 2 verplaatsen we eerst k schijven van 1 naar 3. Dit kost ons t(k) stappen. Dan verplaatsen we die laatste (n-de) schijf van 1 naar 2, dit kost 1 stap. Daarna verplaatsen we opnieuw die (k) schijven van 3 naar 2 hetgeen opnieuw t(k) stappen kost.

In het totaal hebben we dan inderdaad: t(k) + 1 + t(k) = 2t(k) + 1

mvg,
Tom

td
donderdag 30 juni 2005

©2001-2024 WisFaq