alternerende rijen

Opgave - BrMO 1 1994 vraag 5

Een stijgende rij van gehele getallen wordt alternerend genoemd als ze start met een oneven term, de tweede term is even, de derde oneven, de vierde even, etc. De lege rij (met geen enkele term dus) wordt ook als alternerend beschouwd. Zij $A(n)$ het aantal alternerende rijen die enkel betrekking hebben op de verzameling $\{1,2,3,\cdots,n\}$. Toon aan dat $A(1)=2$ en $A(2)=3$. Vind ook de waarde van $A(20)$.

Oplossing

$A(1)=2$, want $\{\}, \{1\}$, $A(2)=3$, want $\{1,2\}$ komt er nog eens bij. Om $A(20)$ te zoeken zullen we een tabelletje opmaken.
Ik noem een rij even, als het laatste element even is (ledige verz=even). Hetzelfde voor oneven.
Voor $A(1) E=1, O=1, T(totaal)=2$
$A(2) E=2, O=1, T=3$ (Doordat er enkel een even element aan de rij kan toegevoegd worden, als het vroige element oneven is, moet je dus bij het bestaande aantal even rijen, het aantal oneven rijen optellen, en het aantal oneven rijen behouden.)
$A(3) E=2, O=3, T=5$ (volgens hetzelfde principe als hierboven)
$A(4) E=5, O=3, T=8$
.....
Op die manier zie je dat alle totalen fibonacci-getallen zijn, en omdat $A(1)$ het derde Fibonaci-getal is, is $A(20)$ het 22e fi-getal. Ligt rond de 16000(geen zin om te berekenen).