Du kannst z.B. eine Rekursion für das Problem finden. Hierfür gebe uns φ(n) die Anzahl solcher Folgen für die Menge {1,2,…,n}. Nun musst du versuchen, eine Relation zwischen φ(n) und φ(k) zu finden, für k∈1,…,n−1. In diesem Fall ergibt sich
φ(n)=φ(n−1)+φ(n−2)
da wir entweder die Zahl n garnich beachten und lediglich die Menge {1,…,n−1} betrachten könnten, oder uns dazu entschliessen, dass die Folge n enthält (und somit nicht n−1 enthalten kann, da diese beiden ja aufeinander folgen). Du erkennst die Rekursion sicherlich direkt als die Fibonacci Folge wieder, deren geschlossene Form sich auf vielerlei Weisen ermitteln lässt.
Hinweis: Wichtig ist in der obigen Betrachtung, dass die beiden Fälle, welche wir unterscheiden, disjunkt sind, also in diesem Fall, dass wir zum einen alle Folgen zählen, welche n nicht enthalten, und jene, welche n enthalten. Somit ist sicher, dass wir keine Folgen mehrfach zählen.