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