WEEK 1

Volledige inductie

Volledige inductie is een bewijsmethode om een uitspraak over alle natuurlijke getallen te bewijzen. Er wordt verwacht dat je deze methode begrijpt en kunt toepassen.

Kern:
	§2 van de reader
Extra ondersteuning:
	Volledige inductie
	Agendeer dit thema voor de bijeenkomst

Deelbaarheid

Zorg dat je in algoritmes en bewijzen concepten rond deelbaarheid soepel kunt gebruiken: delen met rest, deelbaarheid, de notatie $d|n$, priemgetal, grootste gemene deler ($\ggd$). Daarnaast wordt verwacht dat je Euclides' bewijs dat er oneindig veel priemgetallen zijn doorgrondt.

Kern:
	§3 van de reader
Extra ondersteuning:
	Voorbeeld van gebruik van deelbaarheid in bewijzen: de somregel voor delers.
	§2.1, §1.3, definitie 1.16 en stelling 1.21 in het boek van De Weger
	Agendeer dit thema voor de bijeenkomst

Stelling van Bézout

De Stelling van Bézout zegt dat de grootste gemene deler van $x$ en $y$ te schrijven is als lineaire combinatie: $\ggd(x,y)=ax+by$ met $a,b\in\ZZ$. Het is een centrale stelling in deze cursus en er wordt van je verwacht dat je de stelling zowel kunt toepassen, als het bewijs kunt analyseren.

Kern:
	§4 van de reader
Extra ondersteuning:
	De Stelling van Bézout
	In stelling 1.21 in het boek van De Weger is de Stelling van Bézout herkenbaar
	Agendeer dit thema voor de bijeenkomst

Opgave 1

Bewijs met volledige inductie: Voor alle $n\in\NN$ geldt $7|3^{2n+1}+2^{n+2}$.

	Loop je vast? Probeer de heuristiekboom!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 2

In §2 van de reader staat het afsnoeplemma. Dit lemma zegt dat voor alle $n\in\NN_{\ge1}$ en alle $x\in\RR\setminus\{1\}$ geldt $$x^0+x^1+\cdots+x^{n-1}={x^{n}-1\over x-1}.$$

1. Lees het bewijs in de reader door. Leg hem daarna weg en probeer het bewijs te reproduceren.
2. Een alternatieve manier van bewijzen is door de te bewijzen gelijkheid links en rechts met $x-1$ te vermenigvuldigen en dan haakjes uit te werken. Schrijf dit bewijs ook uit. In hoeverre heb je hierbij volledige inductie nodig?

	De uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 3

Bewijs: Voor alle $n\in\NN\setminus\{0\}$ geldt $1+3+5+\cdots+(2n-1)=n^2$.

	Loop je vast? Probeer de heuristiekboom!
	Minder leerzaam: de uitwerking
	Deze opgave is voorgedaan in het filmpje dat al is langsgekomen.
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 4

Bewijs: Voor alle $n\in\NN\setminus\{0\}$ geldt $$1^3+2^3+3^3+\cdots+n^3=\left({\frac{n(n+1)}{2}}\right)^2.$$

	Loop je vast? Probeer de heuristiekboom!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 5

Zij $d,a,b\in\ZZ_{>0}$ en stel dat $d=\ggd(a,b)$. Bewijs dat $\frac ad$ en $\frac bd$ geheel en copriem zijn.

	Loop je vast? Probeer de heuristiekboom!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 6

1. Laat zien dat $\ggd(a,b)=\ggd(b,a-b)$ voor alle $a,b\in\NN$ niet beide nul.
2. Bepaal de ggd van $3^{10000000}+2^{10000000}$ en $3^{10000000}-2^{10000000}$

	Loop je vast? Probeer de heuristiekboom bij deel a en bij deel b!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 7

Bekijk de stelling van Bézout in §4 van de reader.

1. In het bewijs staat dat $W$ een verschilverzameling is. Is het echter ook een somverzameling? Dat wil zeggen: geldt voor ieder tweetal $z_1,z_2\in W$ dat $z_1+z_2\in W$? Bewijs of weerleg je uitpraak.
2. Waarom zijn in deel (i) van het bewijs in de reader de absoluut-strepen nodig?
3. Verderop in deel (i) staat: 'Als $r\not=0$ dan $r=z-qc\in W$'. Werk de details van het bewijs hiervan uit.

	Loop je vast? Probeer de heuristiekboom bij deel a!
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst

Opgave 8

Gegeven $m\in\ZZ$ positief. Er geldt:

$2^m+1$ is priem $\qquad\Rightarrow\qquad m=2^n$ voor $n\ge0$.

In reuzenstappen gaat het bewijs als volgt. Neem maar aan dat $m$ een oneven priemdeler $p$ heeft. Dan geldt $$(2^m+1)=(2^{m/p}+1)(2^{m-m/p}-2^{m-2m/p}+2^{m-3m/p}-\cdots-2^{m/p}+1)$$ en dus heeft $2^m+1$ een echte deler en is het dus niet priem.

1. Schrijf het bewijs uit en vul de ontbrekende details in. Waarom werkt het argument niet voor $p=2$?

Een fermatgetal is een getal $F_n$ van de vorm $$F_n=2^{2^n}+1\qquad(n\in\NN).$$

2. Bewijs met volledige inductie dat voor iedere $n\ge1$: $$\prod_{k=0}^{n-1}F_k=F_n-2.$$(De $\prod$-notatie aan de linkerkant staat voor het product $F_0F_1\ldots F_{n-1}$.)
3. Bewijs dat ieder tweetal verschillende fermatgetallen $F_m$ en $F_n$ (met $m<n$) copriem is.
4. Bewijs met behulp van het vorige onderdeel dat er oneindig veel priemgetallen zijn.

Fermat dacht dat alle fermatgetallen priem zijn. Voor $n=0,\ldots,4$ is dat inderdaad het geval, maar Euler liet zien dat $F_5$ geen priemgetal is. Er geldt namelijk: $$F_5=4294967297=641\cdot 6700417.$$ Het is niet bekend of er boven $n=4$ fermatpriemgetallen zijn. Een beroemd resultaat van Gauss zegt dat een regelmatige $k$-hoek construeerbaar is met passer en latje precies dan als $k$ een product is van fermatpriemgetallen en een macht van $2$.

5. Leg uit dat het feit dat $F_5$ geen priemgetal is niet in tegenspraak is met hetgeen je in onderdeel (a) hebt bewezen.

	Loop je vast? Probeer de heuristiekboom bij onderdeel a, bij onderdeel b en bij onderdeel c
	Minder leerzaam: de uitwerking
	Agendeer deze vraag voor de komende bijeenkomst