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.