Inverse en complementaire rijen

 

Gegeven is een rij f(n) met n=0,1,2,.... Definieer dan

    \[g(n)=k \text{ als } f(k)<n\leq f(k+1)\]

Een voorbeeld: f(n)=0,0,0,1,2,3,3,4,5,6,7,10,… dan is g(n)=3,4,5,7,8,9,10,11,11,11

  • g(n) is eigenlijk het aantal termen in de rij f(n) die kleiner zijn dan n.
  • Als we op g(n) dezelfde procedure toepassen als op f(n), dan bekomen we terug f(n). Vandaar dat we g(n) de inverse rij van f(n) noemen.

Construeer nu volgende twee rijen: F(n)=f(n)+n en G(n)=g(n)+n. In ons voorbeeld is F(n)=1,2,3,5,7,9,10,12,14,...  en G(n)=4,6,8,11,13,15,17,19,20,.... Wat stellen we nu vast? De twee rijen F(n) en G(n) bevatten samen juist 1 keer elk positief natuurlijk getal. Dit feit en het omgekeerde werden ontdekt en bewezen in 1954 door de wiskundigen Lambek (zie hieronder)  en Moser,onder de voorwaarden dat(n)eng(n)niet-dalenderijen zijn van natuurlijke getallen.

De rijen F(n) en G(n) noemen we complementaire rijen.

Als het expliciet voorschrift van een rij gekend is,  kunnen we deze stelling gebruiken om het voorschrift te bepalen van de complementaire rij.  Zo kunnen we de natuurlijke getallen bijvoorbeeld opsplitsen in 2 rijen F(n) van de kwadraten en G(n) van de niet kwadraten: F(n)=1,4,9,16,25,... en G(n)=2,3,5,6,7,8,10,.... We weten dat F(n)=n^2. Wat is nu het voorschrift van G(n)? 

F(n) en G(n) zijn complementair en dus zijn f(n)=F(n)-n=0,2,6,12,20,... en g(n)=G(n)-n=1,1,2,2,2,2,3,... elkaars inverse. Nu is f(n-=n^2-n . Dan is g(n)=k als en slechts als f(k)<n\leq f(k+1) of m.a.w. k^2-k<n\leq k^2+k. Omdat n en k een natuurlijke getallen zijn is dan ook k^2-k+\frac{1}{4}<n< k^2+k\frac{1}{4}. Hieruit volgt dan uiteindelijk dat \sqrt{n}-\frac{1}{2}<k<\sqrt{n}+\frac{1}{2}. Dus : g(n)=\lfloor \sqrt{n}+\frac{1}{2} \rfloor en

    \[G(n)=n+\lfloor \sqrt{n}+\frac{1}{2} \rfloor\]