Matematyka.pl

Witam, mam za zadanie wyznaczyć ilość możliwych kombinacji zbioru 2=elementowego dla ciągu o długości n, tak by jeden z tych dwóch elementów (obojętnie który) nigdy nie występował jeden obok drugiego.
Przykłady:

Zbiór = 0 i 1
Ciąg o długości = 2
Element, który nie ma występować obok siebie = 1
Możliwe kombinacje = 00 01 10
Wynik: 3

Zbiór = 0 i 1
Ciąg o długości = 3
Element, który nie ma występować obok siebie = 1
Możliwe kombinacje = 000 001 010 100 101
Wynik: 5

Zbiór = 0 i 1
Ciąg o długości = 4
Element, który nie ma występować obok siebie = 1
Możliwe kombinacje = 0000 0001 0010 0100 1000 1010 0101 1001
Wynik: 8

Czy jestem w stanie wyznaczyć to jakimś wzorem albo sposobem?
Przez pewien czas uważałem, iż wzór n+2^(n-2), gdzie n to długość ciągu, jest poprawny, jednak wszystko wskazuje na to, że dla większych długości ciągu jest on błędny.

Chodzi mi o to, aby język giętki / Powiedział wszystko, co pomysli głowa. Juliusz Słowacki (1809 - 1849)

\(\displaystyle{ A_n}\) - ilość kombinacji dla ciągu o długości \(\displaystyle{ n}\)

\(\displaystyle{ A_1 = 2\\
A_2 = 3\\
A_n = A_{n-1} + A_{n-2}}\)

Teraz - dlaczego? Powiedzmy, że sytuacja jest taka sama jak w Twoich przykładach, czyli jest \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\), a \(\displaystyle{ 1}\) nie mogą być obok siebie (symetryczna sytuacja jest z obliczeniowego punktu widzenia identyczna). Wtedy na początku możesz postawić:
\(\displaystyle{ 0...}\)
lub
\(\displaystyle{ 10...}\) (wiadomo, że za jedynką musi stać zero)

Tak więc w pierwszym przypadku pozostaje do wypełnienia \(\displaystyle{ n-1}\) miejsc, w drugim \(\displaystyle{ n-2}\).

Aż sam jestem na siebie teraz zły. Bo taką zależność zauważyłem już wcześniej, jednak testując ją błędnie wyznaczyłem kombinacje dla 6 (wynik wychodził mi 22, przez co, ta zależność się nie sprawdzała) i na siłę szukałem kolejnego rozwiązania.

Dziękuję bardzo za pomoc