Jelöljük $A_n$-nel a keresett számot. Megmutatjuk, hogy $n⩾3$ esetén $A_n=A_{n-1}+A_{n-2}+1$.
Soroljuk a sorozatokat három osztályba:
1. A nem $n$-re végződő sorozatok száma $A_{n-1}$, mert ezekre pontosan annak kell teljesülni, hogy $1⩽a_1<a_2<\text{...}<a_k⩽n-1$, és minden tag az indexével azonos paritású.
2. Az a sorozat, amelynek utolsó tagja $n$ és nem tartalmaz $\left(n-1\right)$-nél kisebb elemet. Ilyen pontosan egy van: páratlan $n$ esetén az egy darab $n$-esből álló, páros $n$ esetén pedig az $\left(n-1\right)$, $n$ sorozat.
3. Azok a sorozatok, amelyek utolsó tagja $n$ és tartalmaznak $\left(n-1\right)$-nél kisebb elemet. Ezeket úgy kapjuk, hogy veszünk egy $\left(n-2\right)$-nél nem nagyobb elemekből álló sorozatot (az ilyenek száma $A_{n-2}$); ha ennek legnagyobb eleme $n$-nel azonos paritású, akkor a sorozathoz hozzátesszük az $\left(n-1\right)$ és $n$ számokat, ha pedig az utolsó elem $n$-nel ellentétes paritású, akkor az $n$ számot (minden esetben csak egyféleképpen lehet a sorozatot folytatni).
A háromféle sorozatból összesen $A_{n-1}+A_{n-2}+1$ darab van, a rekurziót igazoltuk. Legyen $f_n$ az $n$-edik Fibonacci-szám $\left(f_0=\mathrm{0,}{f}_1=\mathrm{1,}{f}_{n+1}=f_n+f_{n-1}\right)$. Teljes indukcióval igazoljuk, hogy $A_n=f_{n+2}-1$.
Ha $n=1$, akkor $1$ sorozat van: az egyetlen $1$-esből álló, tehát $A_1=1=f_3-1$.
Ha $n=2$, akkor az $\left(1\right)$ és az $\left(\mathrm{1,2}\right)$ sorozatokra teljesül a feltétel, tehát $A_2=2=f_4-1$.
Az állítás tehát teljesül $n=1$-re és $n=2$-re. Legyen $k⩾3$ és tegyük fel, hogy teljesül $n=k-1$-re és $n=k-2$-re. Ekkor a bizonyított rekurzió és a Fibonacci-sorozat definíciója alapján