univ-vraag van op vwo-stage

We kunnen dit probleem op 2 manieren oplossen:

Manier 1
Inductiebasis:
n=1:1.
n=2:1+1, 2.
n=3:1+1+1 ,1+2, 3.

Inductiehypothese: $n$ kan op $n$ verschillende manieren geschrijven worden als zo'n som, waarbij $k$ van $1$ tot $n$ gaat

Stel nu dat n op k verschillende manieren geschreven kan worden zoals in de opgave.
Dan kan n+1 op k+1 verschillende manieren zo geschreven worden want:
Elke combinatie van n bestaat een een bepaald aantal keren een getal $g$, en een aantal keren $g+1$ (evt. $0$ keer). Als we nu een getal $g$ vervangen door $g+1$, dan wordt de som $n+1$, en voldoet ze nog steeds aan de opgave.
We hebben dus al een manier voor $k$ van $1$ tot $n$.
Maar men kan ook de som van n+1 keer een 1 optellen voor $k=n+1$. Dit voldoet ook aan de opgave.
Er zijn dus minimum k+1 mogelijkheden.

Nu moeten we nog bewijzen dat dit het maximum is. Daarom denken we in de omgekeerde volgorde: als n+1 geschreven kan worden op j+1 manieren, dan kan men voor elke manier bij de "hogere" getallen 1 aftrekken. We krijgen dan echter wel 1 dubbel: n keren 1 (van n+1 keren 1 en n-2 keren 1+2). Deze telt natuurlijk niet dubbel, dus kunnen we besluiten dat n op minimaal j manieren geschreven kan worden.

Reden dat er maar $1$ dubbel is:
Stel dat a en b 2 verschillende combinaties zijn voor n+1. Dan zijn er minstens 2 getallen in deze combinatie verschillend, want moest er maar 1 getal verschillen, dan zou de som duidelijk verschillend zijn. Als men nu van 1 van de "grotere" getallen in elke combinatie 1 aftrekt, dan blijft er minstens 1 verschil bestaan. Dit geldt niet voor de rij van allemaal enen, omdat 1-1=0, en 0 is het neutraal getal van de optelling (en mag je dus schrappen).

We weten echter dat n op k manieren geschreven kan worden. Dus j$\le$k.
We weten ook dat n+1 op j+1 manieren geschreven kan worden, en minimum k+1 manieren. Dus $k+1\lej+1.$

Hieruit volgt dat k=j. Omdat nu het minimum gelijk wordt aan het maximum, kunnen we besluiten dat men n op n manieren volgens de opgave kan schrijven.

Manier 2
Beschouw: $n=p.q+r$ met n,p,q,r $\in \mathbb{N}$ en met p$\le$n en r kleiner dan p.
Dit is ook gekend als de euclidische deling.
Voor iedere 1$\le$p$\le$n, kan je n naar de opgave schrijven als een reeks van p getallen: r hiervan zijn gelijk aan q+1. De rest is gelijk aan q.
Dus $pq+r = r*(q+1) + (p-r)*q$

Er zijn dus minimum n oplossingen. Nu moeten we nog bewijzen dat voor elke p (de lengte van de som), er maar 1 oplossing is.

Merk hiervoor op dat als $a_1+a_2+\cdots+a_p=pq+r$ dat $min(a_1,a_2,\cdots,a_p)=q.$
Want $$a_1+a_2+\cdots+a_p \le min(a_1,a_2,\cdots,a_p)+(p-1)(min(a_1,a_2,\cdots,a_p)+1) \le pq-1$$ als dat minimum $ \le q-1$ is.
Als dat minimum groter is dan $q$ geldt, $$a_1+a_2+\cdots+a_p \ge p*min(a_1,a_2,\cdots,a_p)\ge p(q+1)= pq+p>pq+r=n$$

We weten dus dat we enkel getallen van de vorm $q$ en $q+1$ hebben en dus $s(q+1)+(p-s)q=pq+r$ zodat $r=s$ de enige oplossing is.

Er is dus voor elke p maar 1 oplossing.
Dus voor elke n $\in \mathbb{N}$ zijn er $n$ oplossingen.