Determinare equazione di ricorrenza

[gugione]

Ciao,

faccio informatica e non riesco a capire come risolvere esercizi di questo tipo:

"Determinare un'equazione di ricorrenza per il numero di stringhe ternarie che non contengano 2 o più zeri consecutivi"

So risolvere le eq. di ricorrenza ma non le so creare (come in questo caso). Chi mi aiuta dandomi gentilmente una spiegazione?
Grazie

[apatriarca]

Devi in generale chiederti come risolveresti il problema di contare il numero di stringhe con quella proprietà. Prova a dimenticarti, almeno all'inizio che devi scrivere una equazione di ricorrenza.

In questo caso ad esempio, potresti pensare di dividere la stringa in tre parti:
1. Una prima stringa che contiene solo valori uguali a 1 e 2.
2. Uno zero
3. Una stringa con la proprietà di non avere due o più zeri consecutivi e che non inizia con uno zero.
Siccome la terza sottostringa non deve partire da zero, conviene definire la tua equazione di ricorrenza partendo da quest'altra. In base alla nostra osservazione, la funzione T(n) che restituisce il numero di stringhe ternarie di lunghezza \(n\) che partono da un 1 o da un 2 e che non contengono 0 consecutivi sono:
\[ T(n) = \sum_{i=1}^n 2^i \, T(n-i-1) \]
A questo punto devi pensare ad un modo per aggiungere il caso in cui ci sia uno zero all'inizio della stringa..

[gugione]

Ciao Apatriarca,

grazie per avermi risposto, sono molto in "crisi" con esercizi di questa tipologia che il mio prof chiede a ogni esame. Allora partiamo:

Considero innanzitutto una stringa $a_0 = [0]$
$a_1 = [1], [2]$
e ora come faccio a trovare Una stringa con la proprietà di non avere due o più zeri consecutivi e che non inizia con uno zero.? Io non ho capito come hai ricavato la formula a partire da questo punto...
Grazie per il tuo aiuto