Logica, verzamelingen en relaties [3, 1 ed.] 9789492231550, 9789492231383 [PDF]

Zitiervorschau

Logica, verzamelingen en relaties Cursusdeel 3 Blok 3 Inductie

Open Universiteit Faculteit Management, Science & Technology Auteur mw. drs. J.S. Lodder Deze cursus is grotendeels samengesteld uit delen van de cursussen Discrete wiskunde A (T07131) en Discrete wiskunde B (T33131), waaraan de volgende personen hebben meegewerkt: dhr. dr. R.J. Beerends, auteur dhr. A.S. Haven, auteur mw. drs. J. S. Lodder, auteur dhr. dr. H.M. Mulder, auteur dhr. dr. M. de Rijke, auteur dhr. dr. E.G.C. Thijsse, auteur dhr. drs. J.H. Timmerman, auteur mw. drs. H. Verhage, adviseur dhr. ir. E.M. van de Vrie, auteur Programmaleiding mw. prof. dr. T.E.J. Vos

CURSUSDEEL 3

Logica, verzamelingen en relaties Inductie

Productie Open Universiteit Redactie John Arkenbout Arnold van der Leer Lay-out Maria Wienbröker-Kampermann Omslag Team Visuele communicatie, Open Universiteit Druk- en bindwerk Canon Business Services

Dit materiaal is gelicentieerd onder de Creative Commons-licentie NaamsvermeldingNietCommercieel-GeenAfgeleideWerken 4.0. Zie de licentie voor details: https://creativecommons.org/licenses/ by-nc-nd/4.0/legalcode This content is licensed under the Creative Commons license Attribution-NoncommercialNoDerivs 4.0. See licence for more details: https://creativecommons.org/licenses/ by-nc-nd/4.0/legalcode Eerste druk: 2016 Illustratieverantwoording ANP‐Foto, Rijswijk: blz. 40 Archiv für Kunst und Geschichte, Berlijn: blz. 24 Fototeca Archivi Alinari, Florence: blz. 30 Red Band Venco bv, Breda: blz. 18 Spaarnestad fotoarchief/Stichting NFGC, Haarlem: blz. 9

IB0402_50133_07062016 ISBN 978 94 92231 55 0 (serie) ISBN 978 94 92231 38 3 (deel 3) Cursuscode IB0402

Structuur van de cursus Logica, verzamelingen en relaties

Onderdeel

Blok

Leereenheid

Cursusboek 1

1 Logica

Introductie tot de cursus 1 2 3 4

Bladzijde

Propositielogica Wetten van de propositielogica Predikaatlogica Wetten van de predikaatlogica

Aanwijzingen en terugkoppelingen blok 1 Bijlagen: Symbolen en Grieks alfabet Register Cursusboek 2

2 Verzamelingen en relaties

5 6 7 8 9 10

Verzamelingenalgebra Boolealgebra’s Grafen Relaties en functies Equivalentierelaties Ordeningen

Aanwijzingen en terugkoppelingen blok 2 Bijlagen: Symbolen en Grieks alfabet Register Cursusboek 3

Cursussite

3 Inductie

11 Inductie en recursie 12 Inductieve bewijzen

9 37

Aanwijzingen en terugkoppelingen blok 3 Bijlagen: Symbolen en Grieks alfabet Register

51 71 76

http://youlearn.ou.nl

5

Blok 3

Inductie

Inductie en recursie Introductie Leerkern 11.1 11.2

9 11

Inductieve definities van verzamelingen 11 Recursie 16 11.2.1 Recursieve definities 16 11.2.2 Rekenkundige rijen en eindige rekenkundige reeksen 22 11.2.3 Meetkundige rijen en eindige meetkundige reeksen 25 11.2.4 Recurrente betrekkingen 28

Samenvatting Zelftoets

34

33

Leereenheid 11

Inductie en recursie

INTRODUCTIE

Driehoeksgetallen

In tests die gebruikt worden om de intelligentie te ‘bepalen’, komen steevast vragen voor als: wat is het volgende getal in de rij 1, 3, 6, 10, ...? Het correct beantwoorden van zo’n vraag komt er op neer dat in de gegeven rij een regelmaat herkend moet worden. Meestal is de regelmaat in die tests gebaseerd op rekenkundige bewerkingen als optellen en vermenigvuldigen. Zo dadelijk laten we zien dat dit ook voor de rij 1, 3, 6, 10, ... geldt. De getallen uit deze rij hebben trouwens een rijke historie. Bij de Grieken stonden ze bekend als de driehoeksgetallen. Die naam wordt verklaard door het feit dat ze optreden als we het aantal objecten tellen dat in een driehoeksvorm is gestapeld. Denk bijvoorbeeld aan ‘blikken gooien’.

Het driehoeksgetal 10 (het aantal gestapelde blikken) Halen we van onderaf steeds een laag weg, dan treden de driehoeksgetallen 6, 3 en 1 op.

Uit de driehoekseigenschap volgt direct de regelmaat in de rij: voor iedere laag in de stapel is steeds één blik meer nodig, met andere woorden, de onderlinge verschillen tussen de getallen in de rij worden steeds één groter. Het volgende getal in de rij is dus 15. Is de regelmaat eenmaal gevonden, dan kennen we niet alleen het volgende getal, maar ook het daarop volgende getal (21 in dit voorbeeld), enzovoort. Om het gebruik van het woord enzovoort, of de er mee vergelijkbare ‘enzovoortstippeltjes ...’, draait het in deze leereenheid. Op het eerste gezicht lijkt het misschien vreemd om daar een hele leereenheid aan te besteden. Laten we daarom met wat voorbeelden proberen aan te geven welke problemen er zoal rond dit ‘enzovoort’ zijn. Allereerst kan het erg lastig zijn om het volgende getal te vinden. Een aardig voorbeeld is het rijtje 1, 2, 16, 272, 7936, waaraan wel degelijk een regelmaat ten grondslag ligt. Het verrassende is dat deze soms zeer gecompliceerde rijtjes vaak met een erg eenvoudige methode te verkrijgen zijn, de zogenaamde inductieve of recursieve definities. Bovendien duiken deze ‘vreemde’ rijtjes getallen regelmatig op in allerlei problemen in de (toegepaste) wiskunde. Een tweede probleem is dat het heel goed mogelijk is om een gegeven rij getallen op verschillende manieren voort te zetten. Iedereen zal de rij 1, 2, 3, 4 vervolgen met 5 omdat we er de regelmaat van de natuurlijke getallen in zien. Maar 1, 2, 3 en 4 zijn ook precies de aantallen priemgetallen die ≤ 2, respectievelijk ≤ 4, ≤ 6 en ≤ 8 zijn (een priemgetal is een getal ≥ 2 dat alleen door 1 en zichzelf deelbaar is, zoals 2, 3, 5 en 7). Omdat er ook 4 priemgetallen ≤ 10 zijn, zouden we de rij 1, 2, 3, 4 net zo goed met 4 kunnen vervolgen. Zo zijn er nog vele andere manieren te verzinnen om het volgende getal in de rij 1, 2, 3, 4, ... te krijgen. De eerder genoemde inductieve of recursieve definities zorgen ervoor dat dit probleem zich niet voordoet. In deze voorbeelden hebben we ons beperkt tot rijtjes getallen, maar dezelfde ideeën en problemen zijn bijvoorbeeld ook van toepassing op rijtjes willekeurige symbolen. Inductieve en recursieve definities zijn dan ook een veelgebruikt hulpmiddel in de theorie van de formele talen. In feite geldt hetzelfde voor alle gebieden van de (toegepaste) wiskunde waarin discrete structuren een rol spelen. In de volgende leereenheid zult u zien hoe we inductie ook kunnen gebruiken om eigenschappen te bewijzen. LEERDOELEN

Na het bestuderen van deze leereenheid wordt verwacht dat u – inductieve en recursieve definities kunt lezen en kunt opstellen – de drie onderdelen basis, inductiestap en uitsluiting in een inductieve definitie kunt onderscheiden – met recursief gedefinieerde notaties en begrippen kunt werken en in het bijzonder de notaties met het som- en het productteken kunt gebruiken – rekenkundige rijen en eindige rekenkundige reeksen kunt herkennen en de som van een eindige rekenkundige reeks kunt bepalen – meetkundige rijen en eindige meetkundige reeksen kunt herkennen en de som van een eindige meetkundige reeks kunt bepalen

– de begrippen recurrente betrekking en startwaarde(n) kent en kunt toepassen – voor eenvoudige recurrente betrekkingen een oplossing in de vorm van een formule kunt afleiden.

LEERKERN 11.1

Natuurlijke getallen L. Kronecker, 18231891, Duits wiskundige

‘enzovoort’ of ‘...’ precies maken.

Inductieve definities van verzamelingen

De voorbeelden in de introductie betroffen steeds rijtjes getallen. Omdat rijtjes uiteindelijk gedefinieerd zijn in termen van verzamelingen (zie definitie 8.7), beginnen we de behandeling van het begrip inductie met de inductieve definitie van verzamelingen. Het meest eenvoudige, en tevens meest fundamentele, voorbeeld zal daarbij de verzameling van natuurlijke getallen zijn. In vorige leereenheden werd ervan uitgegaan dat u met bekend bent: de natuurlijke getallen {0, 1, 2, 3, ...} nemen we als vanzelfsprekend (‘natuurlijk’) aan. Immers, als kind leren we al tellen en leren we het verband van de telwoorden met aantallen. Er is zelfs het volgende beroemde citaat van Kronecker over de wiskunde: ‘de natuurlijke getallen heeft de lieve God gemaakt, al het andere is mensenwerk’, waarmee hij doelde op het feit dat de natuurlijke getallen het fundament vormen waarmee de rest van de wiskunde is op te bouwen. Voor zo’n belangrijk fundament zijn de ‘enzovoort-stippeltjes’ in de definitie = {0, 1, 2, 3, ...} eigenlijk wel erg mager. Natuurlijk weet u wel welk element er na 3 komt, en vervolgens na 4, enzovoort. Maar met in het achterhoofd de problemen die geschetst werden in de introductie, stellen we ons nu de vraag hoe dit ‘enzovoort’ precies gemaakt kan worden. De essentie van ‘enzovoort’ is dat we erop vertrouwen dat we allemaal dezelfde regelmaat herkennen (ook als u ‘van de planeet Mars’ mocht komen!): het volgende getal in ontstaat uit het vorige door er 1 bij op te tellen. Beginnend bij 0  , krijgen we zo eerst 0 + 1 = 1  , vervolgens 1 + 1 = 2  , 2 + 1 = 3  , enzovoort. Maar nu zitten we opnieuw met ‘enzovoort’! Gelukkig is dat eenvoudig te vermijden door de optelregel abstract te formuleren: als n  , dan geldt dat n + 1  . Hiermee kunnen we dan uiteindelijk definiëren zonder gebruik te maken van een ‘enzovoort’. is de verzameling die precies bestaat uit de getallen die verkregen kunnen worden door het toepassen van de volgende twee regels: i 0 ii als n  , dan n + 1  .

i en ii zijn kleine versies van de Romeinse I en II.

Voor het gemak zijn de twee regels met i en ii aangegeven. Door te beginnen met 0 en herhaald regel ii toe te passen, verkrijgen we alle getallen van . Dat , naast de elementen verkregen door deze twee regels, geen andere elementen bevat, wordt tot uitdrukking gebracht met de woorden ‘die precies bestaat uit’. Voortaan leggen we dit formeel vast in een aparte derde regel, de uitsluitingsregel: iii bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen.

Inductieve definitie van Basis

Regel i

Inductiestap

Regel ii

Uitsluiting

Regel iii

VOORBEELD

Basis Inductiestap Uitsluiting

Het in deze specifieke vorm definiëren van de verzameling wordt de inductieve definitie van genoemd. In regel i definiëren we het startelement of basiselement van waaruit we zullen gaan opbouwen. Het is gebruikelijk om deze regel de basis van de inductieve definitie te noemen. In regel ii laten we zien hoe we vanuit bestaande elementen weer nieuwe elementen van de verzameling kunnen maken. Deze regel wordt de inductiestap genoemd. Regel iii noemen we kortweg uitsluiting. Ook andere verzamelingen zijn op deze manier te definiëren. We geven nog een voorbeeld. Laat E de verzameling van alle even getallen in zijn, dus E = {0, 2, 4, ...}. Om het gebruik van ‘...’ te vermijden, geven we de volgende inductieve definitie van E: i 0 E ii als x E, dan x + 2 E iii E bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen.

«

OPGAVE 11.1

a Geef vijf verschillende elementen van de verzameling D die inductief gedefinieerd wordt door: i 3 D ii als x D, dan 2x D iii D bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen. b Geef een inductieve definitie van de verzameling O van oneven getallen in . c Geef een inductieve definitie van T = {1, 2, 4, 8, ...}. Tot nu toe bestond de basis steeds uit één element. In het algemeen kan de basis bij een inductieve definitie uit meer elementen bestaan. VOORBEELD Basis Inductiestap Uitsluiting

Een inductieve definitie van V = {0, 1, 4, 5, 8, 9, ...} is als volgt. i 0 V en 1 V ii als x V, dan x + 4 V iii V bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen.

«

OPGAVE 11.2 (Aanw)

Geef een inductieve definitie van V = {1, 2, 3, 4, 6, 8, 12, 16, ...}. Het is ook mogelijk dat de inductiestap meer dan één regel bevat om uit oude elementen nieuwe te maken. Ieder van de regels uit de inductiestap mag dan toegepast worden op alle, tot dan toe in de verzameling aanwezige, elementen. VOORBEELD Basis Inductiestap Uitsluiting

Een inductieve definitie van W = {0, 1, 2, 4, 5, 6, 8, 9, 10, ...} is als volgt. i 0 W en 1 W ii als x W, dan x + 4 W als x W, dan 2x W iii W bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen. «

Geen algemene methode

In dit laatste voorbeeld zien we welk voordeel de inductieve definitie heeft: de regelmaat in de opbouw van de verzameling is onmiddellijk duidelijk uit de regel(s) in de inductiestap. Zoals u wellicht merkt, is het vinden van een inductieve definitie niet altijd even eenvoudig. Er zijn geen algemene methoden om een inductieve definitie uit de gegevens af te leiden, en vandaar ook dat ze populair zijn als ‘intelligentietest’: het blijft altijd weer puzzelen. Een nog groter probleem, waar we niet op in zullen gaan, is de vraag of er voor een gegeven verzameling wel een inductieve definitie bestaat.

OPGAVE 11.3 (Aanw)

a Laat zien dat voor W uit voorgaand voorbeeld ook een inductieve definitie mogelijk is met slechts één regel in de inductiestap. b Geef een inductieve definitie van de verzameling . c Geef een inductieve definitie van V = {0, 1, –3, 4, –4, 5, –7, 8, –8, ...}. Inductieve definitie

Samengevat bestaat een inductieve definitie uit de volgende drie onderdelen. Stap i

Basis Er worden expliciet één of meer elementen aangegeven die tot de verzameling behoren. Dit zijn de zogenaamde basiselementen van waaruit de overige elementen van de verzameling bereikt kunnen worden via de regels in stap ii.

Inductiestap

Stap ii

Er worden één of meer regels beschreven waarmee uit oude elementen nieuwe elementen verkregen kunnen worden. Beginnend met de basiselementen uit stap i, kunnen we met behulp van deze regels steeds weer nieuwe elementen van de verzameling voortbrengen.

Uitsluiting

Stap iii

Er wordt uitdrukkelijk vermeld dat de verzameling geen andere elementen bevat dan welke op grond van basis en inductiestap verkregen kunnen worden. Voor de eenvoud hebben we ons in de voorbeelden en de opgaven beperkt tot getalverzamelingen. Inductieve definities zijn echter op veel meer verzamelingen toe te passen. Veel voorbeelden zijn te vinden in de theorie van formele talen, waar met allerlei verzamelingen van rijtjes symbolen wordt gewerkt.

VOORBEELD

Basis Inductiestap Uitsluiting

Laat L de verzameling zijn die bestaat uit alle rijtjes symbolen ofwel ‘strings’ van de vorm (ab)nb. Hierbij bedoelen we met (ab)n de string abab...ab (n maal ab voor zekere n  ). Dan is L een taal over het alfabet {a, b} die bijvoorbeeld de strings b, abb en ababb. Een inductieve definitie van L is als volgt. i b L ii als x L, dan abx L iii L bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen. In de inductiestap bedoelen we met abx de string die ontstaat door de string ab en de string x L achter elkaar te zetten. «

OPGAVE 11.4

Geef een inductieve definitie van de verzameling L van strings die bestaan uit een aantal a’s gevolgd door evenveel b’s (L is dus een taal over het alfabet {a, b}).

Basis Inductiestap Uitsluiting

Ook rekenkundige expressies als 1 + 2 en 13/(2 – 4) zijn op te vatten als rijtjes symbolen en dus als een (formele) taal. Met behulp van een inductieve definitie kunnen we nu precies vastleggen wat we onder een rekenkundige expressie zullen verstaan. Geven we voor het gemak de beoogde verzameling van alle rekenkundige expressies met R aan, dan is R inductief te definiëren door: i ieder element uit + behoort tot R ii als x R, dan (–x) R als x R en y R, dan (x + y) R, (x – y) R, (x · y) R, (x/y) R iii R bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen. In deze definitie is het getal 0 maar even buiten beschouwing gelaten, om problemen bij het delen te voorkomen. Verder zijn de haakjes ‘(‘ en ‘)’ toegevoegd omdat het anders onduidelijk is wat we bijvoorbeeld met 13/2 – 4 bedoelen: (13/2) – 4 of 13/(2 – 4). Er treden dan wel weer overbodige haakjes op omdat we bijvoorbeeld (1 + 2) en (13/(2 – 4)) moeten schrijven in plaats van 1 + 2 en 13/(2 – 4). Achteraf zijn hier natuurlijk weer aparte afspraken over te maken, maar daar gaat het ons hier niet om.

OPGAVE 11.5

Welke van de volgende uitdrukkingen behoren tot de verzameling R van rekenkundige expressies? Als deze tot R behoort, geef dan aan welke regels uit de inductiestap (en in welke volgorde) u gebruikt om de uitdrukking uit de basis af te leiden. Als deze niet tot R behoort, wat ontbreekt er dan aan? a ((4 – 2)/3) b –(2 · 3) c (–1 + (2/113)) d ((2/113) – 1) e (–(3 · ((4 + 2)/87))) In leereenheid 1 is de verzameling propositielogische formules gedefinieerd. In die definitie legden we vast wat atomaire formules zijn, en we spraken af hoe we nieuwe formules uit al geconstrueerde formules kunnen maken. In feite gaven we daar dus al een inductieve definitie. We zetten de onderdelen van die definitie hier nog eens netjes onder elkaar: De formules van de propositielogica worden als volgt gedefinieerd: Basis Inductiestap

Uitsluiting

i Elke propositieletter (p, q, r, ...) is een formule. ii Als  een formule is, dan is ¬ ook een formule. – Als  en  formules zijn, dan zijn (  ), (  ), (  ) en (  ) ook formules. iii Er zijn geen andere formules.

VOORBEELD 11.1

Tot slot van deze paragraaf een voorbeeld uit het boek ‘Gödel, Escher, Bach’ van D.R. Hofstadter. Daarin wordt niet een verzameling gegeven en vervolgens de inductieve definitie gezocht, maar wordt juist de inductieve definitie gegeven en vervolgens de vraag gesteld of bepaalde elementen tot de verzameling behoren.

Let op!

Laat L de verzameling van alle strings zijn die inductief gedefinieerd wordt door (in de inductiestap mogen x en y ook ‘leeg’ zijn, dus ook bestaan uit geen enkel symbool): i MI L ii als xI L, dan xIU L als Mx L, dan Mxx L als xIIIy L, dan xUy L als xUUy L, dan xy L iii L bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen. Een paar voorbeelden van strings die tot L behoren zijn MIU, MII, MIUIU, MIIII, MUI (zie opgave 11.6). (De verzameling L is een taal over het alfabet {M, I, U}.)

Basis Inductiestap

Uitsluiting

«

In Hofstadter’s boek is de centrale vraag over L: behoort de string MU tot L? In opgave 11.6d wordt gevraagd wat aan dit probleem te puzzelen. Dit ‘MU-probleem’ keert steeds weer terug in het boek en wordt heel fraai gebruikt om er enkele fundamentele ideeën uit de ‘kunstmatige intelligentie’ (waarin zowel wiskunde als informatica een grote rol spelen) mee te illustreren. Het zou te ver voeren hier dieper op die ideeën in te gaan. We verwijzen daarvoor naar het eerder genoemde boek. We hebben inmiddels een aardige indruk gekregen van de mogelijkheden van inductieve definities. Zonder dit verder met meer voorbeelden toe te lichten, merken we nog op dat inductieve definities veelvuldig gebruikt worden zodra ‘discrete structuren’ een rol spelen: getaltheorie en grafentheorie , combinatoriek en kansrekening, logica, formele talen, datastructuren en dergelijke. Hetzelfde geldt voor het begrip recursie, dat onlosmakelijk verbonden is met inductie en in de volgende paragraaf aan de orde komt.

OPGAVE 11.6 (Aanw)

a Geef aan welke regels uit de inductiestap (en in welke volgorde) u gebruikt om de genoemde strings uit voorbeeld 11.1 te verkrijgen uit de basis MI. b Zijn strings uit L op precies één manier via de regels in de inductiestap uit de basis te verkrijgen, of kan er meer dan één manier zijn? Motiveer uw antwoord. c Beredeneer dat alle strings uit L beginnen met een M. d Puzzel eens wat aan de vraag of MU tot L behoort. (De oplossing is niet zo eenvoudig en komt pas in Discrete wiskunde B aan de orde.) OPGAVE 11.7 (Aanw)

a Geef een inductieve definitie van A = {2, 3, 5, 9, 17, ...}. b Idem als in onderdeel a voor D = {..., 1/27, 1/9, 1/3, 1, 3, 9, 27, ...}. OPGAVE 11.8 (Aanw)

Zij a  en r  . Geef een inductieve definitie van de volgende verzamelingen. a M = {a, ar, ar2, ar3, ...} b N = {a, a + ar, a + ar + ar2, a + ar + ar2 + ar3, ...}

OPGAVE 11.9

In deze opgave werken we met een zekere programmeertaal waarin de gebruiker zelf ‘variabelen’ kan introduceren. Die variabelen moeten van de volgende vorm zijn: ze beginnen met een letter uit het Nederlandse alfabet N, terwijl daarna naast letters uit N ook cijfers uit C = {0, 1, 2, ..., 8, 9} en de tekens @, #, $ en % mogen voorkomen. Geef een inductieve definitie van dit begrip ‘variabele’ en pas uw definitie toe om een paar voorbeelden van variabelen te produceren. 11.2

Recursie

11.2.1

RECURSIEVE DEFINITIES

Omdat functies en rijen gedefinieerd zijn in termen van verzamelingen (zie leereenheid 8, kunnen inductieve definities ook gebruikt worden om er zekere functies en rijen mee te definiëren. We illustreren dit aan de hand van de volgende inductief gedefinieerde verzameling V: V als verzameling

i (0, 1) V ii als (n, m) V, dan (n + 1, m(n + 1)) V iii V bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen. Enkele elementen van V zijn (0, 1), (1, 1), (2, 2) en (3, 6) (ga dit na). Met V is iets bijzonders aan de hand omdat V ook te zien is als een functie. Daartoe kijken we eerst naar de eerste coördinaat n van de paren (n, m) in V. Precies vanwege de inductieve definitie van zal die eerste coördinaat de verzameling doorlopen. Als we nu aan de eerste coördinaat n van (n, m) de tweede coördinaat m toevoegen, die hier eveneens tot behoort, dan wordt hiermee inderdaad een functie van naar gedefinieerd: aan iedere n  wordt één element m  toegevoegd. Met nadruk wijzen we nogmaals op het feit dat we de inductieve definitie van gebruikten om te concluderen dat het domein van f is.

Laten we nu, zoals gebruikelijk is voor functies, m = f(n) schrijven in plaats van (n, m) V. Regel i is dan te schrijven als f(0) = 1. Verder volgt uit f(n) = m en f(n + 1) = m(n + 1) dat regel ii herschreven kan worden als f(n + 1) = (n + 1)f(n). De inductieve definitie van V komt er dus op neer dat er een functie f:  is gedefinieerd door: V als functie f

i f(0) = 1 ii f(n + 1) = (n + 1)f(n) voor n  .

Geen uitsluiting

Bij deze definitie van f is de uitsluitingsregel niet nodig. Uit de definitie van ‘functie’ volgt namelijk dat f uitsluitend aan de elementen in het domein ( in ons voorbeeld) één waarde f(n) toekent; andere elementen mogen dan niet meer voorkomen en zijn dus al uitgesloten. Al met al is de definitie van f eenvoudiger dan de equivalente definitie van V. Omdat f als domein heeft, wordt hiermee ook een rij gedefinieerd, namelijk de rij a0, a1, a2, a3, ... waarbij an = f(n). In termen van deze rij geldt er:

V als rij an

a0 = 1 (regel i) en an+1 = (n + 1)an voor n 

(regel ii)

Hoe bepalen we nu met deze definitie bijvoorbeeld f(3)? Allereerst passen we regel ii toe met n = 2. We zien dan dat f(3) is uit te drukken in termen van f(2), namelijk f(3) = 3f(2). Passen we opnieuw regel ii toe, maar nu met n = 1, dan volgt dat f(2) is uit te drukken in termen van f(1), namelijk f(2) = 2f(1). Maar nu is f(1) weer uit te drukken in termen van f(0), namelijk f(1) = 1f(0) (weer regel ii, maar nu met n = 0). Omdat in regel i is gegeven dat f(0) = 1, is hiermee f(3) bepaald: f(3) = 3f(2) = 3 · 2f(1) = 3 · 2 · 1 · f(0) = 3 · 2 · 1 = 6 Nu f(3) berekend is, volgt f(4) door één maal regel ii toe te passen: f(4) = 4f(3), dus f(4) = 4 · 6 = 24. Zo doorgaand kan voor iedere n  de functiewaarde f(n) (of de term an = f(n) uit de bijbehorende rij) berekend worden. OPGAVE 11.10

Laat f de hierboven gedefinieerde functie zijn. a Bereken de functiewaarden f(5) en f(6). b Geef de eerste 7 termen van de rij die bij f hoort. Als we in regel ii overal n door n – 1 vervangen (en opmerken dat n – 1  hetzelfde is als n  +), dan volgt dat regel ii ook geschreven kan worden als ii' f(n) = nf(n – 1) voor n 

+

wat iets gebruikelijker is. Het opmerkelijke aan deze definitie van f is dat we in regel ii' (of in regel ii) de functie niet geven door een functievoorschrift (een ‘formule’), maar door een uitdrukking waar de functie zelf opnieuw in voorkomt. Om f(n) uit te rekenen, moeten we via f(n – 1), f(n – 2), ... teruglopen tot we bij f(0) = 1 zijn aangekomen, of bij een waarde die we al eerder uitgerekend hebben.

Recursieve definitie ‘recursief = inductief’

Naast de term inductieve definitie spreken we ook van een recursieve definitie van f. Recurrent betekent ‘terugkerend’ of ‘teruglopend’, en een ‘teruglopend’ effect is duidelijk herkenbaar in de definitie van f. In de literatuur zult u zien dat de termen inductieve dan wel recursieve definitie naast en door elkaar gebruikt worden. We zullen ‘recursief’ vooral gebruiken als duidelijk zichtbaar is dat een functie (of een rij, of een ander wiskundig object) gedefinieerd wordt in termen van zichzelf. Het ‘in zichzelf terugkeren’ staat ook bekend als het Droste-effect, naar de bekende illustratie op de verpakking van Droste-cacao. Het recursieve karakter ontstaat hier doordat de verpakking zelf als deel van de figuur optreedt. Ook in het werk van de grafische kunstenaar M.C. Escher (1902-1972) speelt recursie een grote rol en recursie is één van de hoofdthema’s in het eerder genoemde boek ‘Gödel, Escher, Bach’ van Hofstadter.

Bij een recursieve definitie is het gebruikelijk om niet van basis, maar van startwaarde(n) te spreken. In ons voorbeeld is f(0) = 1 de startwaarde. De recursie f(n) = nf(n – 1) wordt door deze startwaarde ‘op gang gebracht’.

Startwaarde(n)

We blijven nog even bij dit voorbeeld stilstaan. Het is namelijk niet moeilijk om in dit geval uit de recursieve definitie een expliciete formule voor f(n) af te leiden, dat wil zeggen een uitdrukking waarmee f(n) te berekenen is, zonder dat daarvoor de recursie doorlopen hoeft te worden. Zo’n expliciete formule volgt hier direct door regel ii' herhaald toe te passen. Uit regel ii' krijgen we allereerst dat f(n) = nf(n – 1). Maar nu kunnen we op f(n – 1) opnieuw regel ii' (met n vervangen door n – 1) toepassen en krijgen we dat f(n – 1) = (n – 1) f(n – 2). Op f(n – 2) is weer regel ii' toe te passen (met n vervangen door n – 2) en volgt dat f(n – 2) = (n – 2)f(n – 3). Dit is net zolang voort te zetten tot we bij f(1) = 1f(0) zijn aangekomen. Als we al deze stappen achter elkaar zetten, dan volgt er dat f(n) = nf(n – 1) = n(n – 1)f(n – 2) = ... = n(n – 1)(n – 2) · ... · 3 · 2 · 1 · f(0), en omdat f(0) = 1, is hiermee de formule voor f(n) gevonden:

Expliciete formule

Expliciete formule voor f

Faculteit

f(n) = n(n – 1)(n – 2) · ... · 3 · 2 · 1 Deze uitdrukking heeft de aparte notatie n! gekregen en wordt uitgesproken als n faculteit. Met de notatie n! voor f(n) is de recursieve definitie uit regel i (f(0) = 1) en regel ii' (f(n) = nf(n – 1)) ook als volgt kort op te schrijven: 0! = 1 en n! = n(n – 1)! voor n  +. In programmeertalen kan de recursieve definitie van n! gerealiseerd worden door het herhaald laten doorlopen van een lus. Hieronder illustreren we dit aan de hand van een fictieve ‘programmeertaal’. We geven eerst het programma, daarna volgt een korte toelichting. lees maak zolang

n Fac := 1 k := 1 k ≤ n doe Fac := k * Fac maak k := k + 1

Toelichting op het programma

Lees Fac := 1 als ‘Fac wordt 1’

De opdrachten zijn vetgedrukt. De eerste regel geeft aan dat de computer een getal n inleest dat door de gebruiker wordt opgegeven. We gaan ervan uit dat een getal n  wordt opgegeven. In de tweede regel wordt aan de variabele ‘Fac’ de waarde 1 toegekend, wat symbolisch is weergegeven met Fac := 1. In de derde regel wordt aan k de waarde 1 toegekend. De vierde tot en met zesde regel vormen de lus: als aan de voorwaarde k ≤ n is voldaan, dan wordt Fac met de waarde van k vermenigvuldigd (en als nieuwe waarde aan Fac toegekend), de waarde van k wordt met 1 verhoogd, de voorwaarde k ≤ n wordt opnieuw getest, enzovoort. Het programma stopt als k is verhoogd tot n + 1. De variabele ‘Fac’ heeft dan de waarde n! (ga dit na!). De recursieve definitie van n! kan in een programmeertaal ook zonder expliciete lus gerealiseerd worden: recursieveFaculteit (n) { ..if (n == 0) return 1; ..else return n * recursieveFaculteit (n – 1) }

OPGAVE 11.11 (Aanw)

Laat g:  de functie zijn die recursief gedefinieerd wordt door g(0) = 3 en g(n) = 3g(n – 1) voor n ≥ 1. a Bereken de functiewaarden g(1), g(2) en g(3). b Geef de eerste 5 termen van de rij behorend bij g. c Schrijf een programma in voorgaande fictieve ‘programmeertaal’ dat de functiewaarde g(n) bepaalt voor een gegeven waarde van n. d Bepaal een expliciete formule voor g(n). OPGAVE 11.12 (Aanw)

Bekijk de rij driehoeksgetallen a0 = 1, a1 = 3, a2 = 6, a3 = 10, ... uit de introductie. Schrijf de rij in termen van een functie f en probeer een recursieve definitie voor f te vinden (lees eventueel de introductie er nog eens op na). Recursieve definities worden op zeer uiteenlopende terreinen gebruikt voor het genereren van nieuwe dingen uit oude. We gebruiken met opzet het woord ‘dingen’, omdat recursieve definities niet alleen gebruikt worden voor verzamelingen, functies of rijen, maar bijvoorbeeld ook om nieuwe notaties of begrippen in te voeren. Een voorbeeld hebben we al gezien: de notatie n! is gedefinieerd door 0! = 1 en n! = n(n – 1)! voor n  +. Een ander bekend voorbeeld is de notatie voor de som van een aantal termen, zeg a0, a1, a2 t/m an, die meestal geïntroduceerd wordt met de volgende definitie: n

 ai  a0  a1  a2  ...  an

i0

Somteken

(11.1)

Het symbool  is de Griekse hoofdletter s en is als somteken gekozen omdat het de eerste letter van ‘som’ is (ook in het Engels en Duits).

De ai kunnen getallen zijn, zoals in 4

 i  0  1  2  3  4  10

i0

maar ook symbolen, zoals in 3

 xi  1  x  x 2  x 3

i0

Sommatieindex

De letter i heet de sommatieindex of sommatievariabele en doorloopt alle waarden vanaf de ondergrens, die onder het somteken staat, tot en met de bovengrens, die boven het somteken staat. Het is een ‘lokale’ variabele, waarvoor we ook een andere letter mogen kiezen:

Recursieve definitie van som

 i 2  0  1 4  9  ... (n  1) 2  n 2   k 2

n

n

i0

k 0

Een recursieve definitie van de somnotatie, waarmee het gebruik van ‘...’ in formule 11.1 vermeden wordt, is als volgt: 0

 ai  a0

i0

en

n

n 1

i 0

i0

 ai  an   ai

voor n 

+

In het algemeen hoeft een som niet met i = 0 te beginnen. Een recursieve definitie van de som van as, as+1, as+2 t/m an (met n, s  en n ≥ s) is: s

 ai  as

is

en

n

n 1

i s

is

 ai  an   ai

voor n  s  1

OPGAVE 11.13

5 6 3 2 i2 Bepaal  i 0 i!,  k  3 2k ,  i 2 1/( 2i  1) en  i (dit is een oefening in de 2 somnotatie; u hoeft niet per se de recursieve definitie te gebruiken).

Het product van a0, a1, a2 t/m an wordt als volgt genoteerd: n

 ai  a0  a1  a2  ... an

i0

Het symbool  is de Griekse hoofdletter p en is als productteken gekozen omdat het de eerste letter van ‘product’ is. In opgave 11.14 wordt naar een recursieve definitie van de productnotatie gevraagd.

Productteken

OPGAVE 11.14

a Bepaal 4i 0 (i  1)2 , 3i 0 xi en ni 0 (i  1) . b Geef een recursieve definitie van de productnotatie en laat zien dat de recursieve definitie van n! hier een bijzonder geval van is. c Geef een recursieve definitie van de productnotatie als we niet per se met a0 beginnen, maar met as (s  ). 2 7 i d Bepaal  3i  1 1/( i 2  1),  20 k 5 k en  i  7 x voor x  met x ≠ 0 (deze opgaven hoeft u niet per se met behulp van de recursieve definitie op te lossen).

In de theorie van de formele talen worden recursieve definities onder meer gebruikt om talen mee te genereren. We illustreren dit principe met , wat we nu niet zozeer als de verzameling van gehele getallen zien, maar als verzameling van eindige rijtjes symbolen, ofwel als ‘taal’. Met behulp van een aantal eenvoudige regels is precies te beschrijven welke rijtjes symbolen tot behoren. De eerste observatie is dat die rijtjes al dan niet met een + of – teken beginnen , waarna een natuurlijk getal volgt. We geven dit als volgt weer: ::=  Met deze notatie wordt bedoeld dat er voor het nieuw te definiëren object , dat links van het teken ::= staat, twee alternatieven zijn: het is van de vorm of van de vorm . Deze toegestane alternatieven worden gescheiden door een verticale streep. Het lijkt alsof we hiermee niets zijn opgeschoten, want nu zitten we met twee nieuwe objecten, namelijk en . Met zijn we snel klaar: ::= +  – Dit betekent dat vervangen mag worden door + of –. Nu pakken we aan. Omdat een natuurlijk getal een rijtje is van één of meer cijfers 0 t/m 9, is als volgt recursief te definiëren: ::=  waarbij ::= 0  1 2  3  4  5  6  7  8  9 Het recursieve in deze definitie is duidelijk: mag vervangen worden door , wat opnieuw bevat, enzovoort. Het proces van vervanging stopt pas als we besluiten te vervangen door . Samengevat is de recursieve definitie van de ‘taal’ als volgt: Recursieve definitie van de gehele getallen

::=  ::=  ::= 0  1 2  3  4  5  6  7  8  9 ::= +  – Laten we eens kijken hoe bijvoorbeeld –3157 met deze definitie recursief wordt opgebouwd. We starten met , wat we vervangen door . Dit noteren we kort als:  Nu vervangen we door – en door :  –

Hierin vervangen we steeds door het volgende benodigde getal en door , tot we het einde zien naderen en we door vervangen: –  –3  –31  –315  –3157

Backus-Naur form

BNF

Deze vorm van recursieve definitie wordt veel gebruikt om de toegestane uitdrukkingen (de ‘syntax’) in programmeertalen mee vast te leggen en wordt de Backus-Naur form (afgekort tot BNF) genoemd. Voor meer details verwijzen we naar de literatuur over formele talen.

OPGAVE 11.15

Laat zien hoe het getal 2561 verkregen kan worden met behulp van voorgaande recursieve definitie van . Doe hetzelfde voor +2561. Net als bij de inductieve definities van verzamelingen vormen de voorbeelden in deze paragraaf slechts het topje van de ijsberg: recursieve definities komen in ‘alle vormen en maten’ voor. In de paragrafen 11.2.2 en 11.2.3 behandelen we twee recursies die veelvuldig optreden. OPGAVE 11.16 (Aanw)

De rij a0, a1, a2, a3, ... wordt recursief gedefinieerd door a0 = 1 en an = (2n – 1)an–1 voor n  +. a Bepaal de eerste 6 termen van de rij. b Formuleer de definitie van de rij in termen van een functie. c Schrijf een programma in onze fictieve ‘programmeertaal’ dat an bepaalt voor een gegeven waarde van n. d Bepaal een expliciete formule voor an. OPGAVE 11.17

n Laat Ai een verzameling zijn voor iedere i  . Met i  0 A i bedoelen we de verzameling A0  A1  ...  An (zie ook paragraaf 5.2.2). Geef een n recursieve definitie van i  0 A i die het gebruik van ‘...’ vermijdt. Doe hetzelfde voor A0  A1  ...  An.

OPGAVE 11.18 (Aanw)

In opgave 11.9 werd een inductieve definitie gegeven van het begrip ‘variabele’ in een zekere (fictieve) programmeertaal. Geef hiervan opnieuw een definitie, maar nu in Backus-Naur form. Geef vervolgens aan hoe met die definitie de variabele z%%u8 wordt verkregen. 11.2.2

REKENKUNDIGE RIJEN EN EINDIGE REKENKUNDIGE REEKSEN

Beschouw de rij a0 = 0, a1 = 1, a2 = 2, a3 = 3, ... Deze rij ontstaat door de elementen van in hun natuurlijke volgorde achter elkaar te zetten. De regelmaat in de rij is dan ook niets anders dan de regelmaat in , namelijk steeds er 1 bij optellen. Hieruit halen we meteen de recursieve definitie: a0 = 0 en an = an–1 + 1 voor n ≥ 1. Deze rij is het eenvoudigste voorbeeld van een zogenaamde rekenkundige rij. In plaats van bij 0 kunnen we zo’n rij ook bij ieder ander getal laten beginnen, zeg bij a  .

Ook kan men er in plaats van de vaste waarde 1 iedere andere vaste waarde bij optellen, zeg v  . Zo ontstaat de algemene rekenkundige rij: Rekenkundige rij

a0 = a

Eerste term a Verschil v

Het getal a heet de eerste term. Omdat voor ieder tweetal opeenvolgende termen an–1 en an geldt dat an – an–1 = v, noemen we v het verschil. Hieruit volgt ook direct de recursieve definitie van de rekenkundige rij: a0 = a en an = an–1 + v voor n  +.

a1 = a + v

a2 = a + 2v

a3 = a + 3v

...

OPGAVE 11.19

a Geef de eerste 6 termen van de rekenkundige rij met eerste term 3 en verschil 7. Geef ook de 100-ste term. b Bepaal een expliciete formule voor de (n + 1)-ste term an uit een rekenkundige rij met eerste term a en verschil v. c Bepaal de 237-ste term uit de rekenkundige rij 4, 10, 16, 22, ...

Driehoeksgetallen

De driehoek voor 10, ofwel tetraktys

Eindige rekenkundige reeks

Wordt een rekenkundige rij na een eindig aantal termen afgebroken, dan spreken we van een eindige rekenkundige rij. In telproblemen komt nogal eens de som van de termen uit een eindige rekenkundige rij voor. Als voorbeeld nemen we de driehoeksgetallen 1, 3, 6, 10, ... uit de introductie. Dit zijn precies de getallen 1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4, ..., ofwel steeds de som van de termen uit een eindige rekenkundige rij. Het aantal blikjes dat nodig is om een driehoekige stapel te maken met n lagen, wordt gegeven door het n-de driehoeksgetal 1 + 2 + 3 + ... + n. De driehoek voor het getal 10 is hiernaast weergegeven. De Griekse Pythagoreeërs noemden de driehoek voor 10 de tetraktys (deze was om allerlei redenen heilig en ze legden er een eed op af). In het algemeen noemen we de som van de termen uit een eindige rekenkundige rij een eindige rekenkundige reeks: a + (a + v) + (a + 2v) + ... + (a + nv)

rij ≠ reeks

VOORBEELD 11.2

voor zekere n 

en a, v 

Ook hier spreken we weer van eerste term a en verschil v. De driehoeksgetallen ontstaan als we a = 0 en v = 1 nemen. Let goed op het onderscheid tussen een eindige rekenkundige rij en de bijbehorende eindige reeks: in de reeks worden de getallen uit de rij bij elkaar opgeteld. De naamgeving suggereert dat er ook niet-eindige (ofwel oneindige) reeksen bestaan. Dit is inderdaad het geval, maar oneindige reeksen komen in deze cursus niet aan bod omdat daarvoor het begrip ‘limiet’ nodig is, wat het centrale idee in de ‘continue’ wiskunde is. Voor een eindige rekenkundige reeks leiden we nu een expliciete formule af. We beginnen met een voorbeeld. Over Gauss, één van de bekendste wiskundigen, wordt een anekdote verteld waarin de jonge Gauss van zijn meester de opdracht krijgt om 1 + 2 + 3 + ... + 98 + 99 + 100 te berekenen (het 100-ste driehoeksgetal).

Tot verbazing van de meester komt Gauss direct met het juiste antwoord. C. F. Gauss (17771855), Duits wiskundige

Hij had het volgende opgemerkt. Schrijf de som twee maal op, de tweede keer in omgekeerde volgorde, en tel deze bij elkaar op: 1 + 100 +

2 + 99 +

3 + 98 +

... + ... +

98 + 3 +

99 + 100 2 + 1 +

101 + 101 + 101 +

... + 101 + 101 + 101

In de laatste regel staat 100 keer 101. Twee maal de gevraagde som is dus 100 · 101, zodat de gevraagde som gelijk is aan 50 · 101 = 5050. « OPGAVE 11.20

Bepaal de som van de getallen 1 tot en met 999.

De methode generaliseert!

Het mooie van de methode uit voorbeeld 11.2 is, dat deze ook toe te passen is om het n-de driehoeksgetal sn = 1 + 2 + 3 + ... + (n – 1) + n uit te rekenen, waarbij n  willekeurig is. Wiskundigen zeggen dan dat de methode of het bewijs generaliseert. Schrijf sn tweemaal op, de tweede keer in omgekeerde volgorde, en tel op: sn sn

= =

1 + 2 + 3 + ... + (n – 2) + (n – 1) + n + (n – 1) + (n – 2) + ... + 3 + 2 +

n 1 +

2sn = (n + 1) + (n + 1) + (n + 1) + ... + (n + 1) + (n + 1) + (n + 1) In de laatste regel staat n keer het getal n + 1, dus 2sn = n(n + 1), ofwel Formule voor sn

n

 i  1  2  3  ...  n  12 n( n  1)

i 0

(11.2)

De ondergrens i = 0 in de sommatie kan natuurlijk vervangen worden door i = 1, maar voor het vervolg is het wat handiger om hier met i = 0 te beginnen.

Op dezelfde manier als hiervoor is de volgende formule af te leiden voor de som van de termen van de eindige rekenkundige rij met eerste term a en verschil v: Formule voor een eindige rekenkundige reeks

n

 (a  iv )  a  (a  v )  (a  2v )  ...  (a  nv )  12 (2a  nv )(n  1)

(11.3)

i0

Uit het hoofd leren of niet?

Ga dit na.

Nemen we a = 0 en v = 1 in formule 11.3, dan vinden we formule 11.2 terug. Het staat u vrij om formule 11.3 uit het hoofd te leren; hierbij is het vooral van belang het aantal termen n goed te bepalen, omdat dit vaak een bron van vergissingen is! Het is echter beter om te onthouden hoe de formule afgeleid wordt. De ervaring leert dat een goed begrepen methode waardevoller is en minder snel vergeten wordt dan een (wellicht onbegrepen) formule. Als u de formule voor de som van een rekenkundige reeks wilt onthouden, dan is de makkelijkste manier waarschijnlijk deze: Tel de eerste en de laatste term bij elkaar op en vermenigvuldig dit met de helft van het aantal termen.

OPGAVE 11.21

Zij sn = a + (a + v) + (a + 2v) + ... + (a + nv) voor zekere a, v  . a Gebruik de methode uit voorbeeld 11.2 om formule 11.3 voor sn te bewijzen. b Formule 11.3 is ook eenvoudig af te leiden uit formule 11.2. Laat zien hoe dat gaat. c Bepaal 5 + 9 + 13 + ... + 113 en 7 + 4 + 1 – 2 – ... – 44. d Geef een recursieve definitie van sn. 11.2.3

MEETKUNDIGE RIJEN EN EINDIGE MEETKUNDIGE REEKSEN

De rekenkundige rij ontstaat door steeds eenzelfde vaste waarde op te tellen bij een gegeven getal. Verwant hiermee is de rij die ontstaat door steeds met eenzelfde vaste waarde te vermenigvuldigen. Zulke rijen treden bijvoorbeeld op als we geld op een spaarrekening zetten. VOORBEELD 11.3

Stel dat we (éénmalig) € 100,– op een spaarrekening storten met een vaste rente van 4 % per jaar. Na een jaar zal er € 104,– op de rekening staan, immers 100 + 0,04 · 100 = 1,04 · 100 = 104. Weer een jaar later is dit getal 1,04 · 104 = 108,16, wat te schrijven is als (1,04)2 · 100. Nog weer een jaar later wordt dit 1,04 · 108,16 = 112,4864 (de bank rondt dit af tot 112,49), wat te schrijven is als (1,04) 3 · 100. Enzovoort voor latere jaren. Zo ontstaat de rij 100, 104, 108,64, 112,4864, ..., waarbij ieder volgend getal uit het vorige ontstaat door met 1,04 te vermenigvuldigen. Dit is goed zichtbaar als we de rij schrijven als: 100, 1,04 · 100, (1,04)2 · 100, (1,04)3 · 100, ... «

OPGAVE 11.22

We zetten € 500,– op een spaarrekening met een vaste rente van 3 % per jaar. Geef de bedragen die in de komende 4 jaar op de rekening zullen staan (rond de bedragen niet af). Schrijf deze bedragen ook in de vorm die in de laatste regel in voorbeeld 11.3 werd gegeven.

Rijen als in voorbeeld 11.3 worden meetkundige rijen genoemd en treden overal op waar er groei is volgens een vast percentage. Uitgaande van een bepaalde startwaarde a wordt het volgende getal steeds verkregen uit het vorige door met een vast getal r te vermenigvuldigen. Een meetkundige rij ziet er dus altijd zo uit: Meetkundige rij

a0 = a

Eerste term a

Het getal a heet de eerste term. Voor ieder tweetal opeenvolgende termen an–1 en an geldt dat an/an–1 = r. U verwacht nu misschien dat we r het quotiënt zullen noemen. Het is echter gebruikelijk om r de reden van de meetkundige rij te noemen. (Denk bij ‘reden’ aan ‘ratio’: de verhouding tussen an en an–1 is r.) De recursieve definitie van de meetkundige rij is als volgt: a0 = a en an = ran–1 voor n ≥ 1.

Reden r

a1 = a · r

a2 = a · r2

a3 = a · r3

...

OPGAVE 11.23

a Geef de eerste 6 termen van de meetkundige rij met eerste term 3 en reden 4. Doe hetzelfde als de eerste term √2 en de reden 1/2 is. b Bepaal een expliciete formule voor de (n + 1)-ste term an uit een meetkundige rij met eerste term a en reden r. c Bepaal de 11-de term uit de meetkundige rij 4, 12, 36, 108, ... Wordt een meetkundige rij na een eindig aantal termen afgebroken, dan spreekt men van een eindige meetkundige rij. De som van de termen van een eindige meetkundige rij wordt eindige meetkundige reeks genoemd en is dus van de volgende vorm Eindige meetkundige reeks

a + ar + ar2 + ar3 + ... + arn

voor zekere n 

en a, r 

Ook hier spreken we weer van eerste term a en reden r. Deze eindige reeksen treden in allerlei situaties op. Het volgende voorbeeld komt weer uit de wereld van de financiën. VOORBEELD 11.4

Stel dat we meedoen aan een spaarplan waarbij we ieder jaar € 1000,– storten (denk bijvoorbeeld aan pensioenopbouw). In het spaarplan wordt van de verwachting uitgegaan dat er een ‘rendement’ van 10 % per jaar wordt gehaald. Met deze verwachting zal het bedrag na een jaar zijn toegenomen tot 1,1 · 1000 = 1100 (zie ook voorbeeld 11.3). Omdat ook € 1000,– wordt bijgestort, is na een jaar het kapitaal in het spaarplan 1000 + 1,1 · 1000 = 2100. Weer een jaar later is dit 1000 + 1,1 · 2100 = 3310. Omdat 2100 = 1000 + 1,1 · 1000, geldt er dat 3310 = 1000 + 1,1 · (1000 + 1,1 · 1000) = 1000 + 1,1 · 1000 + (1,1) 2 · 1000 Nog weer een jaar later wordt dit 1000 + 1,1 · 3310 = 4641. Wordt voorgaande uitdruking voor 3310 ingevuld, dan is 4641 te schrijven als 4641 = 1000 + 1,1 · 1000 + (1,1) 2 · 1000 + (1,1)3 · 1000 Enzovoort voor latere jaren. Er ontstaat zo steeds een eindige meetkundige reeks met reden 1,1 en eerste term 1000.

OPGAVE 11.24

a Hoe groot schat u dat het kapitaal in voorbeeld 11.4 is na 25 jaar (aangenomen dat het verwachte rendement gerealiseerd wordt)?

«

b We zetten € 500,– in een spaarplan met een vast rendement van 5 % per jaar. Geef voor 4 achtereenvolgende jaren het kapitaal dat in dit spaarplan zal zijn ontstaan (rond de bedragen niet af). Schrijf de bedragen ook in de vorm van eindige meetkundige reeksen als in voorbeeld 11.4 en geef de eerste term en de reden van deze reeksen. c Geef de meetkundige reeks behorend bij de eerste 6 termen van de twee rijen uit opgave 11.23a. Als we in voorbeeld 11.4 het eindkapitaal na 25 jaar willen weten, dan zou het handig zijn als we daar een formule voor konden gebruiken. Zo’n formule voor een eindige meetkundige reeks is inderdaad af te leiden. Zij a, r  en noem de gevraagde som sn, dus sn = a + ar + ar2 + ar3 + ... + arn. Er wordt nu de volgende ‘truc’ gebruikt. Vermenigvuldig sn met r en trek sn en rsn van elkaar af: = a + ar + ar2 + ar3 + ... = ar + ar2 + ar3 + ...

sn rsn

+ arn + arn + arn+1 –

sn – rsn = a Eerst r ≠ 1

arn+1

–

Uit de laatste regel volgt dat (1 – r)sn = a(1 – rn+1). Als r ≠ 1, dan kunnen we het linker- en rechterlid door 1 – r delen en volgt er dat

Formule voor een eindige meetkundige reeks

n

 ar i 

i 0

Wat als r = 1?

(11.4)

a(1  r n1 ) 1r

Het geval r = 1 is eenvoudig: we krijgen dan de reeks a + a + ... + a die bestaat uit n + 1 keer de term a en als som (n + 1)a heeft. Over het ‘uit het hoofd leren’ van formule 11.4 geldt dezelfde opmerking als bij formule 11.3, inclusief de waarschuwing over het bepalen van de juiste waarde van n. De makkelijkste manier om de formule te onthouden, is waarschijnlijk deze: Laat r de reden zijn; neem de eerste term en trek daar van af de laatste term vermenigvuldigd met r; deel het resultaat door 1 – r.

Uit het hoofd leren of niet?

Ga dit na.

OPGAVE 11.25 (Aanw)

a Bereken hoe groot het kapitaal in voorbeeld 11.4 is na afloop van het 25-ste jaar (als het verwachte rendement gerealiseerd wordt) en vergelijk het resultaat met uw schatting uit opgave 11.24a. b Bepaal 2 + 4 + 8 + 16 ... + 2048. c

Bepaal 3  1 

1 3



1 9

 ... 

1 . 729



1 4

–

1 8

 ... –

1 . 2048

d Bepaal 1 – e

1 2

Bepaal voor alle n 

met n ≥ 3 de som van

n

 23i . i

i 3

OPGAVE 11.26 (Aanw)

Zij sn = a + ar + ar2 + ar3 + ... + arn voor zekere a, r  . a Geef een recursieve definitie van sn. b Stel dat iemand bewezen had dat s5 = a(1 – r6)/(1 – r). Gebruik de recursie om hiermee aan te tonen dat s6 = a(1 – r7)/(1 – r).

11.2.4

RECURRENTE BETREKKINGEN

Voor de recursief gedefinieerde functie f(n) = n! uit paragraaf 11.2.1 was eenvoudig een expliciete formule af te leiden. Ook voor de recursief gedefinieerde eindige rekenkundige en meetkundige reeks hebben we in de voorgaande twee paragrafen de formules 11.3 respectievelijk 11.4 kunnen afleiden. In het algemeen kan het echter erg moeilijk zijn om uit een gegeven recursieve definitie (voor een functie, rij, ...) een expliciete formule af te leiden. Het bestuderen van problemen die door een recursieve definitie beschreven worden, is dan ook een levendig en uitgebreid vakgebied. In deze paragraaf willen we daar wat aandacht aan besteden aan de hand van een paar voorbeelden. Liber = boek Abacus = telraam

Recursie afleiden uit het probleem.

Stap 1: een paar waarden berekenen.

Het eerste voorbeeld betreft één van de bekendste recursieve definities uit de wiskunde. Het is afkomstig uit het boek ‘Liber Abaci’ over de rekenkunde van de Italiaan Leonardo van Pisa, beter bekend als Leonardo Fibonacci (±1180 tot ±1250). In het boek wordt het volgende probleem beschreven. We hebben een pasgeboren konijnenpaar gekregen. Konijnenparen krijgen na twee maanden hun eerste paar jongen, en daarna iedere maand een nieuw paar jongen. Ieder nieuw paar krijgt eveneens vanaf de tweede maand iedere maand een paar jongen. Hoeveel konijnenparen zijn er nu na een bepaald aantal maanden? Dit probleem proberen we op te lossen door het om te zetten in een recursie. Omdat we starten met één paar, nemen we F0 = 1. Het aantal paren na n maanden noemen we Fn. Een eerste gevoel voor het probleem krijgen we wellicht door wat waarden van Fn te bepalen. Na één maand zijn er nog geen jongen geboren, dus F1 = 1. Na twee maanden is het eerste paar jongen geboren, dus F2 = 1 + 1 = 2. Na drie maanden is er weer één paar bijgekomen, dus F3 = 2 + 1 = 3. Na vier maanden zijn er twee paren die nakomelingen produceren, dus F4 = 3 + 2 = 5.

OPGAVE 11.27

Bepaal het aantal paren F5 en F6. Probeer F5 en F6 uit te drukken in eerder bepaalde getallen Fi. Ziet u al een regelmaat? Stap 2: een gokje wagen. Stap 3: proberen de recursie te bewijzen.

Twee startwaarden

Rij van Fibonacci

Recurrente betrekking Recurrentie Differentievergelijking Iteratie

Uit de gegevens tot nu toe zouden we de regelmaat in de getallen Fn kunnen gokken: het lijkt erop dat Fn = Fn–1 + Fn–2. Kunnen we nu beredeneren dat dit de juiste recursie is? De vraag is: hoeveel paren zijn er na n maanden? In ieder geval de paren die er al in de vorige maand waren, wat er Fn–1 zijn. Er komen ook nieuwe paren bij: de nakomelingen van alle paren die er twee maanden geleden waren. Dat zijn er Fn–2. In totaal zijn dit Fn–1 + Fn–2 paren. Onze gok was goed. We hoeven dus niet terug naar stap 1 en 2: nieuwe waarden uitrekenen en een nieuwe gok wagen! Het konijnenprobleem is hiermee omgezet in een rij getallen F0, F1, F2, ..., die recursief gedefinieerd is door Fn = Fn–1 + Fn–2 voor n  met n ≥ 2 en de twee startwaarden F0 = 1 en F1 = 1. De rij die door deze recursie gedefinieerd wordt, heet de rij van Fibonacci. Er zijn nu twee startwaarden nodig omdat de recursie naast de laatst berekende waarde Fn–1 ook de voorlaatste waarde Fn–2 nodig heeft. Voor een relatie als Fn = Fn–1 + Fn–2 wordt meestal de term recurrente betrekking, recurrentie of differentievergelijking gebruikt. Iedere keer dat de recurrentie gebruikt wordt om een volgende waarde uit te rekenen, noemen we een iteratie. Om F2 uit te rekenen is één iteratie nodig, voor F3 twee iteraties, enzovoort.

OPGAVE 11.28

a Bepaal de eerste 10 termen uit de rij van Fibonacci. b Geef een programma in de fictieve programmeertaal uit paragraaf 11.2.1 dat de eerste n termen van de rij van Fibonacci berekent. Neem aan dat het in de taal mogelijk is om een eindige rij variabelen F(0) t/m F(n) te gebruiken (vaak ‘array’ genoemd) om de getallen in op te slaan. Een recurrentie is nog geen oplossing. Liefst een formule.

Met het afleiden van de recurrentie is het probleem nog niet opgelost. Als we Fn willen weten voor n = 3000, dan moet er heel wat gerekend worden. Een expliciete formule voor Fn zou dat kunnen vereenvoudigen (denk aan de formules voor de eindige rekenkundige en meetkundige reeks). Bovendien kunnen we met zo’n formule meer over de getallen Fn te weten komen, bijvoorbeeld hoe snel de getallen in grootte toenemen. Anders geformuleerd: komt er een bevolkingsexplosie, en zo ja, wanneer en hoe ernstig is die? Voor Fn kan inderdaad de volgende formule worden afgeleid, maar het is niet zo eenvoudig:

 1  1  5  Fn    5   2  J. Binet, 1786-1856, Frans wiskundige

n1

1 5    2 

n1 

  

Deze formule wordt de formule van Binet genoemd en is nogal verrassend omdat het niet duidelijk is dat het rechterlid voor elke n  een geheel getal is. Het zou te ver voeren om te laten zien hoe de formule verkregen wordt of te bewijzen dat de formule van Binet correct is, hoewel dit laatste met een bewijsmethode, die in Discrete wiskunde B behandeld wordt, wel mogelijk is. Op zoek naar de Gulden snede Getallen als in de formule van Binet komen ook op heel andere plaatsen in de wiskunde voor. Een van die plaatsen is de gulden snede, waar een rijke historie bij hoort. Een van de open problemen uit de geschiedenis van de Griekse wiskunde betreft de vraag hoe men heeft ontdekt dat er grootheden bestaan die ‘onderling onmeetbaar’ zijn, zoals de Grieken zeggen, dat wil zeggen: grootheden die geen gemene maat hebben en zich dus niet verhouden als gehele getallen. Vermoedelijk hebben Pythagoreeërs, de volgelingen van Pythagoras, deze ‘irrationaliteit’ rond 400 v. Chr. ontdekt en was het een grote schok, omdat men aanvankelijk dacht dat alle grootheden in de kosmos uit te drukken waren in gehele getallen en hun onderlinge verhoudingen. Het verhaal gaat dat Hippasos van Metapontum de ontdekker van de onderling onmeetbare grootheden was, en dat hij als straf voor de bekendmaking hiervan de verdrinkingsdood heeft gevonden. In de afgebeelde regelmatige vijfhoek komt de onderlinge onmeetbaarheid voor. De grootte van de hoeken is met stippen aangegeven: één stip staat voor 36°, twee en drie stippen voor 72° en 108°. Wanneer nu ∆ABD met daarin ∆C'AB uit de regelmatige vijfhoek wordt gelicht, valt een aantal dingen op. Ten eerste dat de beide driehoeken gelijkvormig zijn. Ten tweede valt er iets te zeggen over de lijnstukken AB, BC' en C'D. Omdat in ∆ABC' twee hoeken gelijk zijn, zijn ook de zijden AB en BC' gelijk. Maar ook in ∆BC'D zijn twee hoeken gelijk, dus zijn ook de zijden BC' en C'D gelijk. Kortom AB = BC' = C'D. Vanwege de gelijkvormigheid van ∆C'AB en ∆ABD geldt nu de evenredigheid BD/AB = AB/AC'. Omdat AB = C'D en BD = AD is deze evenredigheid uit te drukken in lijnstukken die alle op de diagonaal AD liggen, namelijk AD/C'D = C'D/AC'.

Wat staat hier eigenlijk? Als we AD even als het ‘geheel’ bestempelen, C'D als het ‘grootste’ deel en AC' als het ‘kleinste’, dan luidt de evenredigheid: geheel : grootste = grootste : kleinste. Deze verdeling van een lijnstuk en de bijbehorende (vaste) verhouding worden sinds de 16-de eeuw de ‘gulden snede’ genoemd; de Grieken spraken gewoon van ‘snede’. Een opmerkelijke eigenschap van de gulden snede komt naar voren wanneer AC' nu op C'D wordt afgepast (B'D is gelijk aan AC'), waarbij de verhouding C'D/AC' gelijk is aan C'D/B'D. Maar deze laatste verhouding correspondeert ook weer met de verhouding van de gulden snede! En dus geldt weer de evenredigheid C'D/B'D = B'D/B'C'. Vervolgens kan B'C' weer op B'D worden afgepast, enzovoort. De verhouding van de gulden snede blijft steeds gehandhaafd. Dit proces herinnert aan het algoritme van Euclides, waarmee de grootste gemene maat van twee grootheden wordt gevonden op het moment dat een rest juist een geheel aantal malen op een vorige rest kan worden afgepast. Maar wanneer twee grootheden zich verhouden als de gulden snede, zal een rest nooit precies op een vorige rest kunnen worden afgepast. In dat geval zijn ze onderling onmeetbaar en is hun verhouding ‘irrationaal’, zoals Euclides in zijn Elementen zegt. Tegenwoordig associëren we het begrip ‘irrationaliteit’ met een getal dat niet als een breuk is te schrijven. Om het getal van de gulden sneden op te sporen, stellen we AD = 1, C'D = d, zodat AC' = 1 – d. De evenredigheid AD/C'D = C'D/AC' wordt nu 1/d = d/(1 – d). Dit geeft voor d een vergelijking van de tweede graad met als positieve oplossing d = (–1 + 5)/2  0,61803, het gulden-snedegetal. De verhouding van de gulden snede wordt veelvuldig in de kunst gebruikt, omdat voorwerpen die volgens deze verhouding zijn gemaakt, er ‘mooi’ uitzien. Voorbeelden daarvan zijn lengte en breedte van zalen, van schilderijen, van foto’s. Ook vele bouwwerken zijn ontworpen volgens de verhouding van de gulden snede, zoals de triomfboog van Constantijn in Rome, waarin de middelste boog de totale hoogte verdeelt volgens de gulden snede.

Ter afsluiting van deze paragraaf nog de volgende opmerkingen. Wat we voor het konijnenprobleem gezien hebben, illustreert een algemene werkwijze. Voor een probleem bekijken we eerst een paar eenvoudige gevallen. Mede aan de hand van die gevallen wordt een recurrentie gegokt, waarvan we vervolgens proberen aan te tonen dat het de juiste is. Lukt dat, dan kunnen we met die recurrentie aan de slag: meer gevallen berekenen, wellicht een formule afleiden, ...

E. Lucas (18421891), Frans wiskundige

De rij van Fibonacci is zeker geen goed model voor de groei van een konijnenpopulatie (in dit model sterven bijvoorbeeld geen konijnen). Maar de belangstelling voor deze rij is altijd erg groot gebleven, omdat ze steeds weer opnieuw in allerlei problemen opduikt. Zo werd de rij, en varianten ervan, door Lucas gebruikt in zijn onderzoek naar priemgetallen. Overigens heeft Lucas ook de naam ‘rij van Fibonacci’ geïntroduceerd. Aan recurrenties die wel een goede weergave van bevolkingsgroei geven (of van andere vormen van groei), wordt veel onderzoek verricht, met name in verband met de recent opgekomen chaostheorie. Hierbij is één van de grote verrassingen dat een eenvoudige recurrentie zeer complexe structuren kan voortbrengen, de zogenaamde fractals. We gaan hier verder niet op in, maar geven wel een voorbeeld van een eenvoudige recurrentie die aanleiding geeft tot onvoorspelbaar of chaotisch gedrag. Voor een willekeurige startwaarde x0  definiëren we de rij x0, x1, x2, ... door de recurrentie

x n 1 

3 x  1 als x n oneven   n x n als x n even   2

Neem als voorbeeld x0 = 3, dan geldt dat x1 = 10, x2 = 5, x3 = 16, x4 = 8, x5 = 4, x6 = 2, x7 = 1, x8 = 4, x9 = 2, x10 = 1, ... en we zien dat de rij zich verder blijft herhalen met 4, 2, 1. Zodra de waarde 1 erin voorkomt, is de rij dus verder niet meer interessant. Daarom spreken we af dat de rij stopt zodra het getal 1 optreedt. Het nog altijd onopgeloste vermoeden is, dat voor iedere startwaarde x0 de rij bij 1 stopt; dit wordt het ‘3x+1-probleem’ genoemd. Bovendien hangt het aantal iteraties dat men moet uitvoeren om bij een gegeven x0 de waarde 1 te bereiken, op een zeer grillige wijze af van x0. Vaak gaan de getallen in de rij in grootte wild op en neer, bereiken grote waarden en komen op onvoorspelbare wijze tot de waarde 1. Probeer eens x0 = 9 of x0 = 27. Een computerprogramma is daarbij wel zo handig (en eenvoudig te schrijven). Voor 27 zijn 111 iteraties nodig en de maximale waarde die bereikt wordt, is 9232. In de figuur is voor 27 het verloop van de waarden xn te zien.

Het 3x+1-probleem voor de startwaarde 27.

OPGAVE 11.29 (Aanw)

In deze opgave willen we het grootste aantal stukken bepalen dat we uit een ronde taart kunnen halen met n rechte sneden. Of, wat op hetzelfde neerkomt: in hoeveel delen kunnen we het platte vlak maximaal verdelen met n rechte lijnen. We geven dit aantal aan met Dn. In figuur 11.1 zien we dat D5 = 16.

FIGUUR 11.1

5 rechte lijnen verdelen het vlak in maximaal 16 delen

a Bepaal net zo D1 t/m D4 door figuren te schetsen. Welke waarde heeft D0? b Probeer in de waarden voor Dn een regelmaat te ontdekken en een recurrente betrekking voor Dn op te stellen (beredeneer dat uw recurrentie de juiste is). c Kunt u een formule voor Dn afleiden uit de recurrentie? OPGAVE 11.30 (Aanw)

De getallen Hn worden gedefinieerd door H0 = 0 en Hn = 2Hn–1 + 1 voor n  + (de getallen Hn treden op in de beroemde puzzel ‘Torens van Hanoi’, bedacht door Lucas). a Bepaal de eerste 8 termen uit de rij en probeer in de waarden voor Hn een regelmaat te ontdekken. b Leid een formule voor Hn af uit de recurrentie.

SAMENVATTING

De inductieve definitie van een verzameling V kent drie onderdelen. In de basis worden expliciet één of meer elementen aangegeven die tot V behoren. Vervolgens worden in de inductiestap één of meer regels beschreven waarmee uit oude elementen nieuwe elementen verkregen kunnen worden. Ten slotte vermeldt de uitsluitingsregel uitdrukkelijk dat V geen andere elementen bevat dan welke op grond van de basis en de inductiestap verkregen kunnen worden. Het bekendste voorbeeld is . In het algemeen zijn inductieve definities toe te passen als er sprake is van een discrete structuur (formele talen, grafen, combinatoriek en dergelijke). Nauw verweven met inductie zijn de recursieve definities, waarbij wiskundige objecten, zoals functies en rijen, gedefinieerd worden in termen van zichzelf. Het bekendste voorbeeld is ‘n faculteit’ gedefinieerd door n! = n · (n – 1)! voor n  + met startwaarde 0! = 1. Hierbij wordt tevens een nieuwe notatie gedefinieerd, wat een andere veelgebruikte toepassing is van recursieve definities (denk aan sommen, producten, doorsneden en dergelijke). Bij formele talen wordt recursie gebruikt om talen mee te genereren. Een belangrijk voorbeeld is het vastleggen in BNF van de syntaxis van programmeertalen. Sommen en recurrenties liggen dicht bij elkaar. Voorbeelden zijn de rekenkundige en meetkundige rijen met hun bijbehorende eindige reeksen. De rekenkundige rij met eerste term a en verschil v is recursief gedefinieerd door an = an–1 + v voor n  + en a0 = a. Voor de som van de termen uit een eindige rekenkundige rij, ofwel de eindige rekenkundige n 1 reeks, geldt dat  i 0 (a  iv)  2 (2a  nv )(n  1) . De meetkundige rij met eerste term a en reden r is recursief gedefinieerd door an = ran–1 voor n  + en a0 = a. Voor de som van de termen uit een eindige meetkundige rij, ofwel de eindige meetkundige reeks, geldt dat  ni 0 ari = a(1 – rn+1)/(1 – r), waarbij r ≠ 1. De recursieve definities van de rekenkundige en meetkundige rijen zijn voorbeelden van een recurrente betrekking: een rij die gedefinieerd wordt door een vergelijking waarin de eerdere termen uit de rij voorkomen. Problemen in de discrete wiskunde worden vaak in termen van een recurrente betrekking vertaald, waarna men op zoek gaat naar een expliciete formule. Soms is zo’n formule na wat zoekwerk te gokken. Vervolgens kan men proberen om de formule te bewijzen.

ZELFTOETS

1

2

3

a Laat E de verzameling zijn die inductief gedefinieerd wordt door: i 2 E ii als x E, dan x(x + 1)/2 E iii E bevat geen andere elementen dan die door toepassing van i en ii verkregen kunnen worden. Geef vijf verschillende elementen van E. b Geef een inductieve definitie van {0, 1, 3/2, 7/4, 15/8, ...}. n a Bepaal voor een aantal waarden van n de uitkomst van  k  1 (2k  1) + en gok hiermee een formule voor alle n  . n b Reken  k  1 (2k  1) uit door op te merken dat het een eindige rekenkundige reeks is en controleer hiermee uw gegokte antwoord uit onderdeel a. c Gegeven is de recurrentie an = an–1 + 2n – 1 voor n  met n ≥ 2 en met startwaarde a1 = 1. Bepaal de eerste paar termen an en geef een formule voor an (met bewijs).

a

Bepaal  71 

4 7



9 7

 ... 

b Bereken voor alle n  c 4

Bereken voor alle n 

99 . 7

met n ≥ 2 de som in2 15  11i. de som in0 (5i – 3).

De rij Fibonacci-getallen is gedefinieerd door de recurrentie Fn = Fn–1 + Fn–2 voor n  én n ≥ 2 , met startwaarden F0 = 1 en F1 = 1. De rij Gn bestaat uit alle Fibonacci-getallen met oneven index, dus Gn is de rij 1, 2, 5, 13, 34, 89, ... Geef een recurrente betrekking voor Gn.

Inductieve bewijzen Introductie Leerkern 12.1 12.2

37 38

Volledige inductie 38 Varianten op het basisprincipe

Samenvatting Zelftoets

47

47

43

Leereenheid 12

Inductieve bewijzen

INTRODUCTIE

Bekijk eens het rijtje getallen 0, 3, 21, 117, 609, ..., waarvoor met enig puzzelen een eenvoudige formule gevonden kan worden: 5 n – 2n voor n  . Als we flink wat getallen uit deze rij berekenen, dan valt op dat het steeds drievouden zijn. Maar het feit dat de eerste 10 getallen uit de rij, of de eerste 100, of de eerste 1000, allemaal een drievoud zijn, is nog geen bewijs dat ieder getal van de vorm 5n – 2n met n  een drievoud is. Het vormt er natuurlijk wel een sterke aanwijzing voor. We kunnen de bewering ‘ieder getal van de vorm 5n – 2n is een drievoud’ opvatten als een uitspraak over natuurlijke getallen: voor elk getal n  geldt dat 5n – 2n een drievoud is. In deze leereenheid wordt een bewijsmethode behandeld, de zogeheten volledige inductie, die speciaal geschikt is om dit soort uitspraken mee te bewijzen. De term inductie bent u ook in de vorige leereenheid al tegengekomen. Daar werd een inductieve definitie gegeven van de natuurlijke getallen. U zult in deze leereenheid zien dat de bewijsmethode ‘volledige inductie’ gebaseerd is op deze inductieve definitie van de natuurlijke getallen. Volledige inductie wordt in alle deelgebieden van de wiskunde toegepast. Een voorbeeld is het bewijs van de distributieregel voor een vereniging van n verzamelingen. Deze regel zegt dat we de doorsnede van een verzameling B met de vereniging van n verzamelingen ook kunnen bepalen door eerst elk van n de verzamelingen met B te doorsnijden en vervolgens de vereniging te nemen van deze n doorsnedes. In formulevorm:

B

n i 1

Ai 

n i 1

( B  Ai )

Deze stelling doet een uitspraak over verzamelingen. Zij is echter ook op te vatten als een uitspraak over natuurlijke getallen: voor elke n  geldt dat de doorsnede van B met de vereniging van de verzamelingen A1, A2, ..., An gelijk is aan (B  A1)  (B  A2)  ...  (B  An). De stelling leent zich daarom voor een bewijs met volledige inductie. De natuurlijke getallen vormen maar één voorbeeld van een inductief gedefinieerde verzameling. Voorbeelden van andere inductief gedefinieerde verzamelingen zijn formele talen. Vaak kunnen eigenschappen van inductief gedefinieerde verzamelingen met behulp van een inductief bewijs bewezen worden. Dit is dan ook een krachtig hulpmiddel dat gebruikt wordt in de theorie van de formele talen, in de logica en in feite in alle gebieden van de (toegepaste) wiskunde waarin discrete structuren een rol spelen.

LEERDOELEN

Na het bestuderen van deze leereenheid wordt verwacht dat u – de volgende soorten bewijs met volledige inductie kunt lezen en kunt gebruiken: – een bewijs met startwaarde 0 – een bewijs met een andere startwaarde – een bewijs met meer dan één startwaarde – een inductief bewijs van een eigenschap van een inductief gedefinieerde verzameling kunt lezen. Studeeraanwijzing Er is een nauw verband tussen inductieve definities en inductieve bewijzen. Bekijk zo nodig leereenheid 11 nog eens voordat u begint met het bestuderen van deze leereenheid.

LEERKERN 12.1 Ga na dat dit drievouden zijn.

Volledige inductie

Bekijk eens de rij 0, 3, 21, 117, 609, ... In de introductie werd al vermeld dat met enig puzzelen een formule voor deze rij te vinden is: het zijn de getallen 5n – 2n met n  . Als we flink wat getallen uit de rij berekenen, dan valt op dat het steeds drievouden zijn: 0, 3, 21, 117, 609, 3093, 15561, 77997, 390369, ... Hoe meer voorbeelden we uitrekenen, des te sterker vermoeden we dat 5n – 2n voor iedere n  een drievoud is. Maar hoeveel voorbeelden we ook uitrekenen, dit zal nooit een bewijs zijn dat ieder getal van de vorm 5n – 2n een drievoud is. Deze bewering doen we immers voor alle n  , wat oneindig veel getallen zijn.

OPGAVE 12.1

Laat zien dat voor n = 0 t/m 15 de getallen n2 – n + 41 priemgetallen zijn (dus alleen deelbaar door 1 en zichzelf). Denkt u dat n2 – n + 41 voor iedere n  een priemgetal is? We laten ons door opgave 12.1 niet van ons stuk brengen en blijven volharden in het vermoeden dat 5n – 2n voor iedere n  een drievoud is. Hoe zouden we dit kunnen bewijzen? De methode die we gaan gebruiken, illustreren we eerst aan de hand van een rekenvoorbeeld. Van 3093 = 55 – 25 zien we meteen dat het een drievoud is, maar van 15561 = 56 – 26 is dat wat minder duidelijk. We kunnen gewoon door 3 delen, maar deze ‘directe’ aanpak helpt ons niet op weg naar een algemeen bewijs. Een andere methode probeert 15561 = 56 – 26 in verband te brengen met 3093 = 55 – 25, waarvan we immers weten dat het een drievoud is. De afzonderlijke termen 56 en 26 zijn eenvoudig in verband te brengen met 55 en 25 omdat 56 = 5 · 55 en 26 = 2 · 25. We hebben nu wel dat 15561 = 56 – 26 = 5 · 55 – 2 · 25, maar hierin herkennen we nog niet een term 55 – 25. Die kunnen we wel krijgen door (bijvoorbeeld) 5 · 25 af te trekken, wat we moeten compenseren door er 5 · 25 bij op te tellen: Ga dit na.

56 – 26 = 5 · 55 – 5 · 25 + 5 · 25 – 2 · 25 = 5 · (55 – 25) + 3 · 25 Het ‘wonder’ is dat naast het drievoud 55 – 25, wat met opzet gecreëerd is, als extra term het drievoud 3 · 25 optreedt. Ook 5 · (55 – 25) + 3 · 25 is dan een drievoud, waarmee bewezen is dat 15561 = 5 6 – 26 een drievoud is.

Deze methode brengt ons op het idee om op precies dezelfde manier af te leiden dat 57 – 27 een drievoud is: 57 – 27 = 5 · (56 – 26) + 3 · 26 en omdat 56 – 26 en 3 · 26 drievouden zijn, volgt dat 57 – 27 een drievoud is. OPGAVE 12.2

a Bewijs op dezelfde manier dat 58 – 28 en 59 – 29 drievouden zijn. b Neem aan dat bewezen is dat 5321 – 2321 een drievoud is. Bewijs dan dat 5322 – 2322 een drievoud is. In het algemeen is zo voor een willekeurige n  af te leiden dat 5n+1 – 2n+1 een drievoud is, als we weten dat 5n – 2n een drievoud is: 5n+1 – 2n+1 = 5 · (5n – 2n) + 3 · 2n

Zie paragraaf 11.1.

(12.1)

Omdat 3 · 2n een drievoud is, volgt uit formule 12.1 en de aanname dat 5n – 2n een drievoud is, dat ook 5n+1 – 2n+1 een drievoud is. In formule 12.1 mogen we voor n een willekeurige waarde invullen, waardoor het hiervoor in gang gezette proces steeds is voort te zetten: 5 9 – 29 is een drievoud (zie opgave 12.2), dus 510 – 210 is een drievoud (pas formule 12.1 toe met n = 9), dus 511 – 211 is een drievoud (formule 12.1 met n = 10), enzovoort. Volgens de inductieve definitie van komt ieder getal in aan bod als we ‘steeds 1 optellen’. Het doel is hiermee bereikt: de bewering ‘5n – 2n is voor iedere n  een drievoud’ is bewezen. Belangrijk is wel dat het proces in gang is gezet met de opmerking dat 3093 een drievoud is. Waar we het proces precies laten beginnen, is niet zo belangrijk: we hadden het ook kunnen starten met 21, 3 of zelfs 0 (wat ook een drievoud is).

OPGAVE 12.3 (Aanw)

Ga voor een aantal waarden van n  na dat 4n + 2 een drievoud is. Laat vervolgens voor willekeurige n  zien: als 4n + 2 een drievoud is, dan is ook 4n+1 + 2 een drievoud. Beschrijving van de algemene methode

Stap i: P(0) is waar. Stap ii: als P(n) waar is, dan is ook P(n+1) waar.

Na deze voorbeelden wordt het tijd om een formele beschrijving te geven van de gevolgde bewijsmethode. Stel dat we op een of andere manier aan een uitspraak P(n) zijn gekomen waarvan we vermoeden dat deze waar is voor alle n  . In ons voorbeeld was P(n) de uitspraak ‘5n – 2n is een drievoud’. Hoe we in het algemeen aan zo’n vermoeden komen, is een andere kwestie waar we zo dadelijk nog wat over zeggen. Om te bewijzen dat P(n) waar is voor alle n  , beginnen we eerst maar eens te bewijzen dat P(0) waar is. Voor ons voorbeeld betekent dit dat we moeten bewijzen dat 50 – 20 = 0 een drievoud is, wat juist is. Vervolgens laten we voor willekeurige n  zien: als P(n) waar is, dan is ook P(n + 1) waar. In ons voorbeeld volgt dit uit formule 12.1: als 5n – 2n een drievoud is, dan is ook 5n+1 – 2n+1 een drievoud. De essentie van formule 12.1 is dat daarin een verband is gelegd tussen 5 n – 2n en het ‘volgende’ getal in de rij, namelijk 5n+1 – 2n+1. Samengevat bestaat de bewijsmethode uit de volgende twee stappen: i bewijs dat P(0) waar is ii bewijs voor willekeurige n  : als P(n) waar is, dan is P(n + 1) waar.

Stappen i en ii bewijzen P(n) voor alle n  .

Deze bewijsmethode volgt precies de inductieve definitie van : in stap i wordt de uitspraak P(n) bewezen voor de basis n = 0, in stap ii wordt bewezen dat P(n) waar blijft als we de inductiestap n  n + 1 uitvoeren. Beginnend met P(0) passen we dan herhaald ii toe: – Omdat P(0) waar is, volgt dat P(1) waar is (pas ii toe met n = 0). – Omdat P(1) waar is, volgt dat P(2) waar is (pas ii toe met n = 1). – Omdat P(2) waar is, volgt dat P(3) waar is. Enzovoort. Omdat er op grond van de uitsluitingsregel geen andere elementen tot behoren, is P(n) bewezen voor alle n  . Deze bewijsmethode wordt goed geïllustreerd met het beeld van een rij omvallende dominostenen: als de eerste steen omvalt (‘steen P(0) valt’), dan volgen uiteindelijk alle andere stenen, als tenminste alle stenen goed geplaatst zijn (‘als steen P(n) valt, dan valt steen P(n + 1)’).

OPGAVE 12.4

Voor willekeurige n  geldt: als 5n + 3 deelbaar is door 12, dan is ook 5n+1 + 3 deelbaar door 12, omdat 5n+1 + 3 = 5 · (5n + 3) – 12. Is nu bewezen dat 5n + 3 deelbaar is door 12 voor alle n  ? Motiveer uw antwoord. Vanwege de nauwe relatie met de inductieve definitie van , wordt de hier gevolgde bewijsmethode het bewijs met volledige inductie genoemd, of korter het inductiebewijs. In de tweede stap proberen we te bewijzen dat P(n + 1) waar is, door aan te nemen dat P(n) waar is. Omdat voor ‘aanname’ ook de term ‘hypothese’ wordt gebruikt, heet P(n) de inductiehypothese. Het doel in de tweede stap is dus altijd om P(n + 1) in verband te brengen met P(n), waarvan we immers aannemen dat deze waar is. In het volgende voorbeeld laten we zien hoe een bewijs met volledige inductie kort wordt opgeschreven.

Bewijs met volledige inductie

Inductiehypothese

VOORBEELD

We bewijzen met volledige inductie dat 7n + 5 deelbaar is door 6 voor alle n  . i Voor n = 0 geldt dat 7n + 5 = 6, wat deelbaar is door 6. ii Laat n  willekeurig zijn en neem aan dat 7n + 5 deelbaar is door 6, dan moeten we bewijzen dat 7n+1 + 5 deelbaar is door 6. Maar we kunnen 7n+1 + 5 als volgt met 7n + 5 in verband brengen: 7n+1 + 5 = 7(7n + 5) – 6 · 5. Omdat nu 7n + 5 deelbaar is door 6 (inductiehypothese) en 6 · 5 deelbaar is door 6, volgt er dat 7n+1 + 5 deelbaar is door 6. We hebben dus bewezen: als 7n + 5 deelbaar is door 6, dan is 7 n+1 + 5 deelbaar door 6. Uit stappen i en ii volgt dat 7n + 5 deelbaar is door 6 voor alle n  . «

Geef steeds de inductiehypothese aan.

Met de formule 7n+1 + 5 = 7(7n + 5) – 6 · 5 wordt in dit voorbeeld het essentiële verband gelegd tussen 7n + 5 en het ‘volgende’ getal 7n+1 + 5. Dit kan vaak op meer dan één manier. Hier zouden we bijvoorbeeld ook 7n+1 + 5 = 6 · 7n + (7n + 5) gebruikt kunnen hebben. Het is een goede gewoonte om, net als in voorgaand voorbeeld, in een bewijs met volledige inductie precies aan te geven waar de inductiehypothese wordt gebruikt.

OPGAVE 12.5

Bewijs met volledige inductie dat 8n – 3n een vijfvoud is voor alle n  .

Hoe komen we aan P(n)?

Een inductiebewijs is alleen mogelijk als we een concrete uitspraak P(n) hebben waarvan we vermoeden dat deze juist is voor alle n  . Hoe we aan P(n) gekomen zijn, wordt in de voorbeelden en opgaven meestal niet duidelijk gemaakt. In de praktijk wordt P(n) vaak gevonden door een combinatie van abstracte argumenten, vage aanwijzingen en ‘verstandig gokwerk’, die voor een aantal waarden van n is gecontroleerd (vaak n = 0, 1, 2, ...). Met behulp van een computerprogramma, of een ‘symbolisch computeralgebrapakket’, kan men tegenwoordig het gokwerk al met aardig wat waarden van n ondersteunen (soms tot in de miljoenen). Hebben we eenmaal een gegrond vermoeden dat een uitspraak P(n) voor alle n  waar zou kunnen zijn, dan kan een bewijs met volledige inductie geprobeerd worden. Het is zeker niet zo dat iedere uitspraak P(n) met volledige inductie bewezen hoeft te worden: er kan een direct bewijs mogelijk zijn dat wellicht zelfs eenvoudiger is. Om het basisprincipe van inductiebewijzen goed in de vingers te krijgen, volgen nu nog meer voorbeelden en opgaven. In een enkel voorbeeld laten we zien hoe we tot een verstandige gok van een te bewijzen uitspraak kunnen komen. In de volgende paragraaf behandelen we een aantal veelgebruikte varianten van het inductiebewijs.

VOORBEELD

In opgave 11.30 bekeken we de recurrentie Hn = 2Hn–1 + 1 voor n  + met startwaarde H0 = 0. De eerste 8 termen van deze rij zijn: 0, 1, 3, 7, 15, 31, 63, 127. We herkennen hierin de getallen 2 n – 1 en gokken daarom dat Hn = 2n – 1 voor iedere n  . Is dit met volledige inductie te bewijzen? i Omdat H0 = 0 en 20 – 1 = 0, is de uitspraak waar voor n = 0. ii Neem aan dat Hn = 2n – 1 voor een willekeurige n  , dan moeten we bewijzen dat Hn+1 = 2n+1 – 1. We gebruiken nu de recurrentie om Hn+1 in verband te brengen met het vorige getal Hn: Hn+1 = 2Hn + 1. Omdat nu Hn = 2n – 1 (inductiehypothese), volgt er dat Hn+1 = 2(2n – 1) + 1, wat inderdaad gelijk is aan 2n+1 – 1. Uit i en ii volgt dat Hn = 2n – 1 voor iedere n  . «

VOORBEELD

Uit paragraaf 11.2.2 weten we dat de som van de eindige rekenkundige reeks 0 + 1 + ... + n gegeven wordt door het n-de driehoeksgetal n(n + 1)/2 (zie formule 11.2). Dit resultaat is ook met volledige inductie te bewijzen. n Laat dus P(n) de uitspraak zijn:  i 0 i  n(n  1)/ 2 voor iedere n  . i P(0) is zeker waar, immers dan bestaat de som uit alleen het getal 0 en ook n(n + 1)/2 = 0 voor n = 0. ii Neem aan dat P(n) waar is voor een willekeurige n  , dan moeten we bewijzen dat P(n + 1) waar is. De uitspraak P(n + 1) verkrijgen we uit P(n) door overal n te vervangen door n + 1. We moeten dus bewijzen dat 1  ni 0 i  (n  1)(n  2)/ 2 . Daartoe splitsen we van de som in het linkerlid de laatste term met i = n + 1 af, dus:

n 1

n

i 0

i 0

 i   i  (n  1)

Het afsplitsen van een laatste term in een som is een ‘truc’ die meestal gebruikt wordt, omdat daarna de inductiehypothese is toe te passen. Immers, vanwege de inductiehypothese geldt nu dat  ni 0 i = n(n + 1)/2, dus volgt er dat n 1

 i  12 n( n  1)  ( n  1)

i 0

wat we vereenvoudigen tot (n + 1)(n/2 + 1) = (n + 1)(n + 2)/2. Dit bewijst 1 dat inderdaad  ni 0 i = (n + 1)(n + 2)/2, ofwel dat P(n + 1) waar is. Samen met i volgt nu dat P(n) waar is voor alle n  . « VOORBEELD

In dit voorbeeld bekijken we het probleem in hoeveel delen Dn het vlak maximaal te verdelen is met n (rechte) lijnen (zie opgave 11.29). We hebben dat D0 = 1, en door figuren te schetsen, vinden we dat D1 = 2, D2 = 4, D3 = 7 en D4 = 11. De getallen 2, 4, 7 en 11 schelen precies 1 met de driehoeksgetallen 1, 3, 6 en 10, waarmee het vermoeden ontstaat dat Dn = 1 + n(n + 1)/2. We proberen dit met volledige inductie te bewijzen. i Omdat D0 = 1, is de formule waar voor n = 0. ii Neem aan dat Dn = 1 + n(n + 1)/2 voor een willekeurige n  , dan moeten we bewijzen dat Dn+1 = 1 + (n + 1)(n + 2)/2. Volgens de inductiehypothese is het vlak met n lijnen in 1 + n(n + 1)/2 stukken te verdelen. Trek de (n + 1)-ste lijn zó dat deze met geen van de n gegeven lijnen evenwijdig is, en niet door een al bestaand snijpunt gaat. Dit geeft het maximale aantal van n snijpunten, ofwel n + 1 extra vlakdelen. Zie figuur 12.1.

FIGUUR 12.1

n lijnen die gesneden worden door een nieuwe lijn, geven maximaal n + 1 extra vlakdelen

Met n + 1 lijnen is het vlak dus te verdelen in maximaal 1 + n(n + 1)/2 + (n + 1) = 1 + (n + 1)(n + 2)/2 delen. Er geldt dus Dn+1 = 1 + (n + 1)(n + 2)/2 als we aannemen dat Dn = 1 + n(n + 1)/2. Uit i en ii volgt dat Dn = 1 + n(n + 1)/2 voor iedere n  . « OPGAVE 12.6 (Aanw)

Hiervoor is met volledige inductie een formule bewezen voor de som van de getallen 1 t/m n. Is er een formule voor de som van de kwadraten van de getallen 1 t/m n? Met gok- en probeerwerk kunnen we tot het vermoeden komen dat voor alle n  geldt dat:

n

 i 2  16 n( n  1)(2n  1)

i 0

Controleer de formule voor n = 0, 1, 2 en 3 en probeer vervolgens de formule te bewijzen met volledige inductie. OPGAVE 12.7 (Aanw)

Bewijs met volledige inductie de volgende uitspraken (voor alle n  ). a 9n+1 + 63 is deelbaar door 72. b Als an gedefinieerd wordt door de recurrentie an = 3an–1 + 2n + 1 voor n  + met startwaarde a0 = 3, dan geldt dat an = 5 · 3n – n – 2. OPGAVE 12.8

Van een dier hebben we één exemplaar dat (door ongeslachtelijke voortplanting) na 1 week slechts éénmalig 2 nakomelingen produceert. Ieder van de nakomelingen produceert weer na 1 week éénmalig 2 nakomelingen, enzovoort. a Laat zien dat het aantal dieren na n weken gegeven wordt door  ni 0 2i (ga ervan uit dat er geen dieren sterven). b Bepaal voor enige waarden van n de uitkomst van de som uit onderdeel a, gok daarmee een expliciete formule voor de som en probeer die formule met volledige inductie te bewijzen. OPGAVE 12.9

Een student op reis in Yland ziet in de wei een zwart schaap staan en roept: ‘Hé, alle schapen in Yland zijn zwart’. Hij geeft zelfs een inductiebewijs. Laat S een verzameling zijn van schapen in Yland. Bewering: alle schapen in S hebben dezelfde kleur (en dus zijn alle schapen in Yland zwart). De bewering bewijzen we als volgt. i Als S bestaat uit één schaap, dan is de bewering waar. ii Neem aan dat in iedere verzameling van n schapen geldt dat ze allemaal dezelfde kleur hebben. Laat S bestaan uit n + 1 schapen die we met s1, s2, ..., sn, sn+1 aangeven. Uit de inductiehypothese volgt dat zowel {s1, s2, ..., sn} als {s2, ..., sn, sn+1} bestaan uit schapen van dezelfde kleur. Hieruit volgt dat alle schapen in S dezelfde kleur hebben. Wat is hier mis? 12.2

Varianten op het basisprincipe

Al onze inductiebewijzen hadden steeds n = 0 als startpunt. Dat moet ook wel als een uitspraak voor alle n  bewezen moet worden. Soms zullen we een uitspraak willen bewijzen die niet per se voor alle n  geldt, maar pas vanaf zekere n0  . We geven een voorbeeld. VOORBEELD

Het is niet waar dat n! > 2n voor alle n  . Zo geldt 3! = 6 en 23 = 8. Maar er geldt wel dat n! > 2n voor alle n  met n ≥ 4. We bewijzen dit als volgt met volledige inductie. i Omdat 4! = 24 en 24 = 16, is de uitspraak waar voor n = 4. ii Neem aan dat n! > 2n voor een willekeurige n  met n ≥ 4, dan moeten we bewijzen dat (n + 1)! > 2n+1. Omdat (n + 1) > 0 en n! > 2n (inductiehypothese), volgt er dat (n + 1)n! > (n + 1)2n. In het linkerlid van deze ongelijkheid staat de gewenste uitdrukking (n + 1)!, maar in het rechterlid staat nog niet de gewenste uitdrukking 2n+1.

We willen dus (n + 1)2n vervangen door 2n+1, ofwel n + 1 door 2. Dit kunnen we ook zonder probleem doen, omdat voor n ≥ 4 zeker geldt dat n + 1 > 2 en dus dat (n + 1) · 2n > 2 · 2n (= 2n+1). Dit bewijst inderdaad dat (n + 1)! > 2n+1 als we aannemen dat n! > 2n. Uit i en ii volgt dat n! > 2n voor alle n  met n ≥ 4. « In dit voorbeeld start het inductieproces bij n = 4. In het algemeen kan iedere n0  als ‘startwaarde’ dienen. We krijgen dan de volgende variant voor het inductiebewijs. Inductiebewijs met een andere startwaarde

i Bewijs dat P(n0) waar is. ii Bewijs voor willekeurige n  P(n + 1) waar.

met n ≥ n0: als P(n) waar is, dan is

Uit i en ii volgt dat P(n) waar is voor alle n  ‘standaardinductie’ geldt dat n0 = 0.

met n ≥ n0. Voor de

OPGAVE 12.10 (Aanw)

Er geldt voor zekere n0  dat 2n + 1 ≤ 2n voor alle n  met n ≥ n0. Bepaal de kleinste n0 en bewijs de uitspraak met volledige inductie. Een andere variant neemt als inductiehypothese niet alleen aan dat P(n) waar is, maar dat P(0) tot en met P(n) waar zijn. Het schema wordt dan als volgt. Inductiebewijs met een andere inductiehypothese

i Bewijs dat P(0) waar is. ii Bewijs voor willekeurige n  : als P(k) waar is voor k = 0, 1, ..., n, dan is ook P(n + 1) waar. Net als bij het oorspronkelijke inductiebewijs kunnen we, beginnend met P(0), herhaald ii toepassen en concluderen dat P(n) waar is voor alle n  . Omdat P(0) waar is, volgt dat P(1) waar is (pas ii toe met n = 0). Omdat nu P(0) en P(1) waar zijn, volgt dat P(2) waar is (pas ii toe met n = 1). Omdat P(0), P(1) en P(2) waar zijn, volgt dat P(3) waar is. Enzovoort. Ook hier geldt dat we niet per se bij 0 hoeven te beginnen.

OPGAVE 12.11

Geef het schema van voorgaande variant van het inductiebewijs voor het geval we niet bij 0, maar bij n0  beginnen. VOORBEELD

Een geheel getal p ≥ 2 is een priemgetal als het alleen deelbaar is door 1 en p. Dus 2, 3 en 5 zijn priemgetallen, 4 en 6 niet. Volgens een bekend resultaat uit de getaltheorie is iedere n  met n ≥ 2 te schrijven als product van priemgetallen (zo zijn 4 = 22, 6 = 2 · 3 en 180 = 22 · 32 · 5). Dit resultaat is met volledige inductie te bewijzen. i We starten de inductie bij 2, wat zelf een priemgetal is en dus in het bijzonder een product van priemgetallen is (met maar één factor). ii Neem aan dat 2, 3, 4, ..., n te schrijven zijn als product van priemgetallen, dan moeten we bewijzen dat n + 1 te schrijven is als product van priemgetallen. Is n + 1 een priemgetal, dan zijn we meteen klaar. Is het geen priemgetal, dan is n + 1 deelbaar door een getal l  met 1 < l < n + 1.

Er geldt dan dat n + 1 = kl, waarbij 2 ≤ k ≤ n en 2 ≤ l ≤ n (met k, l  ). Omdat volgens de inductiehypothese k en l te schrijven zijn als product van priemgetallen, geldt dit ook voor n + 1 = kl. Uit i en ii volgt dat iedere n  met n ≥ 2 te schrijven is als product van priemgetallen. « Inductiebewijs met meer dan één startwaarde

In de laatste variant die we zullen behandelen, wordt het inductieproces niet op gang gebracht door één startwaarde n0  , maar door meer dan één startwaarde.

VOORBEELD

Gegeven is de recurrentie an = 5an–1 – 6an–2 voor n  met n ≥ 2 en met startwaarden a0 = 2 en a1 = 9. We beweren nu dat an = 5 · 3n – 3 · 2n voor alle n  en willen dit met volledige inductie bewijzen. i Omdat 5 · 30 – 3 · 20 = 2 = a0 en 5 · 31 – 3 · 21 = 9 = a1, is de formule waar voor n = 0 en n = 1. ii Neem aan dat de formule voor an en an–1 waar is, dan moeten we bewijzen dat de formule waar is voor an+1. Uit de recurrentie volgt dat an+1 = 5an – 6an–1. Maar nu kunnen we de inductiehypothese voor an en an–1 toepassen en dus de formules an = 5 · 3n – 3 · 2n en an–1 = 5 · 3n–1 – 3 · 2n–1 gebruiken. Als we deze invullen, volgt dat an+1 = 5an – 6an–1 = 5(5 · 3n – 3 · 2n) – 6(5 · 3n–1 – 3 · 2n–1) Het rechterlid hiervan willen we nu naar het antwoord ‘toepraten’, dus naar 5 · 3n+1 – 3 · 2n+1. Dit gaat het handigst door overal factoren 3n–1 en 2n–1 als volgt buiten haakjes te halen: 5(5 · 3n – 3 · 2n) – 6(5 · 3n–1 – 3 · 2n–1) = (5 · 5 · 3 – 6 · 5)3n–1 – (5 · 3 · 2 – 6 · 3)2n–1 = 45 · 3n–1 – 12 · 2n–1 = 5 · 3n+1 – 3 · 2n+1 Hiermee is dus inderdaad aangetoond dat an+1 = 5 · 3n+1 – 3 · 2n+1, ofwel dat de formule ook voor an+1 waar is. Omdat de formule waar is voor n = 0 en n = 1 (zie i), volgt uit ii dat de formule waar is voor n = 2, vervolgens voor n = 3, enzovoort. Dit toont aan dat de formule waar is voor alle n  . «

OPGAVE 12.12

Geef het algemene schema van een inductiebewijs voor een uitspraak P(n) waarvoor twee startwaarden n0  en n0 + 1 nodig zijn. Tot nu toe hebben we ons beperkt tot uitspraken die we wilden bewijzen voor alle natuurlijke getallen (vanaf een zekere n0  ). Ook voor uitspraken over andere inductief of recursief gedefinieerde objecten (verzamelingen, functies, talen en dergelijke) is het vaak mogelijk om een inductiebewijs te geven. Er zijn weer verschillende varianten, waarbij onder meer een rol speelt hoe gecompliceerd de inductieve of recursieve definitie is. Voor een inductief gedefinieerde verzameling V hangt dit bijvoorbeeld af van het aantal elementen in de basis en het aantal regels in de inductiestap. Het meest algemene schema ziet er voor dit geval als volgt uit (de formulering is uit de aard der zaak nogal vaag).

Inductiebewijs voor uitspraken over de elementen van een inductief gedefinieerde verzameling

i Bewijs dat P(b) waar is voor alle b uit de basis van V. ii Bewijs voor een willekeurige x V: als P(x) waar is, dan is ook P(y) waar voor iedere y V die uit x te verkrijgen is door het toepassen van de regels uit de inductiestap. Een voorbeeld van een dergelijk inductiebewijs is de redenering die aantoont dat alle strings uit Hofstadter’s taal L (zie voorbeeld 11.1) met een M beginnen: i MI begint met een M ii Neem aan dat w een string uit L is die met een M begint, dan moeten we bewijzen dat alle strings in L die uit w ontstaan door het toepassen van de regels uit de inductiestap, ook met een M beginnen. Als w van de vorm xI is, dan behoort ook xIU tot L, wat met M begint. Als w = Mx, dan behoort ook Mxx tot L, wat met M begint. Als w = xIIIy, dan behoort ook xUy tot L, wat met M begint. Als w = xUUy, dan behoort ook xy tot L, wat met M begint. Omdat alle strings in L op deze wijze ontstaan (de uitsluitingsregel), volgt uit i en ii dat alle strings in L met een M beginnen. Dit type inductiebewijs komt vaak voor als men eigenschappen wil bewijzen voor de strings uit een inductief gedefinieerde taal. Heel algemeen zijn inductiebewijzen te verwachten in situaties waarin ‘discrete structuren’ een rol spelen.

OPGAVE 12.13 (Aanw)

In Hofstadter’s boek is de centrale vraag over L: behoort de string MU tot L? Los deze MU-puzzel op door te bewijzen dat in de strings uit L het aantal I’s nooit een 3-voud is. OPGAVE 12.14 (Aanw)

Er geldt voor zekere n0  dat n! > 3n voor alle n  met n ≥ n0. Bepaal de kleinste n0 en bewijs de uitspraak met volledige inductie. OPGAVE 12.15 (Aanw)

Bewijs met volledige inductie dat

B

n i 1

Ai 

n i 1

( B  Ai ) voor elke n 

OPGAVE 12.16 (Aanw)

met n ≥ 1.

Gegeven is de recurrentie tn = tn–1 + 6tn–2 – 12n + 8 voor n  met n ≥ 2 en met de twee startwaarden t0 = 5 en t1 = 6. Bewijs met volledige inductie dat tn = 3n + (–2)n + 2n + 3.

SAMENVATTING

De inductieve bewijsmethode komt in vele varianten voor en wordt vaak toegepast in situaties waarin objecten op inductieve of recursieve wijze gedefinieerd zijn (verzamelingen, functies, rijen, talen en dergelijke). Eén van de varianten voor het inductiebewijs van een uitspraak P(n) voor alle n  met n ≥ n0 (n0  ) ziet er als volgt uit. i Bewijs dat P(n0) waar is. ii Bewijs voor willekeurige n  met n ≥ n0: als P(n) waar is (de inductiehypothese), dan is P(n + 1) waar. Er zijn varianten met een andere inductiehypothese en/of meer dan één startwaarde, terwijl er ook varianten zijn om uitspraken te bewijzen over andere inductief of recursief gedefinieerde objecten.

ZELFTOETS

1

Bewijs met volledige inductie dat nk 0 1/2k  2  1/2n voor alle n  .

2

a Bepaal de kleinste waarde n0  + waarvoor geldt dat n2 < 2(n – 1)2. b Bewijs voor de waarde n0 uit onderdeel a dat n2 < 2(n – 1)2 voor alle n ≥ n0.

3

Laat Fn de Fibonacci-getallen zijn, gedefinieerd door de recurrentie Fn = Fn–1 + Fn–2 voor n  met n ≥ 2 en met startwaarden F0 = 1 en F1 = 1. n 2 a Bewijs met volledige inductie dat  i 0 Fi  Fn  1 voor n  met n ≥ 2. n b Bewijs met volledige inductie dat  i 0 F2i  F2n 1 voor n  .

4

Gegeven is de recurrentie an = –an–1 + 12an–2 + 4n voor n  met n ≥ 2 en met startwaarden a0 = 2 en a1 = 1. Bewijs met volledige inductie dat an = (–4)n – 3n + 2 · 4n voor alle n  .

5

We bewijzen als volgt met volledige inductie dat 5 n – 2n een zesvoud is voor alle n  . i Voor n = 0 geldt dat 5n – 2n = 0, wat een zesvoud is. ii Neem aan dat 5n – 2n een zesvoud is, dan moeten we bewijzen dat 5n+1 – 2n+1 een zesvoud is. Maar 5n+1 – 2n+1 = 5(5n – 2n) + 6 · 2n–1, en omdat 6 · 2n–1 een zesvoud is en 5n – 2n een zesvoud is (inductiehypothese), volgt er dat 5n+1 – 2n+1 een zesvoud is. Is dit bewijs correct? Motiveer uw antwoord.

Aanwijzingen en terugkoppelingen

AANWIJZINGEN LEEREENHEID 11

11.2

Neem als basis de elementen 1 en 3 en kijk naar opgave 11.1.

11.3

a Kijk naar de inductieve definitie van V in het voorbeeld voorafgaand aan opgave 11.2 en bedenk een basis met drie elementen. c Als basis kunnen we 0 en 1 nemen. De inductiestap heeft 2 regels.

11.6

b Laat bijvoorbeeld zien dat MIU uit MIIII is te verkrijgen. c De string MI, waar we mee starten, begint met een M. Laat zien dat we met de regels uit de inductiestap niet meer van deze begin-M afkomen.

11.7

a Vermenigvuldig de getallen in A eens met 2 of kijk naar de onderlinge verschillen. Valt u iets op?

11.8

b Breid de inductieve definitie van M in onderdeel a uit met ‘a optellen’.

11.11

d Ga uit van g(n) en pas, net als bij het afleiden van de formule voor n!, de recursie herhaald toe. Probeer een regelmaat te herkennen.

11.12

Definieer f door f(n) = an, dan is dit getal het aantal objecten in een driehoeksstapeling die uit n + 1 lagen bestaat. Hoeveel verschillen dan de driehoeksgetallen an en an–1? Haal hier de recursieve definitie van f uit.

11.16

d Ga uit van f(n) (of an) en pas herhaald de recursie toe. Probeer een regelmaat te herkennen: wat gebeurt er in de eerste stap, in de tweede stap en in de k-de stap?

11.18

Voer een in en neem als eerste regel in de BNF-definitie van ‘variabele’: ::=  . Welke mogelijkheden moeten we nu voor nemen?

11.25

Voor alle onderdelen geldt: bepaal de reden r van de meetkundige reeks en gebruik ofwel de methode waarmee formule 11.4 is afgeleid, ofwel gebruik formule 11.4 rechtstreeks. Voor onderdeel e geldt nog: schrijf 2i/3i als (2/3)i.

11.26

b Gebruik dat s6 = s5 + a · r6, vul de uitdrukking voor s5 in en breng onder één noemer.

11.29

b Kijk naar de onderlinge verschillen van de Dn. Haal hier de recursie uit. Om te laten zien dat deze juist is, nemen we aan dat het vlak in Dn–1 stukken is verdeeld met n – 1 lijnen. Hoe krijgen we nu, door het toevoegen van één nieuwe lijn, een maximaal aantal nieuwe delen van het vlak erbij (kijk naar de figuren)? c Pas herhaald de recursie toe. Er ontstaat een bekende som.

11.30

a Tel 1 op bij de berekende getallen Hn, dan ontstaat een bekende rij. b Pas herhaald de recursie toe en werk de resulaten om in de richting van het vermoeden.

AANWIJZINGEN LEEREENHEID 12

12.3

Breng 4n+1 + 2 in verband met 4n + 2 op vergelijkbare wijze als in de tekst (waar 5n+1 – 2n+1 in verband wordt gebracht met 5n – 2n).

12.6

Het inductiebewijs is vergelijkbaar met het inductiebewijs van de formule voor de som van de getallen 1 t/m n in het voorbeeld boven de opgaven.

12.7

b Het inductiebewijs is vergelijkbaar met het inductiebewijs van de formule voor de getallen Hn in het voorbeeld boven de opgaven.

12.10

Gebruik in het inductiebewijs dat 2(n + 1) + 1 = (2n + 1) + 2 en vervang hierin 2 door een geschikte term.

12.13

De string in de basis heeft een aantal I’s dat geen 3-voud is. Bewijs nu dat de regels in de inductiestap nooit een string kunnen doen ontstaan waarin het aantal I’s wel een 3-voud is. Voor de MU-puzzel moeten we ons afvragen wat het aantal I’s is in MU.

12.14

Zie het eerste voorbeeld van paragraaf 12.2.

12.15

Schrijf voor de inductiestap

n 1 i 1

12.16

n

Ai als (

i 1

Ai )  An

Zie het derde voorbeeld van paragraaf 12.2.

TERUGKOPPELING LEEREENHEID 11 1

Uitwerking van de opgaven

11.1

a Met 3 D (basis) kunnen we via de regel in de inductiestap het volgende element 2 · 3 = 6 in D maken. Zo doorgaand is steeds met de regel in de inductiestap het volgende element in D te maken: 6 D, dus 2 · 6 = 12 D, dus 2 · 12 = 24 D, enzovoort. Omdat D geen andere elementen bevat, zien we dat D = {3, 6, 12, 24, 48, ...}. b Laat O de verzameling van alle oneven getallen in zijn, dus O = {1, 3, 5, ...}. Een inductieve definitie van O is als volgt: i 1 O (basis) ii als x O, dan x + 2 O (inductiestap) iii O bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen (uitsluiting). c Een inductieve definitie van T is als volgt: i 1 T (basis) ii als x T, dan 2x T (inductiestap) iii T bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen (uitsluiting).

11.2

Een inductieve definitie van V = {1, 2, 3, 4, 6, 8, 12, 16, ...} ligt meer voor de hand als we een andere volgorde van de gegeven elementen kiezen: V = {1, 2, 4, 8, 16, ..., 3, 6, 12, ...}. Nu zijn hierin de verzamelingen T en D uit opgaven 11.1a en c te herkennen. Omdat deze beide ontstaan door steeds met 2 te vermenigvuldigen, is een inductieve definitie van V: i 1 V en 3 V (basis) ii als x V, dan 2x V (inductiestap) iii V bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen (uitsluiting).

11.3

a De verzameling V uit het voorbeeld voor opgave 11.2, is een deelverzameling van W. Verder geldt dat W – V = {2, 6, 10, ...}, waarin we de regelmaat ‘vier optellen’ herkennen die ook in V zit. Voor W is nu ook een inductieve definitie mogelijk met slechts één regel in de inductiestap (we laten uitsluiting weg): i 0 W, 1 W en 2 W (basis) ii als x W, dan x + 4 W (inductiestap). b Een inductieve definitie van is (we laten uitsluiting weg): i 0  (basis) ii als x  , dan x + 1  als x  , dan x – 1  (inductiestap). Er zijn vele andere mogelijkheden. Voor de tweede regel in ii kan bijvoorbeeld ook ‘als x  , dan –x  ’ genomen worden (met –0 = 0). c Een inductieve definitie van V = {0, 1, –3, 4, –4, 5, –7, 8, –8, ...} ligt meer voor de hand als we een andere volgorde van de gegeven elementen kiezen: V = {..., –8, –4, 0, 4, 8, ..., –7, –3, 1, 5, ...}. Beide rijtjes ontstaan door 4 op te tellen en af te trekken. Een inductieve definitie van V is dus (we laten uitsluiting weg): i 0 V en 1 V (basis) ii als x V, dan x + 4 V als x V, dan x – 4 V (inductiestap).

11.4

Een inductieve definitie van de verzameling L van strings die bestaan uit een aantal a’s gevolgd door evenveel b’s is (we laten uitsluiting weg): i ab L (basis) ii als x L, dan axb L (inductiestap). (Als u vindt dat ‘aantal’ ook 0 mag zijn, dan moeten we als basis van L de lege string nemen.)

11.5

a De uitdrukking ((4 – 2)/3) behoort tot R: omdat 4 en 2 tot R behoren (basis), geldt dat (4 – 2) R (inductiestap) en omdat ook 3 R (basis), volgt dan weer via de inductiestap dat ((4 – 2)/3) R. b Omdat 2 en 3 tot R behoren (basis), geldt dat (2 · 3) R (inductiestap) en dus ook (–(2 · 3)) R (inductiestap). Maar in de uitdrukking –(2 · 3) ontbreken de buitenste haakjes, die altijd om een uitdrukking van de vorm –x moeten staan, dus –(2 · 3) R. c Omdat om –1 geen haakjes staan, volgt net als in onderdeel b dat (–1 + (2/113)) R. d De uitdrukking ((2/113) – 1) behoort tot R: omdat 2 en 113 tot R behoren (basis), geldt dat (2/113) R (inductiestap) en omdat ook 1 R (basis), volgt dan weer via de inductiestap dat ((2/113) – 1) R. Merk op dat rekenkundig gezien ((2/113) – 1) en (–1 + (2/113)) uit onderdeel c hetzelfde zijn, maar niet als expressies in (de formele taal) R. e De uitdrukking (–(3 · ((4 + 2)/87))) behoort tot R: omdat 4 en 2 tot R behoren (basis), geldt dat (4 + 2) R (inductiestap); omdat (4 + 2) R en 87 R (basis), volgt dat ((4 + 2)/87) R (inductiestap); omdat ((4 + 2)/87) R en 3 R (basis), volgt dat (3 · ((4 + 2)/87)) R (inductiestap); omdat (3 · ((4 + 2)/87)) R, volgt ten slotte uit de inductiestap dat (–(3 · ((4 + 2)/87))) R.

11.6

a Voor het gemak noemen we de vier regels uit de inductiestap even 1, 2, 3 en 4. Omdat MI L (basis) volgt dat MIU L (pas 1 toe met x = M). Omdat MI L (basis), volgt dat MII L (2 met x = I). Omdat MIU L (zie boven), volgt dat MIUIU L (2 met x = IU). Omdat MII L (zie boven), volgt dat MIIII L (2 met x = II). Omdat MIIII L (zie boven), volgt dat MUI L (3 met x = M, y = I). b Er kan meer dan één manier zijn. Zo volgt uit MIIII L (zie boven) en regel 3 met y leeg en x = MI dat MIU L, wat we al op een andere manier hadden gevonden. c De verzameling L wordt opgebouwd uit de string MI, die met een M begint, via de regels uit de inductiestap. Is het nu mogelijk dat door toepassing van één van die regels we een M aan het begin van een string kwijtraken? Als we kunnen aantonen dat dit niet lukt, dan beginnen alle strings in L met een M, omdat de startwaarde MI met een M begint. We lopen nu de vier regels uit de inductiestap één voor één af om na te gaan of we een begin-M kunnen kwijtraken. Als we 1 toepassen, dan blijft de beginletter van een string behouden: als xI met een M begint, dan begint xIU ook met een M. In 2 krijgen we uit Mx de string Mxx, dus een M aan het begin raken we zeker niet kwijt. Als in 3 de string xIIIy met een M begint, dan begint ook xUy met een M. Ten slotte, als in 4 de string xUUy met een M begint, dan begint ook xy met een M. Geen van de regels 1, 2, 3 of 4 zal dus een M aan het begin kwijt raken, terwijl we wel met MI starten. Dus alle strings in L beginnen met een M.

d Hoeveel nieuwe strings we ook genereren (bijvoorbeeld met een computerprogramma), nooit lijken we MU te pakken te krijgen. Het vermoeden ontstaat dat MU L. In de volgende leereenheid zullen we dit vermoeden bewijzen. 11.7

a De getallen in A schelen bijna een factor 2, namelijk op een verschil van 1 na: 3 = 2 · 2 – 1, 5 = 2 · 3 – 1, 9 = 2 · 5 – 1, 17 = 2 · 9 – 1 (dit is ook te ontdekken door naar de onderlinge verschillen te kijken: dat zijn steeds hogere machten van 2 en nemen dus met een factor 2 toe). Dit leidt tot de volgende inductieve definitie van A (we laten uitsluiting weg): i 2 A (basis) ii als x A, dan 2x – 1 A (inductiestap). b De getallen in D schelen steeds een factor 3, wat de volgende inductieve definitie van D geeft (we laten uitsluiting weg): i 1 D (basis) ii als x D, dan 3x D als x D, dan x/3 D (inductiestap).

11.8

a De elementen in M ontstaan uit a door steeds met r te vermenigvuldigen. Een inductieve definitie van M is (we laten uitsluiting weg): i a M (basis) ii als x M, dan xr M (inductiestap). b De elementen in N ontstaan uit a door steeds met r te vermenigvuldigen en hier dan a bij op te tellen. Een inductieve definitie van N is (we laten uitsluiting weg): i a N (basis) ii als x N, dan a + xr N (inductiestap).

11.9

Laat V de verzameling zijn van alle variabelen in deze programmeertaal. Omdat een variabele moet beginnen met een letter uit N, nemen we N als basis. Daarna mogen letters uit N, cijfers uit C en de tekens @, #, $ en % worden toegevoegd (voor N en C zie de opgave). Dit zullen dus de regels uit de inductiestap worden. Een inductieve definitie van V is dus (we laten uitsluiting weg): i iedere  N behoort tot V (basis) ii als  V, dan  V voor iedere  N of  C als  V, dan behoren ook @, #, $ en % tot V (inductiestap). De twee regels uit de inductiestap kunnen we ook combineren in één regel: als  V, dan  V voor iedere  N of  C of  {@, #, $, %}. Voorbeelden van variabelen zijn: a, x, variabele, var12plus33@nl, z%%#$$$u00.

11.10

a Omdat f(4) = 24, volgt uit regel ii met n = 4 dat f(5) = 5f(4) = 5 · 24, ofwel f(5) = 120. Uit regel ii met n = 5 volgt dan dat f(6) = 6f(5) = 6 · 120, ofwel f(6) = 720. b Bij f hoort de rij f(0), f(1), f(2), ..., waarvan de eerste 7 termen gegeven worden door 1, 1, 2, 6, 24, 120, 720.

11.11

a Omdat g(0) = 3, volgt uit g(n) = 3g(n – 1) met n = 1 dat g(1) = 3g(0) = 3 · 3 = 9. Nu volgt uit g(n) = 3g(n – 1) met n = 2 dat g(2) = 3g(1) = 3 · 9 = 27 en net zo dat g(3) = 3g(2) = 3 · 27 = 81. b Bij g hoort de rij g(0), g(1), g(2), ..., waarvan de eerste 5 termen gegeven worden door 3, 9, 27, 81, 243. Iedere volgende term in deze rij ontstaat uit de vorige door met 3 te vermenigvuldigen. c In het volgende programma wordt n  door de gebruiker opgegeven. Als de gebruiker n = 0 opgeeft, dan stopt het programma meteen na de toekenningen g := 3 en k := 1 en dus heeft g inderdaad de waarde g(0). Geeft de gebruiker een n  op met n ≥ 1, dan wordt g = 3 steeds met 3 vermengvuldigd, wat precies in overeenstemming is met de recursieve definitie van g(n). Als k de waarde n heeft bereikt en het programma stopt, dan heeft g dus de waarde g(n). lees maak zolang

n g := 3 k := 1 k ≤ n doe g := 3 * g maak k := k + 1

d Volgens de recursie geldt voor iedere gehele n met n ≥ 1 dat g(n) = 3g(n – 1). We kunnen deze recursie dan ook voor n – 1 toepassen, met andere woorden: g(n – 1) = 3g(n – 2) (voor n ≥ 2). Uit g(n) = 3g(n – 1) en g(n – 1) = 3g(n – 2) volgt dan dat g(n) = 3(3g(n – 2)) = 32g(n – 2). Nu kunnen we opnieuw de recursie toepassen voor n – 2 en volgt er dat g(n – 2) = 3g(n – 3) (voor n ≥ 3). Uit g(n) = 32g(n – 2) en g(n – 2) = 3g(n – 3) volgt dan dat g(n) = 32(3g(n – 3)) = 33g(n – 3). We zien dat er in iedere stap een macht van 3 bijkomt. Dit proces stopt als we na n stappen bij g(n – n) = g(0) zijn aangekomen. Er zijn dan n machten van 3 ontstaan: g(n) = 3ng(n – n) = 3ng(0). Omdat g(0) = 3, volgt de expliciete formule: g(n) = 3n+1. 11.12

Definieer de functie f van naar door f(n) = an, dan is de rij a0 = 1, a1 = 3, a2 = 6, a3 = 10, ... hetzelfde als de rij functiewaarden f(0), f(1), f(2), f(3), ... Het getal f(n) = an geeft het aantal objecten (bijvoorbeeld blikken) aan dat nodig is om een driehoeksstapeling te maken die uit n + 1 lagen bestaat, immers, a0 = 1 is het aantal objecten in een driehoek met 1 laag, a1 = 3 is het aantal objecten in een driehoek met 2 lagen, a2 = 6 is het aantal objecten in een driehoek met 3 lagen, enzovoort. Uit de introductie weten we al dat de onderlinge verschillen tussen de driehoeksgetallen steeds één groter worden: a1 – a0 = 3 – 1 = 2, a2 – a1 = 6 – 3 = 3, a3 – a2 = 10 – 6 = 4 en in het algemeen an – an–1 = n + 1 omdat het volgende driehoeksgetal an uit het vorige an–1 ontstaat door een nieuwe laag met n + 1 objecten toe te voegen aan de driehoek. Hiermee hebben we gevonden dat an = an–1 + n + 1, ofwel f(n) = f(n – 1) + n + 1 voor n  +. De startwaarde is a0 = 1, ofwel f(0) = 1.

11.13

Er geldt dat

i5 0 i! = 0! + 1! + 2! + 3! + 4! + 5! = 1 + 1 + 2 + 6 + 24 + 120 = 154 Als we de recursieve definitie (herhaald) zouden gebruiken, dan komt het bepalen van deze som er als volgt uit te zien:

 i0 i!   i0 i!  5!   i0 i!  4!  5!   i0 i!  3!  4!  5! 5

4

3

2

  i0 i!  2!  3!  4!  5!   i0 i!  1!  2!  3!  4!  5! 1

0

 0!  1!  2!  3!  4!  5! wat dezelfde uitdrukking als hiervoor oplevert. Maar het is ongebruikelijk om voor sommen (en straks ook producten) de berekening zo uitgebreid op te schrijven. We zullen dit dan ook voortaan niet meer zo doen. In het bijzonder bepalen we de andere opgaven op de gebruikelijke manier:

6k 3 2 k = 23 + 24 + 25 + 26 = 8 + 16 + 32 + 64 = 120 i3 21/( 2i  1) = –1/3 – 1 + 1 + 1/3 + 1/5 + 1/7 = 1/5 + 1/7 = 12/35 i2 2 i2 = 22 = 4 (deze som heeft maar één term, namelijk voor i = 2) 11.14

 4i 0 (i  1) 2 = 12 · 22 · 32 · 42 · 52 = (5!)2 = 1202 = 14400

a

 3i 0 x i = x0x1x2x3 = x6  ni 0 (i  1) = 1 · 2 · 3 · ... · n · (n + 1) = (n + 1)! b De recursieve definitie van het product lijkt op die voor de som: 0

n

n1

i0

i0

i0

 ai  a0 en  ai  an   ai

voor n  +

Nemen we hierin ai = i + 1 voor i = 0, 1, ..., n, dan volgt dat 0

n

n1

i0

i0

i0

 (i  1)  1 en  (i  1)  (n  1)  (i  1) voor n  + n en omdat  i 0 (i  1) = (n + 1)! voor n  (zie onderdeel a) staat hier dus dat 1! = 1 en (n + 1)! = (n + 1) · n! voor n  +. Overigens is de startwaarde nu 1! = 1 en niet 0! = 1. Als we deze recursieve definitie gebruiken, dan moeten we dus 0! = 1 apart introduceren.

c Een recursieve definitie van het product van as, as+1, as+2 t/m an (met n, s  en n ≥ s) is: s

n

n1

is

is

is

 ai  as en  ai  an   ai

voor n  s  1

1 1 d  3i 1 1/( i2  1)  12  11  12  15  10  200 20 Er geldt dat  k  5 k 2 = 0 omdat k = 0 een factor 0 in het product geeft. In  7i  7 x i = x–7x–6...x–1x0x1...x6x7 nemen we voor n = 1, 2, ..., 7 steeds x–n en xn samen tot x–n · xn = 1. Omdat ook x0 = 1, staat er dan een product met 8 keer een 1, dus  7i  7 x i = 1.

11.15

We laten in verkorte notatie zien hoe het getal 2561 verkregen kan worden met behulp van de gegeven recursieve definitie van :    2  25  256  2561. Het getal +2561 krijgen we dan als volgt:   +  verder als voor 2561.

11.16

a De eerste zes termen zijn a0 = 1, a1 = a0 = 1, a2 = 3a1 = 3, a3 = 5a2 = 15, a4 = 7a3 = 105 en a5 = 9a4 = 945. b Definieer de functie f:  door f(n) = an, ofwel f(0) = 1 en f(n) = (2n – 1)f(n – 1) voor n  +. c De variabele a in het nu volgende programma heeft de waarde an voor een gegeven waarde van n  , immers, we starten met a = 1 en volgen in de lus precies de recursieve definitie van de rij. lees maak zolang

n a := 1 k := 1 k ≤ n doe a := (2 * k – 1)*a maak k := k + 1

d We gaan uit van f(n) (of an) en passen de recursie herhaald toe. De eerste stap is de recursie zelf, dus f(n) = (2n – 1)f(n – 1). De tweede stap is het opnieuw toepassen van de recursie, maar nu voor n – 1, dus f(n – 1) = (2(n – 1) – 1)f(n – 2) = (2n – 3) f(n – 2), en samen met de eerste stap levert dit f(n) = (2n – 1)(2n – 3)f(n – 2) op. Opnieuw de recursie toepassen geeft dat f(n – 2) = (2(n – 2) – 1)f(n – 3), dus f(n – 2) = (2n – 5)f(n – 3). Samen met de eerste twee stappen hebben we nu dat f(n) = (2n – 1)(2n – 3)(2n – 5)f(n – 3). Zo doorgaand zien we dat er in de k-de stap een factor (2n – (2k – 1)) bijkomt. Dit proces stopt bij (2n – (2n –1))f(n – n) = 1 · f(0), dus: f(n) = (2n – 1)(2n – 3)(2n – 5) · ... · 5 · 3 · 1 · f(0). Omdat f(0) = 1, volgt de expliciete formule: n f(n) = (2n – 1)(2n – 3)(2n – 5) · ... · 5 · 3 · 1 =  k  1 (2k  1) .

11.17

n Een recursieve definitie van i  0 A i , die het gebruik van ‘...’ vermijdt, is als volgt (vergelijk weer met de definitie van som):

0 i 0

Ai  A0

n

en i 0

Ai  An 

n 1 i 0

Ai

voor n 

+

We kunnen hetzelfde doen voor A0  A1  ...  An: 0 i 0

11.18

Ai  A0

n

en i 0

Ai  An 

n 1 i 0

Ai

voor n 

+

De variabele uit opgave 11.9 moet beginnen met een letter uit N, de verzameling van letters uit het Nederlandse alfabet. We kunnen het bij één letter laten of nog karakters toevoegen, waarbij we de keuze uit een aantal mogelijkheden hebben. Om dit weer te geven, voeren we een ‘hulp’ in en nemen als eerste regel in de BNF-definitie van variabele: ::=  We kunnen nu na het toevoegen van één extra karakter stoppen of daarna doorgaan met opnieuw een karakter. Voor het karakter zijn er drie mogelijkheden. De tweede regel wordt daarom: ::=      Door dit te herhalen is het aantal karakters in de rij willekeurig groot te maken. Ten slotte sommen we de letters, cijfers en symbolen op: ::= a  b  c  d ...  x  y  z ::= 0  1  2  3  ...  8  9 ::= @  #  $  % De variabele z%%u8 is als volgt te verkrijgen:   z  z%  z%%  z%%u  z%%u8

11.19

a De eerste zes termen zijn 3, 3 + 7 = 10, 10 + 7 =17, 17 + 7 = 24, 24 + 7 = 31 en 31 + 7 = 38. In dit rijtje is 3 de eerste term, 3 + 1 · 7 de tweede term, 3 + 2 · 7 de derde term, enzovoort. Dus 3 + 99 · 7 = 696 is de 100-ste term. b De eerste term is a, de tweede term is a + 1 · v, de derde term is a + 2 · v, de vierde term is a + 3 · v, enzovoort. De (n + 1)-ste term is dus a + n · v. Dit is ook af te leiden door de recursie herhaald toe te passen: an = an–1 + v = an–2 + 2v = an–3 + 3v = ... = a0 + nv = a + nv. c De eerste term is 4, het verschil is 6, dus volgens onderdeel b is de 237-ste term gelijk aan a + 236 · v = 4 + 236 · 6 = 1420.

11.20

We doen dit net als in voorbeeld 11.2: 1 + 2 + 3 + 999 + 998 + 997 +

... + 997 + 998 + 999 ... + 3 + 2 + 1

1000 + 1000 + 1000 +

... + 1000 + 1000 + 1000

+

In de laatste regel staat 999 keer 1000. Twee maal de gevraagde som is dus 999 · 1000, zodat de gevraagde som gelijk is aan 999 · 500 = 499 500. 11.21

a sn sn

Met de methode uit voorbeeld 11.2 krijgen we: = =

a + (a + v) + ... + (a + (n – 1)v) + (a + nv) + (a + (n – 1)v) + ... + (a + v) +

(a + nv) a +

2sn = (2a + nv) +

(2a + nv) + ... +

(2a + nv) +

(2a + nv)

In de laatste regel staat n + 1 keer het getal 2a + nv, dus 2sn = (n + 1)(2a + nv), ofwel sn = (n + 1)(2a + nv)/2. b De som sn = a + (a + v) + (a + 2v) + ... + (a + (n – 1)v) + (a + nv) bevat n + 1 keer de term a, dus sn = (n + 1)a + (v + 2v + ... + (n – 1)v + nv), wat ook te schrijven is als sn = (n + 1)a + v(1 + 2 + ... + (n – 1) + n). Uit formule 11.2 volgt dan dat sn = (n + 1)a + v(n(n + 1)/2). Haal hier (n + 1)/2 buiten haakjes, dan zien we dat sn = (n + 1)(2a + nv)/2, wat formule 11.3 is. c Omdat 5 + 9 + ... + 113 een rekenkundige rij is met v = 4, schrijven we eerst 113 = 5 + 108 = 5 + 27 · 4, wat betekent dat de som 28 termen bevat. Nu kunnen we natuurlijk formule 11.3 toepassen met a = 5, v = 4 en n = 27, maar liever gebruiken we de methode van voorbeeld 11.2, zodat we 28 keer de helft van 5 + 113 moeten nemen, dus 5 + 9 + ... + 113 = 14 · 118 = 1652. In de rekenkundige rij 7 + 4 + 1 – 2 ... – 44 geldt v = –3 en omdat –44 = 7 + (–51) = 7 + 17 · (–3) volgt dat de som 18 termen bevat. De som is dus 18 keer de helft van 7 + (–44), ofwel 9 · (–37) = –333. d Omdat sn een som is, is dit een bijzonder geval van de recursieve definitie van een som: s0 = a en sn = sn–1 + (a + nv) voor n  +. Immers, s0  0i  0(a  iv )  a en sn   ni 0 (a  iv) schrijven we als de som van de n 1 eerste n – 1 termen  i 0 (a  iv)  sn– 1 en de term met i = n, wat a + nv is. 11.22

In het eerste jaar staat er 500 op de rekening. In het tweede jaar staat er 500 + 0,03 · 500 = 1,03 · 500 = 515 op. In het derde jaar is dit 1,03 · 515 = 530,45, ofwel (1,03) 2 · 500. In het vierde jaar is dit 1,03 · 583,20 = 546,3635, ofwel (1,03) 3 · 500. Enzovoort. Zo ontstaat de rij 500, 515, 530,45, 546,3635, ..., ofwel 500, 1,03 · 500, (1,03)2 · 500, (1,03)3 · 500, ..., waarbij ieder volgend getal uit het vorige ontstaat door met 1,03 te vermenigvuldigen.

11.23

a De eerste zes termen zijn 3, 3 · 4 = 12, 12 · 4 = 48, 48 · 4 = 192, 192 · 4 = 768 en 768 · 4 = 3072 respectievelijk √2, √2/2, √2/4, √2/8, √2/16 en √2/32.

b De eerste term is a, de tweede term is a · r, de derde term is a · r2, de vierde term is a · r3, enzovoort. De (n + 1)-ste term is dus a · rn. Dit is ook af te leiden door de recursie herhaald toe te passen: an = ran–1 = r2an–2 = r3an–3 = ... = rna0 = arn. c De eerste term is 4, de reden is 3, dus volgens onderdeel b is de 11-de term gelijk aan a · r10 = 4 · 310 = 4 · 59 049 = 236 196. 11.24

a De ervaring leert dat dit soort bedragen meestal te laag wordt ingeschat, zoals 40 000 tot 70 000. Zie verder opgave 11.25a. b In het eerste jaar is het kapitaal 500. In het tweede jaar is het 500 + 1,05 · 500 = 500 + 525 = 1025. In het derde jaar is het 500 + 1,05 · 1025 = 1576,25. In het vierde jaar is het 500 + 1,05 · 1576,25 = 2155,0625. Enzovoort. Deze bedragen zijn ook te schrijven als 500, 500 + 1,05 · 500, 500 + 1,05 · 500 + (1,05) 2 · 500 en 500 + 1,05 · 500 + (1,05)2 · 500 + (1,05)3 · 500, ..., wat steeds eindige meetkundige reeksen zijn met eerste term 500 en reden 1,05. c Bij de eerste rij uit opgave 11.23a hoort de meetkundige reeks 3 + 12 + 48 + 192 + 768 + 3072. Bij de tweede rij hoort de meetkundige reeks √2 + √2/2 + √2/4 + √2/8 + √2/16 + √2/32.

11.25

a Na afloop van het eerste jaar wordt het kapitaal gegeven door 1000 + (1,1) · 1000. Na afloop van het tweede jaar wordt dit 1000 + (1,1) · 1000 + (1,1)2 · 1000. (Zie voorbeeld 11.4.) Enzovoort. Na afloop van het 25-ste jaar wordt het kapitaal gegeven door de eindige meetkundige reeks 1000 + 1,1 · 1000 + (1,1)2 · 1000 + ... + (1,1)25 · 1000, waarvan we de som even s noemen. Nu kunnen we natuurlijk formule 11.4 toepassen met a = 1000, r = 1,1 en n = 25, maar liever gebruiken we de methode zoals uitgelegd in de tekst. Vermenigvuldig dus de reeks met de reden 1,1 en trek het resultaat af van de reeks, dan volgt dat s – 1,1 · s = 1000 – (1,1)26 · 1000. Deel nu door 1 – 1,1, dan volgt dat

s

1000(1  (1.1) 26 ) 1126  100001  26   10 221126  10 4  10  1  1.1

Afgerond op hele euro’s is dit 109 182. b Dit is een meetkundige reeks met eerste term 2, reden 2 en laatste term 2048 = 2 · 210, dus volgt (als in onderdeel a of rechtstreeks via formule 11.4) dat de som gelijk is aan 2(1 – 211)/(1 – 2) = 2(211 – 1) = 212 – 2 = 4094. c Dit is een meetkundige reeks met eerste term 3, reden 1/3 en laatste term 1/729 = 3 · (1/3)7, dus volgt dat de som gelijk is aan

3(1  ( 13 ) 8 ) 9  1 9 1 6560 364  1  8     4 1  1 3 2 3 2 2 729 2 729 729 d Dit is een meetkundige reeks met eerste term 1, reden –1/2 en laatste term –1/2048 = 1 · (–1/2)11, dus volgt dat de som gelijk is aan

1(1  ( 21 ) 12 ) 2  1 2 1 4095 1365  1  12      1  ( 21 ) 3 2  3 3 2048 3 2048 2048

e

Omdat n



i 3

     

n 2i  i 3 i 3

2 3

i

2 3

3

2 3

4

 ... 

 2 3

n

hebben we hier een meetkundige reeks met eerste term (2/3) 3, reden 2/3 en laatste term (2/3)n = (2/3)3(2/3)n–3, dus volgt dat de som gelijk is aan

  2 3

3

 1   1

  2 3

2 3

n –2

    3

 2 3

3

 2 n –2  8 8  2 n –2 8 2 n 1  – n  1  n –2    n –2 9 3 3   9 93

Let er goed op dat het aantal termen in deze reeks gelijk aan n – 2 is. 11.26

a Omdat sn een som is, is dit een bijzonder geval van de recursieve definitie van een som: s0 = a en sn = sn–1 + a · rn voor n  +. Immers, n n 1 i i s0  0i  0 ari  a en sn   i 0 ar schrijven we als  i 0 ar  sn–1 en de n term met i = n, wat ar is. b Uit de recursie in onderdeel a met n = 6 volgt dat s6 = s5 + a · r6. Omdat we mogen aannemen dat s5 = a(1 – r6)/(1 – r), volgt er dat (breng eerst onder één noemer en werk vervolgens de teller uit, waarbij a buiten haakjes gehaald wordt):

s6  a  r 6 

a (1  r 6 ) ar 6 (1  r )  a (1  r 6 ) a (1  r 7 )   1 r 1 r 1 r

wat we moesten aantonen. 11.27

Na vijf maanden zijn er de paren uit de vierde maand, wat er F4 = 5 zijn, plus de nakomelingen van ieder van de paren uit twee maanden eerder, dus uit de derde maand, wat er F3 = 3 zijn. Dus F5 = 5 + 3 = 8 = F4 + F3. Na zes maanden zijn er de paren uit de vijfde maand, wat er F5 = 8 zijn, plus de nakomelingen van ieder van de paren uit twee maanden eerder, dus uit de vierde maand, wat er F4 = 5 zijn. Dus F6 = 8 + 5 = 13 = F5 + F4. De regelmaat is hierin goed te zien: steeds geldt dat Fn = Fn–1 + Fn–2.

11.28

a De eerste 10 termen zijn 1, 1, 2, 3, 5, 8, 13, 21, 34 en 55. Een getal in deze rij is steeds de som van de twee getallen direct eraan voorafgaand. b In de fictieve programmeertaal uit paragraaf 11.2.1 kunnen de eerste n termen van de rij van Fibonacci als volgt berekend worden. (De gebruiker geeft een n  op.) lees maak

zolang

n F(0) := 1 F(1) := 1 k := 2 k ≤ n doe F(k) := F(k – 1) + F(k – 2) maak k := k + 1

Als het programma stopt, zijn in de variabelen F(0) t/m F(n) de eerste n Fibonacci-getallen opgeslagen.

11.29

a In figuur 11.2 is te zien dat D1 = 2, D2 = 4, D3 = 7 en D4 = 11. Er geldt dat D0 = 1, omdat het vlak zelf uit 1 deel bestaat.

FIGUUR 11.2

Het vlak in een maximaal aantal delen verdelen

b Als we naar de onderlinge verschillen kijken, dan zien we dat deze steeds met 1 toenemen: D1 – D0 = 1, D2 – D1 = 2, D3 – D2 = 3, D4 – D3 = 4. We vermoeden dan dat Dn – Dn–1 = n, wat de recursie Dn = Dn–1 + n geeft. Dit is de juiste recurrentie. Stel maar eens dat we het vlak met n – 1 lijnen in maximaal Dn–1 delen hebben verdeeld. Trek dan zo de n-de lijn dat deze ieder van de n – 1 lijnen snijdt (dat kan altijd door de n-de lijn niet evenwijdig aan de al aanwezige n – 1 lijnen te trekken). Hierdoor ontstaan precies het maximale aantal van n extra delen van het vlak. Dus Dn = Dn–1 + n. c Pas herhaald de recursie toe: Dn = Dn–1 + n = (Dn–2 + (n – 1)) + n = (Dn–3 + (n – 2)) + (n – 1) + n = (Dn–4 + (n – 3)) + (n – 2) + (n – 1) + n. Dit proces stopt bij D0: Dn = D0 + 1 + 2 + ... + (n – 3) + (n – 2) + (n – 1) + n. Het rechterlid bevat de bekende rekenkundige rij die de driehoeksgetallen n(n + 1)/2 geeft (zie formule 11.2) en omdat D0 = 1, volgt er dat Dn = 1 + n(n + 1)/2. 11.30

a De eerste acht termen zijn H0 = 0, H1 = 2H0 + 1 = 1, H2 = 2H1 + 1 = 3, H3 = 7, H4 = 15, H5 = 31, H6 = 63 en H7 = 127. Als we bij deze getallen 1 optellen, dan ontstaat de rij 1, 2, 4, 8, 16, 32, 64 en 128, wat precies de opeenvolgende machten van 2 zijn. We vermoeden dus dat Hn = 2n – 1. b Pas herhaald de recursie toe: Hn = 2Hn–1 + 1 = 2(2Hn–2 + 1) + 1 = 22Hn–2 + 3 en vanwege het vermoeden in onderdeel a schrijven we dit als 22Hn–2 + 22 – 1. Pas weer de recursie toe, dan volgt dat Hn = 22Hn–2 + 22 –1 = 22(2Hn–3 + 1) + 22 –1 = 23Hn–3 + 22 + 22 – 1, ofwel Hn = 23Hn–3 + 23 – 1. Pas weer de recursie toe: Hn = 23Hn–3 + 23 –1 = 23(2Hn–4 + 1) + 23 –1 = 24Hn–4 + 23 + 23 – 1, ofwel Hn = 24Hn–4 + 24 – 1. Dit proces stopt bij H0: Hn = 2nH0 + 2n – 1. Maar H0 = 0, dus is bewezen dat Hn = 2n – 1. 2

1

Uitwerking van de zelftoets

a Omdat 2 E (basis), volgt dat 2(2 + 1)/2 = 3 E (inductiestap). Door herhaald de inductiestap toe te passen, volgt dat 3(3 + 1)/2 = 6 E, 6(6 + 1)/2 = 21 E en 21(21 + 1)/2 = 231 E. b In de noemer zien we een vermenigvuldiging met 1/2 optreden, maar dat is niet voldoende: het verschil is steeds 1. Een inductieve definitie van V = {0, 1, 3/2, 7/4, 15/8, ...} is dus:

i 0 V (basis) ii als x V, dan 1 + x/2 V (inductiestap) iii V bevat geen andere elementen dan die door toepassing van i en ii kunnen worden verkregen (uitsluiting). 2

3

n a Noem even S(n) =  k  1 (2k  1) , dan geldt dat S(1) = 1, S(2) = 1 + 3 = 4, S(3) = 1 + 3 + 5 = 4 + 5 = 9, S(4) = 1 + 3 + 5 + 7 = 9 + 7 = 16 en we gokken nu n dat S(n) =  k  1 (2k  1) = n2 voor alle n  +. n b De som S(n) =  k  1 (2k  1) = 1 + 3 + 5 + ... + (2n – 3) + (2n – 1) is een eindige rekenkundige reeks met eerste term a = 1 en verschil v = 2. Door de reeks om te draaien en bij zichzelf op te tellen, volgt er dat 2S(n) = 2n + 2n + 2n + ... + 2n + 2n, waarbij deze som uit n termen bestaat. Dus n 2S(n) = n · 2n = 2n2, ofwel  k  1 (2k  1) = n2, wat in overeenstemming met onze gok uit onderdeel a is. (Om de eindige rekenkundige reeks uit te rekenen, kunnen we natuurlijk ook formule 11.3 toepassen.) c Er geldt dat a1 = 1, a2 = a1 + 3 = 4, a3 = a2 + 5 = 9, a4 = a3 + 7 = 16, wat precies dezelfde waarden zijn als in onderdeel a. Dit klopt ook, want n noem an =  k  1 (2k  1) , dan geldt dat an = an–1 + 2n – 1 voor n  met n n ≥ 2 en a1 = 1, met andere woorden  k  1 (2k  1) voldoet precies aan de gegeven recurrentie en heeft de juiste startwaarde. Uit onderdeel b volgt dan dat an = n2.

a Dit is een rekenkundige reeks met eerste term –1/7 en verschil 5/7. Omdat 99/7 = –1/7 + 20 · (5/7), volgt dat de reeks 21 termen heeft. Met de bekende methode voor rekenkundige reeksen (draai om en tel bij zichzelf op; zie eventueel voorbeeld 11.2) volgt dan dat de som gelijk is aan 21 keer de helft van –1/7 + 99/7, dus aan 21 · 98/14 = 147. (We kunnen ook formule 11.3 gebruiken.) b Haal eerst 1/5 uit de reeks, dan houden we de meetkundige reeks over met eerste term 112, reden 11 en laatste term 11n (let op dat er dus n – 1 termen zijn). Noem de som s, vermenigvuldig deze met 11 en trek dit van s af, dan volgt dat (1 – 11)s = 112 – 11n+1, ofwel

s

11n 1 – 112 121 n–1  (11 – 1) 10 10

Het antwoord is dus 121(11n–1 – 1)/50. (We kunnen ook formule 11.4 gebruiken.) c Dit is een rekenkundige reeks met eerste term –3, verschil 5 en n + 1 termen. De som is dus gelijk aan n + 1 keer de helft van –3 + (5n – 3), ofwel aan (n + 1)(5n – 6)/2. 4

We gaan eerst proberen om Fn uit te drukken in Fn–2 en Fn–4. Uit de recurrentie Fn = Fn–1 + Fn–2 volgt Fn–1 = Fn–2 + Fn–3. Invullen van deze uitdrukking voor Fn–1 in de Fibonacci-recurrentie geeft Fn = 2Fn–2 + Fn–3. Nu moeten we alleen Fn–3 nog uitdrukken in Fn–2 en Fn–4. Dat kan met de betrekking Fn–2 = Fn–3 + Fn–4, dus Fn–3 = Fn–2 – Fn–4. Hieruit volgt dat Fn = 2Fn–2 + Fn–3 = 2Fn–2 + Fn–2 – Fn–4 = 3Fn–2 – Fn–4. We zien nu hoe de termen met oneven indices van de Fibonacci-rij samenhangen: elke term is gelijk aan driemaal de vorige min de voorganger van de vorige: Gn = 3Gn–1 – Gn–2 voor n N én n ≥ 2. De startwaarden van de rij Gn zijn de eerste en derde term van de Fibonaccirij: G0 = 1 en G1 = 2.

TERUGKOPPELING LEEREENHEID 12 1

Uitwerking van de opgaven

12.1

We berekenen voor n = 0 t/m 15 de getallen n2 – n + 41, wat allemaal priemgetallen blijken te zijn: 41, 41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251 (en het gaat zo nog even door met priemgetallen!). Toch is n2 – n + 41 niet voor iedere n  een priemgetal, immers, voor bijvoorbeeld n = 41 staat er 412 – 41 + 41 = 412.

12.2

a Er geldt dat 58 – 28 = 5 · (57 – 27) + 3 · 27, en omdat 57 – 27 een drievoud is (zie de tekst) en 3 · 27 een drievoud is, volgt dat 58 – 28 een drievoud is. Er geldt dat 59 – 29 = 5 · (58 – 28) + 3 · 28, en omdat 58 – 28 een drievoud is (net bewezen) en 3 · 28 een drievoud is, is ook 59 – 29 een drievoud. b Er geldt dat 5322 – 2322 = 5 · (5321 – 2321) + 3 · 2321, en omdat 5321 – 2321 een drievoud is (mogen we volgens de opgave aannemen) en 3 · 2 321 een drievoud is, volgt dat 5322 – 2322 een drievoud is.

12.3

Voor n = 0 geldt dat 4n + 2 = 1 + 2 = 3 een drievoud is. Evenzo is 4 1 + 2 = 4 + 2 = 6 een drievoud en 42 + 2 = 16 + 2 = 18 een drievoud. Laat nu n  willekeurig zijn en neem aan dat 4n + 2 een drievoud is. Om te bewijzen dat dan ook 4n+1 + 2 een drievoud is, brengen we dit in verband met 4n + 2 (zoals we in formule 12.1 een verband legden tussen 5n+1 – 2n+1 en 5n – 2n): 4n+1 + 2 = 4 · 4n + 2 = 4 · (4n + 2) – 4 · 2 + 2 = 4 · (4n + 2) – 3 · 2. Merk op hoe we hier 4 · 2 toevoegen (en ter compensatie weer aftrekken) om de gewenste term 4n + 2 te krijgen. Omdat nu 4n + 2 een drievoud is (dat namen we aan) en 3 · 2 een drievoud is, volgt dat 4 n+1 + 2 een drievoud is. Overigens is er meer dan één manier om een verband te leggen tussen 4n+1 + 2 en 4n + 2. We kunnen bijvoorbeeld ook 4n+1 + 2 = 4 · 4n + 2 schrijven als 3 · 4n + (4n + 2). Omdat 4n + 2 een drievoud is (aanname) en 3 · 4n een drievoud is, volgt er ook op deze wijze dat 4 n+1 + 2 een drievoud is. We zullen nog wat vaker laten zien dat er meer dan één manier is om het gewenste verband te krijgen.

12.4

Er is nu nog niet bewezen dat 5n + 3 deelbaar is door 12 voor alle n  , omdat we eerst het proces op gang moeten brengen door voor n = 0 te bewijzen dat 5n + 3 deelbaar is door 12. In dit geval is dat zelfs niet waar: 50 + 3 = 4 is niet deelbaar door 12.

12.5

We bewijzen met volledige inductie dat 8 n – 3n een vijfvoud is voor alle n . i Voor n = 0 geldt dat 8n – 3n = 1 – 1 = 0, wat een vijfvoud is. ii Laat n  willekeurig zijn en neem aan dat 8n – 3n een vijfvoud is, dan moeten we bewijzen dat 8n+1 – 3n+1 een vijfvoud is. Maar we kunnen 8n+1 – 3n+1 als volgt met 8n – 3n in verband brengen: 8n+1 – 3n+1 = 8(8n – 3n) + 8 · 3n – 3 · 3n = 8(8n – 3n) + 5 · 3n. Let op hoe we 8 · 3n aftrekken en ter compensatie ook weer optellen. Omdat 8n – 3n een vijfvoud is (inductiehypothese) en 5 · 3n een vijfvoud is, volgt er dat 8n+1 – 3n+1 een vijfvoud is. Uit i en ii volgt dat 8n – 3n een vijfvoud is voor alle n  .

12.6

De formule is waar voor n = 0 omdat dan n(n + 1)(2n + 1)/6 = 0 en  0i 0 i 2 = 02 = 0. De formule is waar voor n = 1 omdat dan n(n + 1)(2n + 1)/6 = 1 en  1i 0 i 2 = 02 + 12 = 1. De formule is waar voor n = 2 omdat dan n(n + 1)(2n + 1)/6 = 5 en ook  2i 0 i 2 = 02 + 12 + 22 = 5. De formule is waar voor n = 3 omdat dan n(n + 1)(2n + 1)/6 = 14 en ook  3i 0 i 2 = 02 + 12 + 22 + 32 = 14. We bewijzen nu met volledige inductie dat  ni 0 i 2 = n(n + 1)(2n + 1)/6 voor iedere n  (eventueel kunt u deze uitspraak P(n) noemen). i De formule is waar voor n = 0: zie hiervoor. ii Neem aan dat  ni 0 i 2 = n(n + 1)(2n + 1)/6 voor een willekeurige 1 2 n  , dan moeten we bewijzen dat  ni 0 i = (n + 1)(n + 2)(2n + 3)/6 (let op dat 2(n + 1) + 1 = 2n + 3). Daartoe splitsen we van de som in het linkerlid de laatste term met i = n + 1 af, dus: n 1

n

i 0

i 0

 i2   i2  (n  1)2

Omdat  ni 0 i 2 = n(n + 1)(2n + 1)/6 (inductiehypothese), volgt er dat n 1

 i2  61 n(n  1)(2n  1)  (n  1) 2

i 0

In het rechterlid halen we (n + 1)/6 buiten haakjes, wat (n + 1)(n(2n + 1) + 6(n + 1))/6 geeft, en dit schrijven we vervolgens als (n + 1)(2n2 + 7n + 6)/6 1 2 = (n + 1)(n + 2)(2n + 3)/6, wat inderdaad bewijst dat  ni 0 i = (n + 1)(n + 2)(2n + 3)/6. Samen met i volgt nu dat  ni 0 i 2 = n(n + 1)(2n + 1)/6 voor alle n  . 12.7

a We bewijzen met volledige inductie dat 9 n+1 + 63 deelbaar is door 72 voor alle n  . i Voor n = 0 geldt dat 9n+1 + 63 = 72, wat deelbaar is door 72. ii Laat n  willekeurig zijn en neem aan dat 9n+1 + 63 deelbaar is door 72, dan moeten we bewijzen dat 9n+2 + 63 deelbaar is door 72. Maar we kunnen 9n+2 + 63 als volgt met 9n+1 + 63 in verband brengen: 9n+2 + 63 = 9(9n+1 + 63) – 9 · 63 + 63 = 9(9n+1 + 63) – 8 · 63. Omdat 9n+1 + 63 deelbaar is door 72 (inductiehypothese) en 8 · 63 = 7 · 72 deelbaar is door 72, volgt er dat 9n+2 + 63 deelbaar is door 72. Samen met i volgt nu dat 9n+1 + 63 deelbaar is door 72 voor alle n  . Het verband tussen 9n+2 + 63 en 9n+1 + 63 kan bijvoorbeeld ook als volgt tot stand worden gebracht: 9n+2 + 63 = 9 · 9n+1 + 63 = 8 · 9n+1 + 9n+1 + 63 = 72 · 9n + (9n+1 + 63). Omdat 72 · 9n deelbaar is door 72, kan hiermee ook het inductiebewijs worden volbracht. b We bewijzen met volledige inductie dat an = 5 · 3n – n – 2 voor alle n . i Voor n = 0 geldt dat a0 = 5 · 30 – 0 – 2 = 3, wat juist is. ii Laat n  willekeurig zijn en neem aan dat an = 5 · 3n – n – 2, dan moeten we bewijzen dat an+1 = 5 · 3n+1 – (n + 1) – 2. We gebruiken nu de recurrentie om an+1 in verband te brengen met het ‘vorige’ getal an: an+1 = 3an + 2(n + 1) + 1. Omdat an = 5 · 3n – n – 2 (inductiehypothese), zien we dan dat an+1 = 3(5 · 3n – n – 2) + 2(n + 1) + 1, ofwel an+1 = 5 · 3n+1 – 3n – 6 + 2n + 2 + 1 = 5 · 3n+1 – (n + 1) – 2. Dit is precies wat we moesten bewijzen. Samen met i volgt nu dat an = 5 · 3n – n – 2 voor alle n  .

12.8

a Na 1 week heeft het eerste dier (éénmalig) 2 nakomelingen geproduceerd, zodat er na 1 week 1 + 2 dieren zijn. Na 2 weken hebben ieder van de 2 nakomelingen weer éénmalig 2 nakomelingen geproduceerd, dus in totaal 2 · 2 = 22 nakomelingen. Na 2 weken zijn er dus 1 + 2 + 22 dieren. Na 3 weken komen er 22 · 2 = 23 nakomelingen bij en zijn er in totaal 1 + 2 + 22 + 23 dieren. Enzovoorts: na n weken komen er 2n–1 · 2 = 2n nakomelingen bij en zijn er in totaal 1 + 2 + 2 2 + ... + 2n–1 + 2n =  ni 0 2i dieren. b Voor n = 0, 1, 2 en 3 geldt dat de som uit onderdeel a gelijk is aan 1, 1 + 2 = 3, 1 + 2 + 4 = 7 en 1 + 2 + 4 + 8 = 15. Als we 1 bij deze getallen optellen, ontstaat de rij 2, 4, 8, 16, wat opeenvolgende machten van 2 zijn. We bewijzen nu met volledige inductie dat  ni 0 2i = 2n+1 – 1 voor alle n  . i Voor n = 0 geldt dat 2n+1 – 1 = 1 en ook  ni 0 2i = 20 = 1. ii Laat n  willekeurig zijn en neem aan dat  ni 0 2i = 2n+1 – 1, dan 1 i moeten we bewijzen dat  ni 0 2 = 2n+2 – 1. Als altijd splitsen we de som n 1 i n n+1 i als volgt:  i 0 2 =  i 0 2 + 2 . Uit de inductiehypothese volgt dan dat 1 i  ni 0 2 = 2n+1 – 1 + 2n+1 = 2 · 2n+1 – 1 = 2n+2 – 1, wat we moesten aantonen. Samen met i volgt nu dat  ni 0 2i = 2n+1 – 1 voor alle n  .

12.9

Het bewijs is niet correct omdat de redenatie in ii onjuist is voor n = 1. Immers, dan zijn {s1} en {s2} disjunct en uit het feit dat alle schapen in {s1} dezelfde kleur hebben en dat alle schapen in {s2} dezelfde kleur hebben, mag er dan niet geconcludeerd worden dat alle schapen in S = {s1, s2} dezelfde kleur hebben.

12.10

Voor n = 0 geldt dat 2n + 1 ≤ 2n, maar dat geldt niet meer voor n = 1 en 2. Pas vanaf n0 = 3 geldt dat 2n + 1 ≤ 2n voor alle n  met n ≥ n0. We bewijzen dit met volledige inductie. i Voor n = 3 geldt dat 2n + 1 = 7 en 2n = 8, dus 2n + 1 ≤ 2n. ii Laat n  met n ≥ 3 willekeurig zijn en neem aan dat 2n + 1 ≤ 2n, dan moeten we bewijzen dat 2(n + 1) + 1 ≤ 2n+1. Omdat we in de inductiehypothese iets over 2n + 1 weten, ligt het voor de hand om 2(n + 1) + 1 te schrijven als (2n + 1) + 2. Nu kunnen we gebruiken dat 2n + 1 ≤ 2n (inductiehypothese) en volgt er dat (2n + 1) + 2 ≤ 2n + 2, ofwel 2(n + 1) + 1 ≤ 2n + 2. In het rechterlid willen we niet 2n + 2 hebben, maar 2n+1 = 2 · 2n = 2n + 2n. Echter, voor n ≥ 3 geldt zeker dat 2 ≤ 2n, dus ook 2n + 2 ≤ 2n + 2n, ofwel 2n + 2 ≤ 2n+1. Hiermee zien we dan dat 2(n + 1) + 1 ≤ 2n+1, wat we moesten aantonen. Samen met i volgt nu dat 2n + 1 ≤ 2n voor alle n  met n ≥ 3.

12.11

Het schema wordt dan als volgt. i Bewijs dat P(n0) waar is. ii Bewijs voor willekeurige n  met n ≥ n0: als P(k) waar is voor k = n0, n0 + 1, ..., n, dan is ook P(n + 1) waar. Omdat P(n0) waar is, volgt uit ii dat P(n0 + 1) waar is. Omdat nu P(n0) en P(n0 + 1) waar zijn, volgt uit ii dat P(n0 + 2) waar is, enzovoort.

12.12

Het schema wordt dan als volgt. i Bewijs dat P(n0) en P(n0 + 1) waar zijn. ii Bewijs voor willekeurige n  met n ≥ n0: als P(n) en P(n + 1) waar zijn, dan is ook P(n + 2) waar. Omdat P(n0) en P(n0 + 1) waar zijn, volgt uit ii dat P(n0 + 2) waar is. Omdat nu P(n0 + 1) en P(n0 + 2) waar zijn, volgt uit ii dat P(n0 + 3) waar is, enzovoort.

12.13

We bewijzen met volledige inductie dat in de strings uit L het aantal I’s nooit een 3-voud is. i Het aantal I’s in MI is geen 3-voud. ii Neem aan dat w een string uit L is waarin het aantal I’s geen 3-voud is, dan moeten we bewijzen dat in alle strings van L, die uit w ontstaan door het toepassen van de regels uit de inductiestap, het aantal I’s ook geen 3voud is. De regel ‘als xI L, dan xIU L’ verandert het aantal I’s niet. De regel ‘als Mx L, dan Mxx L’ verdubbelt het aantal I’s, waardoor geen 3-voud kan ontstaan. De regel ‘als xIIIy L, dan xUy L’ vermindert het aantal I’s met 3, waardoor geen 3-voud kan ontstaan. De regel ‘als xUUy L, dan xy L’ verandert het aantal I’s niet. Omdat alle strings in L op deze wijze ontstaan (de uitsluitingsregel), volgt uit i en ii dat het aantal I’s in de strings van L nooit een 3-voud is. De oplossing van de ‘MU-puzzel’ is dan eenvoudig: het aantal I’s in MU is 0, wat een 3-voud is! Dit bewijst dat MU L.

12.14

Voor n = 0, 1, 2, ..., 6 geldt niet dat n! > 3n, maar wel voor n = 7, omdat 7! = 5040 en 37 = 2187. We beweren nu dat met n0 = 7 geldt dat n! > 3n voor alle n  met n ≥ n0 en bewijzen dit met volledige inductie. i Voor n = 7 geldt dat n! > 3n (zie hiervoor). ii Laat n  met n ≥ 7 willekeurig zijn en neem aan dat n! > 3n, dan moeten we bewijzen dat (n + 1)! > 3n+1. Omdat (n + 1)! = n!(n + 1) en n! > 3n (inductiehypothese), volgt er dat (n + 1)! > 3n(n + 1). Het rechterlid willen we naar het gewenste resultaat 3n+1 toewerken, met andere woorden, we willen 3n(n + 1) vervangen door 3n+1, ofwel n + 1 door 3. Dit kunnen we doen omdat voor n ≥ 7 zeker geldt dat n + 1 > 3, dus 3n(n + 1) > 3n · 3 = 3n+1, wat we moesten aantonen. Samen met i volgt nu dat n! > 3n voor alle n  met n ≥ 7.

12.15

i

Voor n = 1 geldt B 

1 i 1

ii Zij n 

B

n i 1

B

Ai 

n1 i 1

Ai 

Ai  B  A1 

1 i 1

( B  Ai ) .

met n ≥ 1 willekeurig en neem aan dat n i 1

( B  Ai ) , dan moeten we bewijzen dat

n1 i 1

( B  Ai ) . We splitsen de vereniging

n 1 i 1

n

Ai ) in

i 1

Ai , de

vereniging van de eerste n termen, en de term met i = n + 1, dus An + 1: n1  n  B  Ai  B   Ai  An1   distributiviteit   i 1  i 1  n   inductiehypothese  B  Ai   B  An1  i 1  



n i 1



( B  Ai )   B  An1  

n 1 i 1

voeg de afgesplitste term weer toe

( B  Ai )

Samen met i volgt nu dat B 

n i 1

Ai 

n i 1

( B  Ai ) voor alle n 

+.

12.16

We bewijzen met volledige inductie dat tn = 3n + (–2)n + 2n + 3 voor alle n . i Omdat 30 + (–2)0 + 2 · 0 + 3 = 5 = t0 en 31 + (–2)1 + 2 · 1 + 3 = 6 = t1, is de formule waar voor n = 0 en n = 1. ii Neem aan dat de formule voor tn en tn–1 waar is, dan moeten we bewijzen dat de formule waar is voor tn+1. Uit de recurrentie volgt dat tn+1 = tn + 6tn–1 – 12(n + 1) + 8. We kunnen de inductiehypothese voor tn en tn–1 toepassen en dus de formules tn = 3n + (–2)n + 2n + 3 en tn–1 = 3n–1 + (–2)n–1 + 2(n – 1) + 3 gebruiken. Als we deze invullen, dan volgt dat tn+1 = tn + 6tn–1 – 12(n + 1) + 8 = (3n + (–2)n + 2n + 3) + 6(3n–1 + (–2)n–1 + 2(n – 1) + 3) – 12n – 4 Het rechterlid hiervan willen we naar het antwoord toewerken, dus naar 3n+1 + (–2)n+1 + 2(n + 1) + 3. Hiertoe halen we overal factoren 3 n en (–2)n als volgt buiten haakjes (en nemen we het resultaat op de gewenste manier bij elkaar): (1 + 2)3n + (1 – 3)(–2)n + 2n + 3 + 12n – 12 + 18 – 12n – 4 = 3n+1 + (–2)n+1 + 2(n + 1) + 3, wat we moesten bewijzen. Samen met i toont dit aan dat de formule waar is voor alle n  . Uitwerking van de zelftoets

2

1

We bewijzen met volledige inductie dat voor alle n  . i Omdat  0k 01/2k  1/20  1 en 2  1/20  1, is de formule waar voor n = 0. ii Neem aan dat de formule waar is voor een willekeurige n  . We moeten nu bewijzen dat de formule ook waar is voor n + 1, dus dat nk 10 1/2k  2  1/2n1 . We bewijzen dit door een term af te splitsen:

1 1   nk 0 k  2k 2 1 1  2  n  n 1  2  2 2 n 1

 k 0

1  (gebruik de inductiehypothese) 2n 1 2 1 1  n 1  2  n 1 n  1 2 2 2

Uit i en ii volgt nu dat de formule waar is voor alle n. 2

a Proberen van verschillende waarden voor n levert dat voor n = 4 de ongelijkheid geldt: 42 < 2(4 – 1)2. b We bewijzen met volledige inductie dat n2 < 2(n – 1)2 voor alle n ≥ 4. i De uitspraak is waar voor n = 4 (zie onderdeel a). ii Neem aan dat de uitspraak waar is voor een willekeurige n ≥ 4. We moeten bewijzen dat de uitspraak waar is voor n + 1, dus dat (n + 1)2 < 2n2. We bewijzen dit door de volgende berekening: (n + 1)2 = n2 + 2n + 1 < (gebruik de inductiehypothese) 2(n – 1)2 + 2n + 1 = 2n2 – 4n + 2 + 2n + 1 = 2n2 – 2n + 3 < 2n2 (want n ≥ 4). Uit i en ii volgt dat de uitspraak waar is voor elke n  .

3

–2 a We bewijzen met volledige inductie dat  ni 0 Fi  Fn  1 voor n  met n ≥ 2. i Omdat  0i 0 Fi  F0  1  F2  1 is de formule waar voor n = 2. ii Neem aan dat de formule waar is voor willekeurige n  , n ≥ 2. n –1 We moeten bewijzen dat de formule waar is voor n + 1, dus dat  i 0 Fi = Fn+1 – 1. We doen dit door een term af te splitsen: –1 2  ni 0 Fi   n– i 0 Fi  Fn 1 = (gebruik de inductiehypothese) = Fn – 1 + Fn–1 = ( gebruik de recurrente betrekking voor Fn) Fn+1 – 1. Uit i en ii volgt dat de formule waar is voor elke n ≥ 2. b We bewijzen met volledige inductie dat  ni 0 F2i  F2n 1 voor n  . i Omdat  0i 0 F2i  F0  F1 geldt de formule voor n = 0. ii Neem aan dat de formule waar is voor willekeurige n  . We moeten bewijzen dat de formule waar is voor n + 1, dus dat 1  ni 0 F2i  F2(n 1)1 = F2n+3. We doen dit door een term af te splitsen. 1  ni 0 F2i   ni 0 F2i  F2n 2 = (gebruik de inductiehypothese) = F2n+1 + F2n+2 = (gebruik de recurrente betrekking voor Fn) = F2n+3

4

We bewijzen met volledige inductie dat an = (–4)n – 3n + 2 · 4n voor alle n . i Omdat (–4)0 – 30 + 2 · 40 = 2 = a0 en (–4)1 – 31 + 2 · 41 = 1 = a1, is de formule waar voor n = 0 en n = 1. ii Neem aan dat de formule voor an en an–1 waar is, dan moeten we bewijzen dat de formule waar is voor an+1. Uit de recurrentie volgt dat an+1 = –an + 12an–1 + 4n+1. We kunnen nu de inductiehypothese voor an en an–1 toepassen en dus de formules an = (–4)n – 3n + 2 · 4n en an–1 = (–4)n–1 – 3n–1 + 2 · 4n–1 gebruiken. Als we deze invullen, dan volgt dat an+1 = –an + 12an–1 + 4n+1 = –((–4)n – 3n + 2 · 4n) + 12((–4)n–1 – 3n–1 + 2 · 4n–1) + 4n+1 Het rechterlid hiervan willen we naar het antwoord toewerken, dus naar (–4)n+1 – 3n+1 + 2 · 4n+1. Hiertoe schrijven we 12 als 3 · 4 = (–3) · (–4) en nemen de termen als volgt samen: (–1 – 3)(–4)n + (1 – 4)3n + (–2 + 6 + 4)4n = (–4)n+1 – 3n+1 + 2 · 4n+1 Dus an+1 = (–4)n+1 – 3n+1 + 2 · 4n+1, wat we moesten bewijzen. Samen met i toont dit aan dat de formule waar is voor alle n  .

5

Het bewijs is niet correct omdat in ii een redenatie voorkomt die niet correct is voor n = 0. Immers, in het rechterlid van de vergelijking 5n+1 – 2n+1 = 5(5n – 2n) + 6 · 2n–1 is 6 · 2n–1 geen zesvoud voor n = 0.

Bijlage

Symbolenlijst

symbool

betekenis

« □   {...} {xP(x)} {x AP(x)}

einde voorbeeld einde bewijs is element van is geen element van expliciete definitie van een verzameling impliciete definitie van een verzameling impliciete definitie van verzameling van elementen uit verzameling A aantal elementen van verzameling V indexnotatie met index i universum van verzamelingen gelijkteken ongelijkteken lege verzameling verzameling van de natuurlijke getallen verzameling van de gehele getallen verzameling van de gehele positieve getallen verzameling van de gehele negatieve getallen verzameling van de rationale getallen verzameling van de rationale positieve getallen verzameling van de rationale negatieve getallen verzameling van de reële getallen verzameling van de reële positieve getallen verzameling van de reële negatieve getallen is deelverzameling van doorsnede vereniging complement van de verzameling A is groter dan is kleiner dan is groter dan of gelijk aan is kleiner dan of gelijk aan (logische) en, conjunctieteken (logische) of, disjunctieteken is deler van

V Pi, ai U =  Ø

+ –

+ –

+ –

   Ac > < ≥ ≤   

symbool

betekenis

ggd kgv G = (V, E)

grootste gemene deler kleinste gemene veelvoud graaf G met puntenverzameling V en lijnenverzameling E gerichte graaf D met puntenverzameling V en pijlenverzameling A graad van punt v uitgraad van u ingraad van u wandeling in graaf doorsnede van verzamelingen Ai vereniging van verzamelingen Ai machtsverzameling van de verzameling A symmetrisch verschil absolute waarde van x n-tupel het paar (x, y) behoort tot de relatie R het paar (x, y) behoort niet tot de relatie R f is een functie van A naar B aan x wordt f(x) toegevoegd functie van n variabelen samenstelling van de functies f en g samenstelling van n functies f inverse functies van f van B naar A identieke functie op A cartesisch product van A en B cartesisch product  , ‘het platte vlak’ cartesisch product   , ‘de ruimte’ cartesisch product van n verzamelingen faculteit som van variabelen xi product van variabelen xi Fibonacci-getal toekenningsopdracht: definitiesymbool negatieteken implicatieteken equivalentieteken niet beide noch logische equivalentie verum falsum logisch gevolg

D = (V, A) d(v) d+(u) d–(u) v0 v1 v2 i I A i i I A i P(A)  x (a1, a2, ..., an) xRy x Ry  f: A  B x  f(x) f: n  fg fn f–1: B  A 1A AB 2 3 n !  i I x i  iI x i  Fn :=    nand nor  ⊤ ⊥ 

symbool

betekenis

P(x1, x1, ..., xn)   [t/v] ⊓ ⊔ 1 0 D(n) a Rn R+ R* ST [x]R V/R PL ⊑ ⊏ ≤* sup(A) inf(A)

n-plaatsig predikaatsymbool universele kwantor existentiële kwantor substitutie van v in door t binaire verzamelingsoperatie dakje binaire verzamelingsoperatie bakje één-element nul-element verzameling van delers van n complement van a in Boole-algebra n-de macht van relatie R transitieve afsluiting van relatie R reflexieve afsluiting van relatie R samenstelling van relaties equivalentieklasse van x in relatie R quotiënt van equivalentierelatie R in verzameling V verzameling propositielogische formules gaat vooraf aan (partiële ordening) irreflexieve variant van relatie u lexicografische ordening supremum van verzameling A infimum van verzameling A

Bijlage

Grieks alfabet

kleine letter

hoofdletter

uitspraak

         k           ,    

         K              

alfa bèta gamma delta epsilon zèta èta thèta iota kappa lambda mu nu ksi omicron pi rho sigma tau upsilon phi chi psi omega

Register

Absolute waarde II: 90 Absorptie I: 44 Absorptie voor doorsnede en vereniging II: 21 Afbeelding II: 87 Algemeen geldig I: 88 Al-kwantor I: 65 Antisymmetrie II: 109 Antisymmetrisch II: 128 Argument II: 87 Assenstelsel II: 75 Associativiteit I: 43 Associativiteit van doorsnede en vereniging II: 16 Atomaire formule I: 71 Axioma II: 38 Backus-Naur form III: 22 Bakje II: 37 Basis III: 12 Bedrijfsregels I: 81 Beeld II: 89 Beginpunt II: 59 Bereik I: 21 Bereik of waardenverzameling II: 89 Besliskunde II: 52 Bewijs met volledige inductie III: 40 Bijectie II: 94 Bijectief II: 94 Binaire relatie II: 79 Binaire relatie II: 106 Boole, G. II: 43 Boolealgebra II: 42 Bovengrens II: 137 Buur II: 54 Cartesisch product II: 74 Cirkelschijf II: 78 Commutativiteit I: 42 Commutativiteit van doorsnede en vereniging II: 15 Complement II: 10, 41, 139 Complementregels II: 23 Component II: 59, 67 Conclusie I: 53 Conjunct I: 17 Conjunctie I: 17 Conjunctieteken I: 17 Conjunctieve normaalvorm I: 50 Connectief I: 18 Constante I: 63 Constante functie II: 95 Constante rij II: 95 Contingentie I: 38 Continu II: 88

Contradictie I: 37 Coördinaat II: 73 Correctheidsbewering Cykel II: 61

I: 80

Dakje II: 37 Dan en slechts dan als I: 18 De Morgan II: 43 Deelformule I: 20, 72 Deelverzamelingen II: 51 Delerrelatie II: 110 Desda I: 18, 28 Differentievergelijking III: 28 Disjunct I: 17 Disjunctie I: 17 Disjunctieteken I: 17 Disjunctieve normaalvorm I: 47 Distributiviteit I: 44, 90, 95 Distributiviteit van doorsnede en vereniging II: 20 Domein of definitiegebied II: 89 Doorsnede II: 10 Driehoeksgetallen III: 9, 23 Dualiteit I: 95 Dubbel complement II: 23, 44 Dubbele negatie I: 45 Dubbele pijl II: 64 Een II: 137 Een-eenduidig II: 93 Eénelement II: 22, 40 Een-op-een II: 93 Eenplaatsig I: 64 Eerste term a III: 23, 26 Eindige meetkundige reeks III: 26 Eindige rekenkundige reeks III: 23 Eindpunt II: 55, 59 Equivalentie I: 18 Equivalentie-eliminatie I: 46 Equivalentieklasse II: 119 Equivalentierelatie II: 116 Equivalentieteken I: 18 Existentiële generalisatie I: 98, 103 Existentiële kwantor I: 66 Expliciete formule III: 18 Faculteit III: 18 Falsum I: 42 Formule I: 19 Formule van de predikaatlogica I: 71 Formule van de propositielogica I: 20 Formule voor een eindige meetkundige reeks III: 27 Formule voor een eindige rekenkundige reeks III: 25

76

Formule voor sn III: 24 Functie II: 86 Functie van één variabele II: 91 Functie van n variabelen II: 91 Functiesymbool I: 68 Functievoorschrift II: 87 ‘gaat vooraf aan’ II: 129 Gebonden variabele I: 73 Gedeeltelijke distributiviteit I: 102 Geïsoleerd punt II: 55 Geordend paar II: 73 Gericht pad II: 67 Gerichte cykel II: 67 Gerichte graaf II: 64, 85 (Gerichte) lus II: 64 Gerichte wandeling II: 66 Gesloten formule I: 73 Gesloten wandeling II: 59 Graad II: 55 Graad d(u) II: 65 Graaf II: 53, 85 Graaf van een relatie II: 83 Grafiek II: 88 Grafiek van de inverse II: 98 Grootste element II: 136 Hassediagram II: 133 Herbenoemen gebonden variabele 99 Hoofdkolom I: 37 Hornclausule I: 106 iat-relatie II: 129 Idempotentie I: 44; II: 44 Idempotentie van doorsnede en vereniging II: 14 Identieke functie II: 96 Identiteit II: 96 Implicatie I: 18 Implicatie-eliminatie I: 46 Implicatieteken I: 18 In relatie staan met II: 80 Incident II: 54 Incidentie II: 54 Indexnotatie II: 18 Indexverzameling II: 17 Inductiehypothese III: 40 Inductiestap III: 12, 13 Inductieve definitie III: 13 Inductieve definitie van N III: 12 Infimum II: 138 Ingraad d–(u) II: 65 Injectie II: 93 Injectief II: 93

I:

Instantiatie I: 93, 103 Inverse II: 97 Inverse functie II: 97 Invoer II: 87 Irreflexief II: 108, 129 Iteratie III: 28 Kleinste element II: 136 Koningsbergen II: 56 Kop II: 64 Kwantorbereik I: 72 Lege relatie II: 79 Lengte van een gerichte wandeling II: 66 Lengte van een wandeling II: 58 Leonhard Euler II: 57 Lexicografische ordening II: 130 Lijn II: 53, 78 Lijnenverzameling II: 53 Lineaire ordening II: 130 Logica I: 13 Logisch equivalent I: 40, 95 Logisch gevolg I: 53, 101 Logistiek II: 52 Loze kwantificatie I: 95 Loze universele kwantificatie I: 93 Lus II: 64, 84 Machten van een relatie II: 112 Machtsverzameling II: 13 Materiële equivalentie I: 41 Maximaal element II: 135 Meetkundige rij III: 26 Minimaal element II: 135 Model I: 77 Natuurlijke getallen III: 11 Negatie I: 17 Negatieteken I: 17 NIET-poort II: 30 n-kubus II: 134 Normaalvorm I: 47 Normaliseren I: 47 n-plaatsig I: 64 n-Tupel II: 73 Nul II: 137 Nulelement II: 22, 40 OF-poort II: 31 Omkeerprobleem II: 96 Ondergrens II: 137 Ongerichte wandeling II: 66 Onsamenhangend II: 59

Onsamenhangende gerichte graaf II: 67 Onvergelijkbaar II: 130 Op II: 92 Open formule I: 73 Open wandeling II: 59 Opvolger II: 132 Origineel II: 89 Paar II: 73 Pad II: 60 Pad tussen u en v II: 61 Partieel geordende verzameling II: 129 Partiële functie II: 95 Partiële ordening II: 129 Partitie II: 117 Peirce I: 29 Pijl II: 64 Predikaatsymbool I: 63 Prenexe normaalvorm I: 100 Principe van de uitgesloten derde I: 39 Productteken III: 20 Prolog I: 51 Propositieletter I: 18 Punt II: 53 Puntenverzameling II: 53 Quine I: 30 Quotiënt II: 122 rat-relatie II: 129 Recurrente betrekking III: 28 Recurrentie III: 28 Recursieve definitie III: 18 Recursieve definitie van som III: 20 Reden r III: 26 Reflexief II: 108, 129 Reflexieve transitieve afsluiting II: 114 Rekenkundige rij III: 23 Relatie II: 79 Relatie in A II: 79 Relatie van A naar B II: 79 Representant II: 120 Resolutie I: 107 Rij II: 90 Rij van Fibonacci III: 28 Rooster II: 75 Samengestelde formule I: 71 Samenhangend II: 59, 67 Samenstelling II: 99 Schakelalgebra II: 35

77

Semantiek I: 22 Sheffer I: 29 Sommatieindex III: 20 Somteken III: 19 Staart II: 64 Stamboom II: 51 Standaardtautologie I: 38 Startwaarde(n) III: 18 Sterk samenhangend II: 67 Strikte partiële ordening II: 129 String II: 130 Substitutie I: 74 Supremum II: 138 Surjectie II: 92 Surjectief II: 92 Symmetrie II: 109 Symmetrisch verschil II: 15 Syntaxis I: 22 Tarski I: 22 Tautologie I: 37 Tegenvoorbeeld I: 89 Term I: 70 Termen II: 90 Toekenningsregel I: 105 Toevoegen aan II: 84 Totale ordening II: 130 Transitief II: 128 Transitieve afsluiting II: 114 Transitiviteit II: 109 Tweeplaatsig I: 64 Uiteinde II: 54 Uitgangspunt I: 53 Uitgraad d+(u) II: 65 Uitsluiting III: 12, 13 Uitvoer II: 87 Universele generalisatie I: 94 Universele kwantor I: 65 Universele relatie II: 79 Variabele I: 64 Verbinden II: 54 Vereniging II: 10 Vergelijkbaar II: 130 Verschil II: 11 Verschil v III: 23 Vertaalsleutel I: 63 Verum I: 42 Verzamelingenalgebra II: 9 Volledig origineel II: 89 Voorganger II: 132 Voorouder-nakomeling-relatie Vrij voor I: 92 Vrije variabele I: 73

II: 128

Waardering I: 37 Waarheidsfunctioneel I: 16 Waarheidstabel I: 22 Waarheidswaarde I: 15 Wandeling II: 58 Wetten van De Morgan I: 45; II: 24 Wortelfunctie II: 92 Zwak samenhangend Zwarte doos II: 87

II: 67

78