Samenvatting getaltheorie
Volledige inductie
Voor volledige inductie hebben wij het volgende stappenplan:
1. Beginconditie; toon aan dat P(0) (de laagst mogelijke waarde) waar is.
2. Inductie stap;
a. Neem aan dat P(k) waar is.
b. Toon aan dat P(k+1) waar is.
3. Conclusie; de bewering P(n) geldt voor alle n.
Voorbeeld
n ( n+1 )
Stelling: bewijs dat 1+2+3+…+ n=
2
Bewijs:
2
1. P ( 1 ) : 1= → 1=1, dit klopt. (Let op dat je P(x): schrijft en niet P(x)=)
2
k ( k +1 )
2. Neem aan dat P ( k ) : 1+ 2+ 3+…+ k= klopt.
2
Toon aan dat P ( k +1 ) klopt:
( k +1 ) ( ( k +1 ) +1 ) k ( k +1 ) ( k +1 ) ( ( k +1 ) +1 )
1+2+3+…+ k + ( k +1 )=? + ( k +1 )=?
2 2 2
k ( k +1 ) 2 ( k + 1 ) ( ( k +1 )+ 1 ) k ( k +1 ) 2 ( k +1 ) ( k + 1 ) ( ( k +1 )+ 1 )
+ ( k +1 )=? + =?
2 2 2 2 2 2
k ( k +1 )+ 2 ( k +1 )=? ( k + 1 )( k + 2 )k 2+ k +2 k +2=? k 2 +2 k +k +2k 2+3 k + 2=k 2 +3 k + 2
n ( n+1 )
3. Conclusie: 1+2+3+…+ n= klopt voor elke n.
2
, Deelbaarheid
Als er een d bestaat, die n deelt zodat er een heel getal uit komt, schrijven wij dit op
als: d∨n‘d is een deler van n’. Bijvoorbeeld: 4∨56 , want 56=4 ∙16 .
Het bewijzen van deelbaarheid doen wij zo:
Stelling: voor elke n, als 4|n, dan 2|n. (voor elke n, als 4 een deler is van n, dan is 2
ook een deler van n)
Bewijs: neem n willekeurig
Stel: 4|n
Bepaal een k, zodat n=4 ∙ k
Dan: n=2∙ 2 ∙ k
n=2∙( 2k ) 2k = l
n=2l
Dus: 2|n
Lijstje met standaardregels die je moet kennen:
Volledige inductie
Voor volledige inductie hebben wij het volgende stappenplan:
1. Beginconditie; toon aan dat P(0) (de laagst mogelijke waarde) waar is.
2. Inductie stap;
a. Neem aan dat P(k) waar is.
b. Toon aan dat P(k+1) waar is.
3. Conclusie; de bewering P(n) geldt voor alle n.
Voorbeeld
n ( n+1 )
Stelling: bewijs dat 1+2+3+…+ n=
2
Bewijs:
2
1. P ( 1 ) : 1= → 1=1, dit klopt. (Let op dat je P(x): schrijft en niet P(x)=)
2
k ( k +1 )
2. Neem aan dat P ( k ) : 1+ 2+ 3+…+ k= klopt.
2
Toon aan dat P ( k +1 ) klopt:
( k +1 ) ( ( k +1 ) +1 ) k ( k +1 ) ( k +1 ) ( ( k +1 ) +1 )
1+2+3+…+ k + ( k +1 )=? + ( k +1 )=?
2 2 2
k ( k +1 ) 2 ( k + 1 ) ( ( k +1 )+ 1 ) k ( k +1 ) 2 ( k +1 ) ( k + 1 ) ( ( k +1 )+ 1 )
+ ( k +1 )=? + =?
2 2 2 2 2 2
k ( k +1 )+ 2 ( k +1 )=? ( k + 1 )( k + 2 )k 2+ k +2 k +2=? k 2 +2 k +k +2k 2+3 k + 2=k 2 +3 k + 2
n ( n+1 )
3. Conclusie: 1+2+3+…+ n= klopt voor elke n.
2
, Deelbaarheid
Als er een d bestaat, die n deelt zodat er een heel getal uit komt, schrijven wij dit op
als: d∨n‘d is een deler van n’. Bijvoorbeeld: 4∨56 , want 56=4 ∙16 .
Het bewijzen van deelbaarheid doen wij zo:
Stelling: voor elke n, als 4|n, dan 2|n. (voor elke n, als 4 een deler is van n, dan is 2
ook een deler van n)
Bewijs: neem n willekeurig
Stel: 4|n
Bepaal een k, zodat n=4 ∙ k
Dan: n=2∙ 2 ∙ k
n=2∙( 2k ) 2k = l
n=2l
Dus: 2|n
Lijstje met standaardregels die je moet kennen:
