Fundamenten uitwerkingen inleveropgave week 8
19 november 2021
Inleveropgave:
Gegeven en te bewijzen opschrijven: 1pt
Gegeven: de rij (an )n∈N gedefinieerd door a1 = 1, a2 = 1 en an + 2 = an+1 + an voor
n ∈ N.
Te bewijzen (via volledige inductie): ggd(an+1 , an ) = 1 voor n ∈ N.
Bewijs. .
Een inductiebegin geven : 1pt, ook juist uitvoeren: 1pt (totaal 2pt).
Als inductiebegin moeten we aantonen dat ggd(a2 , a1 ) = 1.
Aangezien ggd(a2 , a1 ) =ggd(1, 1) = 1 geldt inderdaad dat de stelling waar is voor n = 1.
Voor n = 2 merken we op dat ggd(a3 , a2 ) =ggd(2, 1) = 1.
Een correcte inductiehypothese geven : 1,5pt.
We nemen nu aan dat voor n = k met een vaste, doch willekeurige k ∈ N≥2 , er geldt dat
ggd(ak+1 , ak ) = 1.
Inductiestap : 4pt
We bekijken nu ggd(ak+2 , ak+1 ) =ggd(ak+1 +ak , ak+1 ). We merken op dat rest van ak+1 +ak na
deling door ak+1 gelijk is aan ak dit aangezien ak+1 > ak (hierom hebben we ook het geval n =
2 apart bekeken en k ∈ N≥2 genomen). Dus geeft Lemma V.3.6 dat ggd(ak+2 , ak+1 ) =ggd(ak+1 +
ak , ak+1 ) = ggd(ak+1 , ak ). Uit de inductiehypothese volgt ggd(ak+2 , ak+1 ) = ggd(ak+1 , ak ) =
1.
Daarmee is de stelling ook waar voor n = k + 1.
Uiteindelijke conclusie geven en benoemen dat deze uit inductie volgt : 1,5pt.
Uit inductie volgt nu dat ggd(an+1 , an ) = 1 voor elke n ∈ N.
1
19 november 2021
Inleveropgave:
Gegeven en te bewijzen opschrijven: 1pt
Gegeven: de rij (an )n∈N gedefinieerd door a1 = 1, a2 = 1 en an + 2 = an+1 + an voor
n ∈ N.
Te bewijzen (via volledige inductie): ggd(an+1 , an ) = 1 voor n ∈ N.
Bewijs. .
Een inductiebegin geven : 1pt, ook juist uitvoeren: 1pt (totaal 2pt).
Als inductiebegin moeten we aantonen dat ggd(a2 , a1 ) = 1.
Aangezien ggd(a2 , a1 ) =ggd(1, 1) = 1 geldt inderdaad dat de stelling waar is voor n = 1.
Voor n = 2 merken we op dat ggd(a3 , a2 ) =ggd(2, 1) = 1.
Een correcte inductiehypothese geven : 1,5pt.
We nemen nu aan dat voor n = k met een vaste, doch willekeurige k ∈ N≥2 , er geldt dat
ggd(ak+1 , ak ) = 1.
Inductiestap : 4pt
We bekijken nu ggd(ak+2 , ak+1 ) =ggd(ak+1 +ak , ak+1 ). We merken op dat rest van ak+1 +ak na
deling door ak+1 gelijk is aan ak dit aangezien ak+1 > ak (hierom hebben we ook het geval n =
2 apart bekeken en k ∈ N≥2 genomen). Dus geeft Lemma V.3.6 dat ggd(ak+2 , ak+1 ) =ggd(ak+1 +
ak , ak+1 ) = ggd(ak+1 , ak ). Uit de inductiehypothese volgt ggd(ak+2 , ak+1 ) = ggd(ak+1 , ak ) =
1.
Daarmee is de stelling ook waar voor n = k + 1.
Uiteindelijke conclusie geven en benoemen dat deze uit inductie volgt : 1,5pt.
Uit inductie volgt nu dat ggd(an+1 , an ) = 1 voor elke n ∈ N.
1
