Gebruiker:Patrick/inductie

inductie (wiskunde)
Volledige inductie

k variabel

I. Als $E(k)$, en voor $m$ = $k$ t/m $n-1$ geldt $E(m)\rightarrow E(m+1)$, dan geldt $E(m)$ voor $m$ = $k$ t/m $n$.

II. Als $F(k)$, en voor $m$ >= $k$ geldt $F(m)\rightarrow F(m+1)$, dan geldt $F(m)$ voor $m$ >= $k$.

Neem aan II. Neem aan dat E voldoet aan de voorwaarde van I, dus $E(k)$, en voor $m$ = $k$ t/m $n-1$ geldt $E(m)\rightarrow E(m+1)$.

Neem $F(m)$ voor alle $m$ = $k$ t/m $n$ gelijk aan $E(m)$ en voor m>n waar.

Dan $F(k)$, en voor $m$ = $k$ t/m $n-1$ geldt $F(m)\rightarrow F(m+1)$, want voor m<=n zijn $E(m)$ en $F(m)$ gelijk.

Voor m >= n geldt $F(m)\rightarrow F(m+1)$, want $F(m+1)$ is dan waar.

Aan de voorwaarde van II is dus voldaan, dus $F(m)$ voor $m$ >= $k$, en dus $E(m)$ voor $m$ = $k$ t/m $n$.

Conclusie: uit II volgt I.

Neem nu aan I. Neem aan dat F voldoet aan de voorwaarde van II, dus $F(k)$, en voor $m$ >= $k$ geldt $F(m)\rightarrow F(m+1)$,

Neem $E(m)$ voor alle voor alle $m$ = $k$ t/m $n$ gelijk aan $F(m)$. Dan $E(m)$ voor $m$ = $k$ t/m $n$, dus $F(m)$ voor $m$ = $k$ t/m $n$.

Dit geldt voor iedere n>=k.

Conclusie: uit I volgt II.

k=0 en preciezer

I. Voor elk geheel getal n>=0 en elke boolean functie E op {0,1,..n} geldt: Als $E(0)$, en voor $m$ = $0$ t/m $n-1$ geldt $E(m)\rightarrow E(m+1)$, dan geldt $E(m)$ voor $m$ = $0$ t/m $n$.

II. Voor elke boolean functie F op {0,1,2,..} geldt: Als $F(0)$, en voor $m$ >= $0$ geldt $F(m)\rightarrow F(m+1)$, dan geldt $F(m)$ voor $m$ >= $0$.

Neem aan II. Neem aan dat E voldoet aan de voorwaarde van I, dus $E(0)$, en voor $m$ = $0$ t/m $n-1$ geldt $E(m)\rightarrow E(m+1)$.

Neem $F(m)$ voor alle $m$ = $0$ t/m $n$ gelijk aan $E(m)$ en voor m>n waar.

Dan $F(0)$, en voor $m$ = $0$ t/m $n-1$ geldt $F(m)\rightarrow F(m+1)$, want voor m<=n zijn $E(m)$ en $F(m)$ gelijk.

Voor m >= n geldt $F(m)\rightarrow F(m+1)$, want $F(m+1)$ is dan waar.

Aan de voorwaarde van II is dus voldaan, dus $F(m)$ voor $m$ >= $0$, en dus $E(m)$ voor $m$ = $0$ t/m $n$.

Conclusie: uit II volgt I.

Neem nu aan I. Neem aan dat F voldoet aan de voorwaarde van II, dus $F(0)$, en voor $m$ >= $0$ geldt $F(m)\rightarrow F(m+1)$,

Neem $E(m)$ voor alle voor alle $m$ = $0$ t/m $n$ gelijk aan $F(m)$. Dan $E(m)$ voor $m$ = $0$ t/m $n$, dus $F(m)$ voor $m$ = $0$ t/m $n$.

Dit geldt voor iedere n>=0.

Conclusie: uit I volgt II.

Toepassingen

Gevallen waaein $E(m)\rightarrow E(m+1)$ gemakkelijker te bewijzen is dan $E(m+1)$ rechtstreeks.