Jeroen's Studie Archief
Bewijzen in de wiskunde 30 september 2024

Sterke inductie en relaties

Minimaal tegenvoorbeeld

Als je een bewering van de vorm ∀n∈N:P(n)\forall n \in N : P(n) wilt bewijzen, kun je gebruik maken van het minimale tegenvoorbeeld. Hierbij neem je aan dat er een kleinste getal m∈Nm\in\N bestaat waarvoor P(m)P(m) niet waar is. Het doel is om dan uit te komen op een contradictie.

Stelling

∀n∈N:6∣n3−n \forall n \in \N : 6 | n^3 - n

Bewijs

Bij contradictie, neem aan dat er een n∈Nn\in\N bestaat waarvoor 6∤n3−n6 \nmid n^3 - n. Dan bestaat er een kleinste m∈Nm\in\N waarvoor 6∤m3−m6 \nmid m^3 - m. Omdat 6∣13−1=06|1^3-1=0 en 6∣23−2=66|2^3-2=6, moet gelden dat m≥3m \ge 3. Dan schrijven we m=k+2m=k+2 voor een k∈Nk\in\N met 1≤k<m1 \le k < m. Nu geldt:

m3−m=(k+2)3−(k+2)=k3−k+6(k2+2k+1) m^3-m = (k+2)^3-(k+2) = k^3-k+6(k^2+2k+1)

Omdat k<mk<m en mm het kleinste getal is waarvoor 6∤m3−m6 \nmid m^3-m, geldt dat 6∣k3−k6|k^3-k. We schrijven kk dus als 6x6x voor een x∈Zx\in\Z. Dit geeft:

m3−m=6x+6(k2+2k+1) m^3-m = 6x + 6(k^2+2k+1)

En omdat x,k2+2k+1∈Zx, k^2+2k+1 \in \Z, concluderen we dat 6∣m3−m6|m^3-m. Dit is een contradictie. QED.

Sterke inductie

Sterke inductie is een uitbreiding op normale inductie, en gaat alsvolgt:

Laat P(n)P(n) een bewering zijn met domein N\N. Als (1) P(1)P(1) waar is en (2) ∀k∈N:(P(1)∧P(2)∧...∧P(k))  ⟹  P(k+1)\forall k \in \N : \big(P(1) \land P(2) \land ... \land P(k)\big) \implies P(k+1) waar is, geldt ∀n∈N:P(n)\forall n \in \N: P(n).

Stelling

Laat ana_n recursief gedefiniëerd zijn door a1=1a_1=1, a2=3a_2=3 en an=2an−1−an−2a_n = 2a_{n-1} - a_{n-2} voor n≥3n \ge 3. Dan geldt an=2n−1a_n=2n-1 voor alle n∈Nn\in\N.

Bewijs

Met sterke inductie op nn, bewijzen we (1) 1=2(1)−11=2(1)-1 en 2=2(2)−12=2(2)-1, en (2) ∀k∈N:(a1=2(1)−1∧a2=2(2)−1∧...∧ak=2k−1)  ⟹  ak+1=2(k+1)−1\forall k \in N : (a_1=2(1)-1 \land a_2=2(2)-1 \land ... \land a_k=2k-1) \implies a_{k+1} = 2(k+1)-1.

(1) Er geldt 2(1)−1=12(1)-1=1 en 2(2)−1=32(2)-1=3, dus dit klopt.

(2) Laat k∈Nk\in\N. We nemen aan dat ai=2i−1a_i=2i-1 geldt voor elke i∈Ni\in\N waarvoor i<ki<k. Er geldt:

ak=2ak−1−ak−2=IH2(2(k−1)−1)−(2(k−2)−1)=2k−1 \begin{aligned} a_k &= 2a_{k-1}-a_{k-2} \\ &\stackrel{IH}= 2(2(k-1)-1) - (2(k-2)-1) \\ &= 2k-1 \end{aligned}

QED.

Relaties

Voor verzamelingen AA en BB is een relatie RR van AA naar BB een deelverzameling van A×BA \times B. Als (a,b)∈R(a,b) \in R, zeggen we dat aa gerelateerd is aan bb, notatie aRbaRb.

Voor een relatie RR van AA naar BB geldt dat het domein, notatie dom(R)\text{dom}(R), en het bereik, notatie range(R)\text{range}(R), gelijk zijn aan:

dom(R)={a∈A:(a,b)∈R voor een b∈B} \text{dom}(R) = \{ a \in A : (a, b) \in R \text{ voor een } b \in B \}

range(R)={b∈B:(a,b)∈R voor een a∈A} \text{range}(R) = \{ b \in B : (a, b) \in R \text { voor een } a \in A \}

Voorbeeld

Gegeven zijn A={1,2,3}A=\{1,2,3\}, B={x,y}B=\{x,y\} en R={(2,x),(1,y),(2,y)}R=\{(2,x),(1,y),(2,y)\}. Er geldt R⊆A×BR \subseteq A \times B, dus RR is een relatie van AA naar BB.

Hier geldt dat dom(R)={1,2}\text{dom}(R) = \{1,2\} en range(R)={x,y}\text{range}(R) = \{x,y\}.

De inverse van een relatie RR van AA naar BB, notatie R−1R^{-1}, is een relatie van BB naar AA, zodat:

R−1={(b,a):(a,b)∈R} R^{-1} = \{ (b,a) : (a,b) \in R \}

Relaties op verzamelingen

Een relatie RR op een verzameling AA is een relatie van AA naar AA, oftewel R⊆A×AR \subseteq A \times A.

Laat RR een relatie zijn op AA. Dan is RR:

  • Reflexief precies als aRaaRa voor alle a∈Aa \in A.
  • Symmetrisch precies als aRb  ⟹  bRaaRb \implies bRa voor alle a,b∈Aa,b \in A.
  • Transitief precies als (aRb∧bRc)  ⟹  aRc(aRb \land bRc) \implies aRc voor alle a,b,c∈Aa,b,c \in A.

Voorbeeld

Laat RR de relatie zijn op R\R zodat aRbaRb precies als ∣a−b∣≤1|a-b|\le1. Dan is RR wel reflexief, wel symmetrisch, maar niet transitief.

Gemaakt door Jeroen van Rensen.