Matematyka.pl

Witam,

mam problem z zadaniem:

Niech \(\displaystyle{ a_n}\) będzie liczbą podzbiorów zbioru \(\displaystyle{ \left[ n\right]}\) bez par typu \(\displaystyle{ k, k+2}\). Znaleźć zależność rekurencyjną na \(\displaystyle{ a_n}\).

Nie za bardzo wiem jak się zabrać i czy dobrze rozumuję, że jeśli np. \(\displaystyle{ n=3}\). To możliwe podzbiory poza pustym to są:
\(\displaystyle{ 1}\)
\(\displaystyle{ 2}\)
\(\displaystyle{ 3}\)
\(\displaystyle{ 12}\)
\(\displaystyle{ 23}\)
\(\displaystyle{ 123}\)
i wtedy \(\displaystyle{ a_3 = 6}\).
Proszę o wskazówki i pomoc przy rozwiązaniu

\(\displaystyle{ n=3}\) jest za małe, bo jest pierwsze, w której występuje para \(\displaystyle{ \{k;k+2\}}\).
Rozpisz wszystkie podzbiory dla \(\displaystyle{ n=4}\), może coś Cię oświeci.

A jaką przyjemną funkcję tworzącą wytropiłam Możesz użyć jej do sprawdzenia, czy dobrze liczysz \(\displaystyle{ a_n}\).

\(\displaystyle{ \frac{1}{(1 + z^2) (1 - z - z^2)}.}\)