bitstrings

Voor $n=1$ hebben we $s(1)=1$ en $s(2)=0$ dus het klopt.
Laat $n>1$.

Veronderstel dat $s(p)$ en $s(q)$ gelijk zijn, dat $0< p< q$ en dat $(a,b)$ het koppel getallen $(p,q)$ is waarvoor het grootste van de twee, $b$, van alle $q$ de kleinste is. Dus voor alle koppels $(p,q)$ geldt dat $q\geq b$.

Het is onmogelijk dat $s(a)$ en $s(b)$ beide eindigen op een $1$ omdat een $1$ alleen wordt toegevoegd als de resulterende bitstring nog niet bestaat.
Dus $s(a)$ en $s(b)$ eindigen allebei op een $0$.

Stel daarom $s(a)=s(b)=t0$ met $t$ een bitstring van lengte $n-1$.
Omdat $b$ minimaal is moeten $s(a-1)$ en $s(b-1)$ verschillend zijn, dus $s(a-1)=et$ en $s(b-1)=ft$ met $e\neq f$ en $e$, $f$ beide $0$ of $1$.
Omdat $s(a)$ eindigt op $0$ zijn er twee mogelijkheden:

• Er moet er al een $c< a$ zijn geweest waarvoor $s(c)=t1$, en dus $s(c-1)=gt$ met $g$ opnieuw $0$ of $1$.Omdat $e\neq f$ moet $g=e$ of $g=f$, dus $s(c-1)=s(a-1)$ (met $a-1> c-1$) of $s(c-1)=s(b-1)$ (met $b-1>c-1$ want $b>a>c$) maar in beide gevallen is $ a-1< b $ en $b-1< b$ dus was $b$ toch niet de minimale waarde. Er is dus geen minimale waarde voor $b$, dus is er ook geen $b$ mogelijk. De bitstring $t0$ komt dus toch geen twee keer voor.
• Of, $t$ is een reeks van alleen maar nullen. (Hier kunnen we dus niet met zekerheid een $c$ vinden omdat $s(1)=00..001$ en $c=1$ mag niet want dan is $s(c-1)$ niet gedefinieerd.)

We kunnen dus besluiten dat als een bepaalde bitstring $x$ twee keer voorkomt, dat dan $x=00..00$. $(*)$.

Dit betekent dat er zeker een $a\leq2^n$ is zodat $s(a)=00..00$. Zoniet zouden er van de eerste $2^n$ bitstrings zeker twee gelijk zijn wegens het duivenhokprincipe, maar wegens (*) dat kan niet. $(**)$

Vervolgens bewijzen we dat alle bitstrings voorkomen.
Merk op dat een bepaalde bitstring $x0$ (Met $x\neq00..00$) slechts kan voorkomen als zowel $1x$ als $0x$ al zijn voorgekomen, want wegens (*) is het onmogelijk dat $1x$ of $0x$ tweemaal voorkomt.

Dit betekent dat als een bitstring $x=x_1x_2\cdots x_n$ (met $x_i$ telkens gelijk aan $0$ of $1$ en $x\neq00..00$) niet voorkomt, ook $x_2x_3\cdots x_n0$ niet voorkomt.
Dus dan is ofwel $x_2=x_3=\cdots=x_n=0$, ofwel komt ook $x_3x_4\cdots x_n00$ niet voor.

Dan is opnieuw ofwel $x_3=x_4=\cdots=x_n=0$, ofwel komt $x_4x_5\cdots x_n000$ niet voor.
Enzovoort, tot uiteindelijk $x_n=0$ ofwel komt $00..00$ niet voor.
Dus vinden we uiteindelijk dat in elk geval de bitstring $00..00$ niet voorkomt.
Dit is in tegenstrijd met (**), dus onze veronderstelling dat de bitstring $x$ niet voorkomt is fout. Bijgevolg komt elke bitstring voor.

Aangezien er $2^n$ mogelijke bitstrings zijn en deze allemaal ergens voorkomen moeten deze voorkomen bij de bitstrings $s(1),\cdots s(2^n)$ omdat na $00..00$ hetzelfde blijft komen en omdat $00..00$ te laatste als $2^n$-de voorkomt wegens (**).
Bijgevolg zijn de bitstrings $s(1)$ tot $s(2^n)$ alle verschillend.