Volledige inductie

Schrijver: Leandro Alegsa

21-11-2020

Wiskundige inductie is een speciale manier om een wiskundige waarheid te bewijzen. Het kan gebruikt worden om te bewijzen dat iets waar is voor alle natuurlijke getallen (alle positieve gehele getallen). Het idee is dat

Iets is waar voor het eerste geval
Datzelfde geldt altijd voor de volgende zaak...

dan

Datzelfde geldt voor elk geval

In de zorgvuldige taal van de wiskunde:

Zeg dat het bewijs zal worden geleverd door inductie over n {\\\playstyle n} . ( n {\\\playstyle n} is de inductievariabele.)
Laat zien dat de verklaring waar is als n {\\\\\\\an5} 1.
Veronderstel dat de verklaring waar is voor elk natuurlijk getal n {\\\playstyle n} . (Dit wordt de inductiestap genoemd.)

Laat dan zien dat de verklaring waar is voor het volgende nummer, n + 1 {\playstyle n+1} $n+1$ .

Omdat het waar is voor 1, dan is het waar voor 1+1 (=2, door de inductiestap), dan is het waar voor 2+1 (=3), dan is het waar voor 3+1 (=4), enzovoort.

Een voorbeeld van bewijs door inductie:

Bewijs dat voor alle natuurlijke getallen n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\\\\\\\\\\+2+3+.... $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Bewijs:

Eerst kan de verklaring worden geschreven: voor alle natuurlijke getallen n

2 ∑ k = 1 n k = n ( n + 1 ) {\playstyle 2\sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$

Door inductie op n,

Ten eerste, voor n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\playstyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

dus dit is waar.

Ga er vervolgens van uit dat voor sommige n=n0 de bewering waar is. Dat wil zeggen:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\\\\sum 2{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

Dan voor n=n0+1:

2 ∑ k = 1 n 0 + 1 k {\playstyle 2\sum _{k=1}^{n_{0}}+1}k} $2\sum _{k=1}^{{n_{0}}+1}k$

kan worden herschreven

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) 2 links... $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Aangezien 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\playstyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\playstyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2}}. $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Vandaar dat het bewijs juist is.

Vergelijkbare bewijzen

Wiskundige inductie wordt vaak aangegeven met de startwaarde 0 (in plaats van 1). In feite werkt het net zo goed met verschillende beginwaarden. Hier is een voorbeeld wanneer de beginwaarde 3 is. De som van de binnenhoeken van een n {\\\playstyle n} -sided polygon is ( n - 2 ) 180 {\playstyle (n-2)180} $(n-2)180$ graden.

De initiële startwaarde is 3, en de binnenhoeken van een driehoek zijn ( 3 - 2 ) 180 {\playstyle (3-2)180} $(3-2)180$ graden. Veronderstel dat de binnenhoeken van een veelhoek ( n - 2 ) 180 $(n-2)180$ graden zijn. Voeg daar een driehoek aan toe die de figuur een n + 1 maakt (n+1). $n+1$ -zijdige veelhoek, en dat verhoogt het aantal hoeken met 180 graden ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\playstyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ graden. Bewijs.

Er zijn een groot aantal wiskundige objecten waarvoor bewijzen door middel van wiskundige inductie werken. De technische term is een goed geordende set.

Inductieve definitie

Hetzelfde idee kan werken om te definiëren, maar ook om te bewijzen.

Definieer n nevenbeeld van de graad neef:

Een neef van de 1e $1$ graad is het kind van de broer of zus van een ouder...
Een n+1 n+1 $n+1$ st graad neef is het kind van een ouder's n+1 graad neef.

Er is een set van axioma's voor de rekenkunde van de natuurlijke getallen die gebaseerd is op wiskundige inductie. Dit wordt "Peano's Axioma's" genoemd. De ongedefinieerde symbolen zijn | en =. De axioma's zijn

| is een natuurlijk getal
Als n neppeeltje een natuurlijk getal is, dan $n|$ is neppeeltje een natuurlijk getal...
Als n = m || {\displaystyle n|=m|} $n|=m|$ dan n = m {displaystyle n=m} $n=m$

Men kan dan de bewerkingen van optellen en vermenigvuldigen en zo verder definiëren door middel van wiskundige inductie. Bijvoorbeeld:

m + | = m | m + |=m|| $m+|=m|$
m + n | = ( m + n ) | m+n|=(m+n)| $m+n|=(m+n)|$

Vragen en antwoorden

V: Wat is wiskundige inductie?

A: Wiskundige inductie is een speciale manier om een wiskundige waarheid te bewijzen die kan worden gebruikt om te bewijzen dat iets waar is voor alle natuurlijke getallen of positieve getallen vanaf een bepaald punt.

V: Hoe verloopt het bewijs door inductie?

A: Het bewijs door inductie verloopt typisch door te stellen dat het bewijs over n zal worden gedaan, te laten zien dat de uitspraak waar is als n 1 is, aan te nemen dat de uitspraak waar is voor elk natuurlijk getal n, en dan te laten zien dat het waar is voor het volgende getal (n+1).

V: Wat betekent het om iets aan te nemen in een inductieve stap?

A: Iets aannemen in een inductieve stap betekent iets als waar aannemen zonder bewijs te leveren. Het dient als uitgangspunt voor verder onderzoek.

V: Wat voor soort getallen worden gebruikt bij wiskundige inductie?

A: Wiskundige inductie gebruikt meestal natuurlijke getallen of positieve getallen vanaf een bepaald punt.

V: Hoe toont u aan dat iets waar is voor het volgende getal (n+1)?

A: Om aan te tonen dat iets waar is voor het volgende getal (n+1), moet u eerst bewijzen dat het waar is als n=1, en dan uw aanname uit de inductieve stap gebruiken om aan te tonen dat het ook waar is voor n+1.