Ilość sposobów wyboru elementów zbioru

[Azras]

Mam n-elementowy zbiór różnych liczb naturalnych. Na ile sposobów można wybrać niektóre z tych elementów (można wziąć wszystkie, żadnego, lub tylko niektóre), tak aby spośród podanych nie było żadnych dwóch, które stały obok siebie w zbiorze?
Np. dla n=3 mamy 5 możliwych sposobów:

Przykładowy zbiór \(\displaystyle{ \left\{ 1,2,3\right\}}\)

Możliwe wybory:

\(\displaystyle{ \left\{ 1\right\}
\left\{ 2\right\}
\left\{ 3\right\}
\left\{ 1,3\right\}
\left\{ \right\}}\)

[Qń]

Oznaczmy ilość takich wyborów ze zbioru \(\displaystyle{ n}\)-elementowego przez \(\displaystyle{ A_n}\). Wskazówka: spróbuj wykazać zależność rekurencyjną \(\displaystyle{ A_n=A_{n-1}+A_{n-2}}\).

Q.