Stringhe terniarie

[Karozzi]

Durante l'esame non sono riuscito neanche ad impostare la risoluzione del seguente problema.

Sia $a_n$ il numero di stringhe ternarie di lunghezza $n$ che non presentano due o piu' zeri consecutivi:
ricavare un’equazione di ricorrenza per an.

Che cosa dovrei fare? Almeno per iniziare? Con stringa ternaria si intende formata da ${0,1,2}$ ?

[gugo82]

Beh, innanzitutto devi determinare un'espressione per il numero \(a_n\), poi cerchi una ricorrenza che leghi i valori di \(a_n\) con \(a_{n+1}\).
Prova...

[Karozzi]

In che modo posso determinare l'espressione?
Cioè ho capito che la stringa ternaria non deve presentare 2 zeri consecutivi, ma non so proprio come renderlo, matematicamente parlando.

[gugo82]

Quante stringhe di lunghezza \(n\) puoi formare con i tre elementi \(\{0,1,2\}\)?
Questo è un problema di conteggio.

E, tra queste stringhe, quante hanno almeno due zeri consecutivi?
Questo pure è un problema di conteggio.

Sottrai il secondo numero dal primo ed ottieni \(a_n\).

Prova con \(n=2,3,4,5\) e poi cerca di generalizzare.