In het leerplan wiskunde voor de richtingen van de derde graad D-finaliteit met 12 graaduren wiskunde (III-WisS’’-d) staat in de afbakening van het leerplandoel over bewijsvoering het bewijs door volledige inductie vermeld. In dit artikel onderzoeken we op hoeveel manieren je een rechthoek kan betegelen met tegels van een bepaald formaat. Dit leidt tot een mooi voorbeeld van bewijsvoering met volledige inductie.
LPD 4 De leerlingen beargumenteren wiskundige redeneringen en bewijzen wiskundige uitspraken.
Het is essentieel dat leerlingen niet alleen de redenering begrijpen maar ook inzicht krijgen in de kracht van deze bewijsmethode. Door geregeld een bewijs door volledige inductie aan bod te laten komen, ontwikkelen ze hun logisch denkvermogen en leren ze omgaan met wiskundige argumentatie. Klassieke voorbeelden van bewijzen door volledige inductie zijn het binomium van Newton, de formule van de Moivre en de som van de eerste n kwadraten of derdemachten.
In dit artikel gaan we in op het aantal vlakvullingen van een rechthoek.
Onder een 1xn-rechthoek verstaan we een rechthoek met lengte n en breedte 1. We betegelen deze met 1x1- en 1x2-tegels. Elke mogelijke betegeling noemen we een vlakvulling van de 1xn-rechthoek. Op de afbeelding zie je een 1x1- en 1x2-tegel als ook een mogelijke vlakvulling van een 1x7-rechthoek.
We willen het aantal manieren bepalen waarop een rechthoek van 1 bij n betegeld kan worden met tegels van 1x1 of 1x2. We noteren dit aantal als T(n). Er wordt beweerd dat dit gelijk is aan het (n+1)-ste Fibonacci-getal. We noteren dit getal als Fn+1.
We krijgen:
We bewijzen deze bewering met volledige inductie.
De rij van Fibonacci is een getallenrij waarbij elk getal gelijk is aan de som van de twee voorgaande getallen. De rij start als volgt:
De formele definitie luidt:
Via onderstaande tabel laten we leerlingen aanvoelen dat het aantal vlakvullingen van een 1xn-rechthoek wel degelijk het (n+1)-ste Fibonacci-getal is. Je kan de leerlingen zelf alle mogelijke vlakvullingen laten zoeken en ze zo het verband zelf laten ontdekken. Dit verhoogt de motivatie voor het bewijs van het gevonden verband.
We gaan nu bewijzen dat T(n) = Fn+1 voor alle natuurlijke getallen n, met behulp van volledige inductie.
Voor n = 1 geldt:
Een 1x1-rechthoek kan enkel betegeld worden met één 1x1-tegel.
Dus:
Voor n = 2 geldt:
Een 1x2-rechthoek kan op twee manieren betegeld worden:
Dus:
We veronderstellen dat de stelling klopt voor n en n-1, dus:
We tonen aan dat de stelling dan ook geldt voor n+1, dus dat:
Om dit te bewijzen, bekijken we alle mogelijke manieren om een 1x(n+1)-rechthoek te betegelen.
Er zijn twee mogelijke manieren om te beginnen:
Dan blijft er nog een 1xn-rechthoek over, die op T(n) manieren betegeld kan worden.
Dan blijft er nog een 1x(n–1)-rechthoek over, die op T(n–1) manieren betegeld kan worden.
Daaruit volgt:
Uit de inductiehypothese en de definitie van de rij van Fibonacci volgt:
We hebben aangetoond dat de stelling geldt voor n = 1 en n = 2, en dat als ze geldt voor n en n-1, ze ook geldt voor n+1. Daarom geldt de stelling voor alle natuurlijke getallen n.
Het aantal manieren om een 1xn-rechthoek te betegelen met 1x1- en 1x2-tegels is dus inderdaad het (n+1)-ste Fibonacci-getal.
We willen het aantal manieren bepalen waarop een rechthoek van 2 bij n betegeld kan worden met tegels van 1x2. We noteren dit aantal als T(n). Er wordt beweerd dat dit opnieuw gelijk is aan het (n+1)-ste Fibonacci-getal, met andere woorden:
Deze afbeelding toont een mogelijke vlakvulling van een 2x7-rechthoek.
We bewijzen deze bewering met volledige inductie. Dit bewijs verloopt volledig analoog aan het vorige voorbeeld.
Voor n = 1 geldt:
Een 2x1-rechthoek kan slechts op één manier betegeld worden, namelijk met één 1x2-tegel.
Dus:
Voor n = 2 geldt:
Een 2x2-rechthoek kan op twee manieren betegeld worden:
Dus:
We veronderstellen dat de stelling klopt voor n en n-1, dus:
We tonen aan dat de stelling dan ook geldt voor n+1, dus dat:
Om dit te bewijzen, bekijken we alle mogelijke manieren om een 2x(n+1)-rechthoek te betegelen.
Er zijn twee mogelijke manieren om te beginnen:
1) We leggen eerst verticaal een 1x2-tegel.
Dan blijft er nog een 2xn-rechthoek over, die op T(n) manieren betegeld kan worden.
2) We leggen eerst twee 1x2-tegels onder elkaar.
Dan blijft er nog een 2x(n–1)-rechthoek over, die op T(n–1) manieren betegeld kan worden.
Daaruit volgt:
Uit de inductiehypothese volgt:
We hebben aangetoond dat de stelling geldt voor n = 1 en n = 2, en dat als ze geldt voor n en n-1, ze ook geldt voor n+1. Daarom geldt de stelling voor alle natuurlijke getallen n.
Het aantal manieren om een 2xn-rechthoek te betegelen met 1x2-tegels is dus inderdaad het (n+1)-ste Fibonacci-getal.
Sterkere leerlingen kan je in verschillende situaties een recursieformule voor het aantal vlakvullingen van een rechthoek laten zoeken.
We geven enkele voorbeelden:
Leerlingen kunnen bij elk voorbeeld voor een aantal n-waarden alle vlakvullingen tekenen. Zo kunnen ze telkens de recursieformule voor het aantal vlakvullingen ontdekken.
In het laatste voorbeeld is de lengte van de rechthoek 2n. Laat leerlingen verklaren waarom er voor rechthoeken met een oneven lengte geen enkele vlakvulling mogelijk is.
