triviale IMC combinatoriek

Opgave - IMC 2012 dag 1 vraag 1

We definieren $p(n)$ als het aantal manieren om $n$ te schrijven als de som van positieve getallen $\in \mathbb{N}.$
Bewijs dat $p(n)-p(n-1)$ gelijk is aan het aantal manieren om $n$ te schrijven als een som van positieve getallen $\in \{2,3,4,5\cdots \}.$

Oplossing

$p(n)$ is het aantal manieren $X$ waarop je $n$ kan schrijven zonder een $1$ te gebruiken opgetelt bij $Y$ manieren waarvoor je $1$ gebruikt.
Dus $p(n)=X+Y$

Als $p(n) - p(n-1)$ gelijk is aan het aantal manieren om $n$ te schrijven als een som van positieve getallen $\in \{2,3,4,5\cdots \}.$ , $X$ dus, dan is $p(n-1)$ het aantal manieren waarop je $n$ kan schrijven als som van getallen , en waar er minstens één $1$ in zit. $Y$ dus.
Want $p(n) - p(n-1) = X + Y - p(n-1)=X$

We moeten dus bewijzen dat $p(n-1)$ het aantal manieren is om $n$ als som van natuurlijke getallen (zonder 0) en met minstens een $1$ te schrijven.

We kunnen dit met de verschillende getallen a.
$a_1+a_2+...+a_x+1=n$

Stel er zo $Z$ verschillende combinaties voor de getallen $a$ zijn waarvoor dit klopt.

Vorm nu deze som om tot:
$a_1+a_2+...+a_x=n-1$

Omdat voor elke combinatie van a's dit ofwel niet geld, ofwel allebei geldt zijn hier ook $Z$ combinaties voor a. Maar omdat $Z$ hier het aantal combinaties is waarop $n-1$ geschreven kan worden geldt; $Z= p(n-1)$ en vanwege $Y=p(n-1)$ $=> Z=Y$.

We hebben echter al in de eerste alinea gesteld dat Y het aantal manieren is om de som van $n$ uit te schrijven met een $1$ erin.

Q.E.D.