Aiuto per eq. di ricorrenza

[gugione]

ciao,

sto risolvendo un esercizio che mi sta dando "rogne": "ricavare un eq. di ricorrenza per il numero S(n) delle stringhe lunghezza $n >= 1$ ottenute usando i caratteri ${a,b}$ e contenenti almeno una $a$.
Io ho ragionato così: le stringhe che contengono almeno una $a$ possono essere di due tipi:
1) iniziano con $a$
2) iniziano con $b$ e hanno dopo una lettera $a$.
E fin qui penso sia corretto alla luce di questo, mi sembrava meglio calcolare le stringhe che non contengono almeno una $a$. quindi ho calcolato $T(n) = T(n-1) + T(n-2)$ dove T(n-1) é il caso in cui la stringa inizii con una $B$, mentre l'altro il caso in cui sia $bb$.
Da qui ho ricavato $S(n) = -T(n)$. Cosa ne pensate?
Grazie a tutta la community per un eventuale spiegazione

[apatriarca]

Le stringhe che non contengono alcuna "a", sono le stringhe che contengono solo "b". E ovviamente di queste ce n'è solo una. Per cui il numero di stringhe che cerchi è \( 2^n - 1 \)..

Volendo scrivere una equazione di ricorrenza possiamo ragionare come segue. Le stringhe con almeno una "a" sono di due tipi:
1. quelle che iniziano con una "a" seguite da qualsiasi stringa
2. quelle che iniziano con "b" e che sono seguite da una stringa che contiene almeno una "a".
Per cui \( S(n) = S(n-1) + 2^{n-1} \) è una possibile equazione. In effetti vediamo che \( 2^n - 1 = (2^{n-1} - 1) + 2^{n-1}. \)

[gugione]

grazie mille Apatriarca veramente gentile ed esauriente!! Come vedi mi sto cimentando spesso in questa tipologia di esercizi, ma non sempre guardare o prendere spunti da esercizi fatti precedente aiuta infatti qui il ragionamento da fare cambia spesso e va beh, pian piano imparerò
grazie ancora