Volledige inductie

Volledige inductie is een veelgebruikte bewijsmethode in de wiskunde, meestal als we werken met natuurlijke getallen of met een andere rij.

Principe

Het basisprincipe is dat we de bewering bewijzen voor een eerste element, bij de natuurlijke getallen meestal n = 1. Dat bewijzen we door gewoon in te vullen. In de volgende stap, de inductiestap, bewijzen we de implicatie “als de bewering geldt voor n = a, dan geldt ze ook voor n = a + 1”.

Uit deze twee stappen kunnen we afleiden dat de gegeven uitdrukking geldt voor alle n (uit een of andere verzameling waarmee we werken). Waarom is dat zo? Aan het begin bewijzen we dat de uitdrukking geldt voor n = 1. Tegelijk weten we dat als de uitdrukking geldt voor n = a, ze ook geldt voor n = a + 1. We kiezen dus a = 1. We weten dat de uitdrukking voor a = 1 geldt en ook dat ze geldt voor a + 1 = 2. Op dit moment weten we dat de uitdrukking geldt voor a = 2. Maar omdat ze ook voor a + 1 geldt, moet ze ook gelden voor 2 + 1 = 3. En zo verder.

Eerste voorbeeld

Het eerste voorbeeld is triviaal. We bewijzen dat als we bij een willekeurig even getal twee optellen, we weer een even getal krijgen. Omdat we werken met natuurlijke getallen, schrijven we een even getal in het algemeen als 2n, waarbij n een natuurlijk getal is. Als we voor n een willekeurig natuurlijk getal invullen, krijgen we als resultaat een even getal, dat zie je meteen. Deelbaarheid noteren we met een verticale streep, zo:

$$2\mid 2n$$

Deze notatie betekent dat twee de uitdrukking 2n zonder rest deelt. Nu we deelbaarheid kunnen opschrijven, kunnen we ook opschrijven wat we met volledige inductie moeten bewijzen.

$$2\mid 2n+2;n\in \mathbb{N}$$

Dit moeten we in het eerste voorbeeld bewijzen, dus dat twee de uitdrukking 2n + 2 deelt. Dat komt precies overeen met de oorspronkelijke opgave in woorden: “als we bij een willekeurig even getal twee optellen, krijgen we weer een even getal”.

In de eerste stap van de inductie bewijzen we het voor het eerste element, voor één. We vullen n = 1 in de uitdrukking in:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Twee deelt vier zonder rest, dus voor het eerste element geldt het. Dan komt de inductiestap, waarin we moeten bewijzen dat als het geldt voor het a-de element, het ook geldt voor het (a + 1)-de element. Aan het begin nemen we aan dat onze aanname geldt, dus n = a:

$$2\mid 2a+2$$

Van deze uitdrukking nemen we aan dat ze waar is. We gebruiken haar bij de constructie van het bewijs. Nu willen we bewijzen dat

$$2\mid 2(a+1)+2.$$

Wat hebben we gedaan? In plaats van a hebben we (a + 1) geschreven. De haakjes zijn belangrijk, deze uitdrukking zou fout zijn: 2a + 1 + 2. We tellen niet één op bij de hele uitdrukking, maar we maken van a echt een uitdrukking die één groter is, dus (a + 1). We vormen de uitdrukking om door de haakjes uit te werken.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Nu een kleine zijsprong over deelbaarheid. Als we twee getallen hebben, zeg p en q, die deelbaar zijn door een bepaald getal, bijvoorbeeld r, dan geldt dat ook hun som deelbaar is door het getal r. Er geldt dus:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

We kunnen daar bijvoorbeeld de getallen p = 8, q = 20 en r = 4 invullen. We zien dat vier zowel acht als twintig deelt. En ook hun som 8 + 20 = 28 wordt door vier gedeeld.

Hoe gebruiken we dat in ons voorbeeld? We splitsen de rechterkant in de getallen p en q zo:

$$p=2a+2;q=2$$

Het getal q, dus twee, is triviaal deelbaar door twee. En de uitdrukking p is ook deelbaar door twee, omdat de aanname ons dat zegt. De uitdrukking p komt precies overeen met onze aanname, waarvan we aannemen dat ze waar is. En als p deelbaar is door twee en tegelijk q deelbaar is door twee, dan is ook hun som deelbaar door twee.

Nog een keer over die aanname. Aan het begin zeiden we dat we aannemen dat geldt

$$2\mid 2a+2.$$

Daarom konden we, toen we tijdens de constructie van het bewijs de uitdrukking 2a + 2 tegenkwamen, zeggen dat die deelbaar is door twee. Juist omdat het onze aanname is. Dit is meestal de moeilijkste stap van volledige inductie: begrijpen wanneer en waarom je de inductiehypothese mag gebruiken.

Hiermee eindigt de inductie, het bewijs is succesvol geleverd, de stelling geldt.

Als je wilt, kun je het ook anders ontbinden en dan hoef je de aanname niet te gebruiken: p = 2n en q = 2 + 2. Het getal q = 4 is triviaal deelbaar door twee en dat geldt ook voor p = 2n, want na deling door twee houden we het getal n over, dat natuurlijk is, dus geheel. We hebben dus weer twee uitdrukkingen gekregen die allebei deelbaar zijn door twee, dus ook hun som is deelbaar door twee.

In beide gevallen hebben we echter bewezen dat

1. de uitdrukking geldt voor n = 1,
2. als de uitdrukking geldt voor n, ze dan ook geldt voor n + 1.

Hieruit kunnen we afleiden:

• We weten dat de uitdrukking geldt voor n = 1.
• Als ze geldt voor n, moet ze ook gelden voor n + 1, dus ook voor 1 + 1, dus de uitdrukking geldt ook voor n = 2.
• Als ze geldt voor n, moet ze ook gelden voor n + 1, dus ook voor 2 + 1, dus de uitdrukking geldt ook voor n = 3.
• Als ze geldt voor n, moet ze ook gelden voor n + 1, dus ook voor 3 + 1, dus de uitdrukking geldt ook voor n = 4.
• Als ze geldt voor n, moet ze ook gelden voor n + 1, dus ook voor 4 + 1, dus de uitdrukking geldt ook voor n = 5.
• …

Tweede voorbeeld

Nu bewijzen we met volledige inductie een eenvoudige bewering:

$$2^n\ge 2n;n\in \mathbb{N}.$$

Eerst de eerste stap: we kijken of de bewering geldt voor n = 1, als eerste element van de natuurlijke getallen waaruit we n kiezen.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Dit geldt triviaal. Nu gaan we naar de inductiestap, waarin we moeten uitzoeken of als de bewering geldt voor n = a, ze ook geldt voor n = a + 1. Onze aanname is dus dat geldt

$$2^a\ge 2a$$

en we willen bewijzen:

$$2^{a+1}\ge 2(a+1)$$

De linkerkant schrijven we eerst uit met de rekenregels voor machten en de rechterkant werken we gewoon uit.

$$2\cdot 2^a\ge 2a+2$$

Aan de linkerkant gebruiken we in plaats van vermenigvuldigen optellen, de rechterkant laten we ongewijzigd.

$$2^a+2^a\ge 2a+2$$

Nu gebruiken we de aanname. De aanname is een uitspraak waarvan we aannemen dat ze geldt. In de ongelijkheid staan aan beide kanten twee termen die bij elkaar zijn opgeteld. Tegelijk weten we echter dat

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

De eerste regel is de aanname en de tweede uitspraak is triviaal (de kleinste 2^a is voor a = 1 en dat is precies twee). We weten dus dat aan de linkerkant beide termen groter dan of gelijk aan beide termen aan de rechterkant zijn. Daarmee hebben we met inductie bewezen dat als de uitdrukking geldt voor a, ze ook geldt voor (a + 1), en omdat de uitdrukking ook voor één geldt, is de gegeven uitdrukking waar.

Derde voorbeeld

We proberen de volgende bewering te bewijzen:

$$3\mid n\Rightarrow 3\mid n^2;n\in \mathbb{N}$$

In woorden: als n deelbaar is door drie, dan is ook n² deelbaar door drie. Als n niet deelbaar is door drie, dan geldt de uitdrukking triviaal (volgens de definitie van de implicatie), dus we houden ons bezig met de gevallen waarin n deelbaar is door drie. Dat levert ons een rij natuurlijke getallen a_i=3, 6, 9, 12, 15… Vanaf nu bewegen we ons in deze rij a_i.

Het bewijs met inductie beginnen we met de eerste stap, dus of het geldt voor het eerste element. Ik herinner je eraan dat we ons in de rij a_i bewegen, dus we nemen het eerste element van deze rij, dus het element a₁, en dat is drie. Voor drie geldt de uitdrukking:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Nu gaan we naar de inductiestap. We zien dat de rij a_i geschreven zou kunnen worden als 3n, waarbij n een natuurlijk getal is. Het tweede element is dus drie groter dan het vorige enzovoort. Nu nemen we aan dat de uitdrukking geldt voor n en we moeten ervoor zorgen dat ze ook geldt voor (n + 3), wat het voorschrift is dat het volgende element van de rij waarin we ons bewegen, voortbrengt. We schrijven eerst de aanname op:

$$3\mid n\Rightarrow 3\mid n^2$$

en dan wat we willen bewijzen

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

We werken het haakje aan de andere kant uit met de formule:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

En nu zijn we bijna bij het doel. Aan de linkerkant hebben we een uitdrukking die zeker deelbaar is door drie, omdat n volgens de aanname deelbaar is door drie (we bewegen ons alleen in getallen uit de rij a_i) en drie ook deelbaar is door drie. Aan de rechterkant hebben we eerst n², en dat is volgens de aanname deelbaar door drie. We weten namelijk dat n deelbaar is door drie en de aanname zegt dat als n deelbaar is door drie, ook n² deelbaar is door drie:

$$3\mid n\Rightarrow 3\mid n^2$$

Verder volgt de term 6n, die triviaal deelbaar is door drie. Je kunt het je voorstellen als het vereenvoudigen van een breuk:

$$\frac{6n}{3}=2n$$

De variabele n is een natuurlijk getal, dus ook het product 2n is een natuurlijk getal, dus na deling door drie hebben we een natuurlijk getal gekregen en de term 6n moet dus deelbaar zijn door drie. En de negen aan het eind is weer deelbaar door drie. De uitdrukking geldt voor het eerste element en voor de inductiestap, ze is dus waar.

Aantal haakjes in een uitdrukking

Het laatste voorbeeld is wat ongebruikelijk. We proberen de bewering te bewijzen dat het aantal haakjes in een eenvoudige uitdrukking altijd even is, zodat je ziet dat volledige inductie ook in een heel andere context te gebruiken is dan alleen bij natuurlijke getallen. Aan het begin moeten we definiëren wat een eenvoudige uitdrukking is. Een eenvoudige uitdrukking is:

• een natuurlijk getal,
• als p een eenvoudige uitdrukking is, dan is ook (p²) een eenvoudige uitdrukking,
• als p en q eenvoudige uitdrukkingen zijn, dan is ook (p + q) een eenvoudige uitdrukking.

Eenvoudige uitdrukkingen zijn dus bijvoorbeeld: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). En dit zijn juist geen eenvoudige uitdrukkingen:

• 1 + 2 → de buitenste haakjes ontbreken,
• (1 + 2 → het rechterhaakje ontbreekt,
• 13² → de buitenste haakjes ontbreken,
• (1 + 2 + 3) → haakjes ontbreken, de juiste notatie zou (1 + (2 + 3)) moeten zijn

Een eenvoudige uitdrukking kan bijvoorbeeld zo ontstaan. Aan het begin kiezen we een eenvoudige uitdrukking (a + b). Nu vullen we voor a een eenvoudige uitdrukking a = (c + d) in, dus we krijgen ((c + d) + b), en voor b vullen we drie in: ((c + d) + 3). Voor c vullen we tien in: ((10 + d) + 3) en tot slot vullen we voor d in (5²): ((10 + (5²)) + 3). Het is belangrijk de haakjes in acht te nemen, anders werkt het niet.

Nu bewijzen we dat een eenvoudige uitdrukking een even aantal haakjes bevat (onder de even getallen valt ook nul).

In de eerste stap van de inductie kiezen we een eerste element. In dit geval is het eerste element de meest triviale eenvoudige uitdrukking, dat is een willekeurig natuurlijk getal. We stellen dus

$$j=n;n\in \mathbb{N}.$$

Voor de uitdrukking j geldt dat het aantal haakjes nul is, dus het eerste element voldoet. In de inductiestap nemen we aan dat we twee eenvoudige uitdrukkingen p en q hebben en dat beide een even aantal haakjes hebben. Dan moeten we bewijzen dat ook de eenvoudige uitdrukkingen (p + q) en (p²) een even aantal haakjes hebben.

Eerst de optelling. We definiëren nog een functie h(q), die het aantal haakjes van de uitdrukking q teruggeeft. Dan geldt dat de uitdrukking (p + q) precies h(p) + h(q) + 2 haakjes heeft. Ze heeft dus twee haakjes meer dan de som van de haakjes van de uitdrukkingen p en q. Volgens de aanname zijn zowel h(p) als h(q) even, dus als we drie even getallen optellen, krijgen we weer een even getal. Voor dit geval geldt de uitspraak.

Nu de macht. Weer geldt de aanname dat de eenvoudige uitdrukking p een even aantal haakjes bevat. De uitdrukking (p²) bevat dan h(p) + 2 haakjes, dus weer twee haakjes meer dan de uitdrukking p. Ook in dit geval tellen we even getallen op, dus het resultaat is even.

De uitspraak geldt voor het eerste element en geldt ook in de inductiestap, dus de uitspraak is waar.