Dimostrazione su stringhe e Fibonacci - induzione o combinatoria?

[Ulyx3s]

Ciao!
Avrei il seguente esercizio:

Dato $ n $ naturale non nullo, sia $ S_n $ il numero di tutte le possibili stringhe di cifre binarie (solo usando 0 e 1) tali che:

- hanno lunghezza $n$
- se $n=1$ la stringa è $0$, se $n>1$ la lista comincia per $01$
- non ci sono mai tre cifre uguali consecutive

Esempio: $S_5 =5$ (1001, 01010, 01011, 01100, 01101)
Dimostrare che $S_n = F_n$, dove Fn sono i numeri di Fibonacci.

Ora, io ho provato sia con il calcolo combinatorio (casi totali di stringhe di lunghezza n meno i casi "proibiti"), ma sono uscito pazzo. E poi per unduzione, ma comunque quella regola dei tre numeri non riesco a utilizzarla.

Da voi vorrei almeno sapere, secondo voi quale delle due strade è meglio percorrere? poi ci riprovo, ma almeno un suggerimento di percorso se potete, grazie.

[gugo82]

"Ad occhio", si tratta di mostrare che $(S_n)$ soddisfa la stessa ricorrenza di $(F_n)$, i.e.:
$\{ (x_(n+2) = x_n + x_(n+1)), (x(0)=1), (x(1)=1):}\ .$

Quindi ti conviene ragionare su come $S_(n+2)$ si ottiene partendo da $S_n$ ed $S_(n+1)$.
Comincia a ragionare per $n=1,2,3$ e poi generalizza.
Mi pare che, in fin dei conti, sia una faccenda combinatoria.