|
De afzonderlijke eis dat de uitspraak geldig moet zijn voor de minimale elementen van ''V'', is als zodanig niet nodig, aangezien deze al bevat is in de tweede eis. Een minimaal element heeft immers geen voorganger, dus voor alle voorgangers is de uitspraak waar, en uit deze ware uitspraak moet de geldigheid voor het minimale element afgeleid worden.
===Volledige inductie===
{{Zie hoofdartikel|Volledige inductie}}
Volledige inductie is een methode om te bewijzen dat een uitspraak geldig is voor alle positieve, gehele getallen. Omdat er oneindig veel getallen zijn, kan een dergelijk bewijs niet voor elk getal afzonderlijk worden geleverd. Volledige inductie houdt in dat het bewijs eerst wordt geleverd voor het getal 1, de basisstap. Daarna wordt verondersteld dat de stelling geldig is tot en met het getal ''n'', dit is de inductieveronderstelling. Met de inductieveronderstelling als uitgangspunt wordt de inductiestap gedaan, er moet worden bewezen, dat als de uitspraak geldig is voor ''n'', de uitspraak ook geldig is ''n+1''. Wanneer het inductiebegin geldt en de basisstap kan worden uitgevoerd, is de stelling waar voor alle natuurlijke getallen. Met 1 in de eerste stap is de stelling waar voor alle positieve gehele getallen.
Een vorm van welgefundeerde inductie is het bekende principe voor de [[Natuurlijk getal|natuurlijke getallen]] van versterkte [[volledige inductie]], door sommige auteurs ook eenvoudigweg "volledige inductie genoemd". Het principe is gelijkwaardig aan (gewone) volledige inductie, wat dan ook wel eenvoudig als "inductie" wordt aangeduid.
In de formele rekenkunde wordt natuurlijke inductie gevat in een [[axioma]]schema.
Zij nu ''V'' een verzameling die welgefundeerd is ten opzichte van een relatie ''R''. Een volledig inductief bewijs van een stelling <math>\phi</math> over V verloopt nu in het algemeen zo:
# Bewijs <math>\phi</math> voor alle minimale elementen van ''V''
# Veronderstel nu dat <math>\phi</math> geldt voor een willekeurig element ''v'' van ''V''
# Bewijs nu dat als <math>\phi</math> geldt voor ''v'', dat <math>\phi</math> ook geldt voor de directe opvolger van ''v'' (en "directe opvolger" is een term die hier betekenis heeft door de aanwezigheid van de partiële ordening)
Nu is het bewijs klaar. Het bewijs ontstaat doordat <math>\phi</math> geldt voor het de minimale elementen van v en dat <math>\phi</math> geldt voor de opvolger van ieder element waar <math>\phi</math> voor geldt – zo ontstaat dus een keten van elementen waar <math>\phi</math> voor geldt, die zich uitstrekt van de minimale elementen van ''V'' tot en met alle elementen van ''V''.
===Voorbeeld 1===
''Stelling'': De som van de getallen <math>1,2,\dots,n</math> is <math>\frac{n(n+1)}{2}</math>
''Bewijs'' We bewijzen dit met natuurlijke inductie.
:''Basisstap'': Als <math>n=1</math>, is de som 1, wat inderdaad gelijk is aan <math>\frac{1\cdot(1+1)}{2}</math>.
:''Inductiestap'': Stel de stelling geldt voor zekere ''n'', dat wil zeggen <math>1+2+\dots+n=\frac{n(n+1)}{2}</math>. We moeten het nu bewijzen voor ''n+1'', dat wil zeggen, we moeten bewijzen dat <math>1+2+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}</math>.
:Dit bewijzen we aldus:
:<math>
\begin{matrix}
1+2+\ldots+n+(n+1)= \\
(1+2+\ldots+n)+(n+1)=
\end{matrix}
</math>
:(volgens de inductiehypothese)
:<math>
\begin{matrix}\frac{1}{2}n(n+1)+\frac{1}{2}\cdot2(n+1)= \\
\frac{1}{2}(n(n+1)+2(n+1))= \\
\frac{1}{2}(n+2)(n+1)= \\
\frac{1}{2}(n+1)(n+2)
\end{matrix}
</math>
Hiermee is het bewijs geleverd.
<br><br>
Opmerking: deze bewering is overigens ook rechtstreeks bewijsbaar als volgt:
:<math>
\begin{matrix}
1+2+\ldots+n= \\
\frac{1}{2}(1+2+\ldots+n) + \frac{1}{2}(n+\ldots+2+1)= \\
\frac{1}{2}((1+n) + (2+n-1) + \ldots + (n+1))= \frac{1}{2}n(n+1)\\
\end{matrix}
</math>
<br>
===Voorbeeld 2===
<br>
''Stelling'': Zij ''V'' de verzameling van natuurlijke getallen zonder 0 (dat wil zeggen <math> V = \N^{+}</math>). Deze verzameling is partieel geordend door de relatie <math>\leq</math>. Te bewijzen is nu dat voor ieder element ''n'' van <math>\N^{+}</math> geldt
:<math>\sum^{n}_{k = 1} k * k! = (n + 1)! - 1</math>
<br>
''Bewijs'':
<br>
:''Basisstap'': Het minimale element van <math>\N^{+}</math> is 1; er geldt
::<math>\sum^{1}_{k = 1} k * k! = 1 * 1! = 1 * 1 = 1 = 2 - 1 = (2 * 1) - 1 = 2! - 1 = (1 + 1)! - 1</math>
:dus dat klopt.
<br>
:''Inductiestap'': Veronderstel, voor getal ''n'' geldt de stelling.
: <math>
\begin{matrix}
\sum^{n + 1}_{k = 1} k * k! \\
= (n + 1) * (n + 1)! + \sum^{n}_{k = 1} k * k!
\end{matrix}
</math>
:(hieronder wordt de inductiehypothese toegepast)
:<math>
\begin{matrix}
= (n + 1) * (n + 1)! + (n + 1)! - 1 \\
= n * (n + 1)! + (n + 1)! + (n + 1)! - 1 \\
= n * (n + 1)! + 2(n + 1)! - 1 \\
= (n + 2)(n + 1)! - 1 \\
= (n + 2)! - 1
\end{matrix}
</math>
<br>
''of rechtstreeks''
<br>
:<math>
\begin{matrix}
n*n! + (n-1)*(n-1)! + (n-2)*(n-2)! + \ldots + 1*1!= \\
((n+1) - 1)*n! + (n - 1)*(n-1)! + ((n - 1) - 1)*(n-2)! + \ldots + (2 - 1)*1! = \\
(n+1)! - n! + n! - (n-1)! + (n-1)! - (n-2)! + \ldots + 2! - 1! = \\
(n+1)! - 1
\end{matrix}
</math>
<br>
Merk op dat in het bovenstaande voorbeeld in de inductiestap gebruik wordt gemaakt van de inductiehypothese om het bewijs te leveren: we laten zien dat de stelling geldt voor het volgende element, juist omdat het voor het voorgaande (laatste element van de inductiehypothese) geldt.
==Bewijs door versterkte volledige inductie==
Bewijs door versterkte volledige inductie lijkt heel erg op volledige inductie. Het principe van volledige inductie is dat de waarheid van een stelling over een verzameling bewezen kan worden door het bewijs van het basisgeval en het bewijs voor de opvolger:
:<math>(\phi(v_0) \wedge \phi(v_s) \Rightarrow \phi(v_{s + 1})) \Rightarrow \forall_{v \in V} : (\phi(v))</math>
Versterkte volledige inductie zegt nu dat als de waarheid van een stelling voor een willekeurig element volgt uit de waarheid van al zijn voorgangers, dat de stelling dan geldt voor alle elementen van de verzameling:
:<math>(\forall_{v \in V} : (\forall_{w \in V} : (w R^{*} v) \Rightarrow \phi(w)) \Rightarrow \phi(v)) \Rightarrow \forall_{v \in V} : \phi(v)</math>
Oftewel, als voor iedere v de stelling voor de aaneengesloten rij van alle voorgangers van v geldt en daarom ook voor het eerstvolgende element v, geldt de stelling voor de hele verzameling. Dit is bijna hetzelfde als volledige inductie, maar het schept de mogelijkheid om de waarheid van een stelling voor een hele verzameling te bewijzen door alleen naar de structuur te kijken en niet naar een bijzonder element.
Het is overigens bewijsbaar dat versterkte volledige inductie als principe volgt uit volledige inductie (maar niet erg makkelijk).
===Voorbeeld 3===
De Fibonacci-getallen zijn een reeks van getallen die als volgt gevormd worden:
:<math>a_1 = 1</math>
:<math>a_2 = 1</math>
:<math>\forall_{n>2}: a_n = a_{n-1} + a_{n-2}</math>
''Stelling'': Voor ieder natuurlijk getal ''n'' groter dan nul geldt, dat ''n'' een Fibonacci-getal is of de som van een aantal niet-opeenvolgende Fibonacci-getallen.
<br>
''Bewijs:''
<br>
''Gebruik volledige inductie naar de index <math>q</math> van de respectievelijke Fibonacci-getallen''
<br>
:''Basisstap'':
:<math>1 = a_2</math> is een Fibonaccigetal, <math>2 = a_3</math> ook.
:Laat <math>q</math> pas bij 3 beginnen te tellen.
<br>
:''Inductiestap''
:Bewijs dat wanneer voor alle getallen <math>n</math> tot en met het <math>q-de</math> Fibonaccigetal de stelling geldt, de stelling ook voor alle getallen tot en met het <math>q+1-de</math> Fibonaccigetal geldt.
:<math>n > a_q</math> vanwege de inductieveronderstelling.
:<math>n < a_{q+1}</math>, voor <math>n = a_{q+1}</math> is het geval triviaal.
:<math>a_q < n < a_{q+1} \Leftrightarrow 0 < n - a_q < a_{q+1} - a_q = a_{q-1}</math>,
:dus <math>n - a_q < a_{q-1}</math>.
:Nu de inductiehypothese:
:<math>a_q</math> komt wel voor in de rij Fibonaccigetallen, waarvan de som samen <math>n</math> is, maar <math>a_{q-1}</math> niet.
:Voor het verschil <math>n - a_q</math> kan de inductieveronderstelling worden toegepast.
:Samen betekent dit, dat de stelling voor alle getallen tot en met het Fibonaccigetal <math>a_{q+1}</math> geldt.
===Voorbeeld 4===
De [[determinant]] van Vandermonde van de orde is als volgt gedefinieerd
:<math>V_n = \begin{vmatrix}
1 & x_1 & x_1^2 & \cdots & x_1^{n-2} & x_1^{n-1} \\
1 & x_2 & x_2^2 & \cdots & x_2^{n-2} & x_2^{n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
1 & x_n & x_n^2 & \cdots & x_n^{n-2} & x_n^{n-1}
\end{vmatrix}
</math>
Het aantal variabelen <math>x_i</math> in deze determinant is <math>n</math>.
Voor deze determinant geldt:
:<math>\displaystyle V_n = \prod_{1 \le i < j \le n} \left({x_j - x_i}\right) </math>
Het bewijs van deze stelling gaat met volledige inductie naar het aantal variabelen <math>x_i</math> in de determinant.
Noot 4: In de wiskunde zijn er voor de twee stellingen uit de voorbeelden 3 en 4, geen andere stellingen die met behulp van één van deze twee worden bewezen.
==Structuurinductie==
In deelgebieden van de wiskunde waarin inductief gedefinieerde structuren, zoals termen of formules, een rol spelen, wordt ook vaak ''structuurinductie'' of ''structurele inductie'' toegepast. Een inductief gedefinieerde verzameling structuren bestaat uit een verzameling basisstructuren, die vervolgens wordt afgesloten onder een aantal operatoren. Het idee achter structuurinductie is nu dat als
#een stelling geldt voor alle mogelijke basisstructuren en
| 