Equazione di ricorrenza

[Tommytop]

Ciao, non riesco a capire come impostare il seguente problema:

Determinare un’equazione di ricorrenza per il numero delle stringhe decimali di lunghezza n che contengono un numero dispari di zeri.

So che devo arrivare a un'equazione di ricorrenza del tipo
$\{(a_n=...),(a_o=...):}$
ma non ho proprio idee...

Grazie

[Tommytop]

Up

[Tommytop]

Niente?

[stedrum1]

esame di "matematica del continuo" anche tu eh!?

Allora: dividi il problema in due casi:
1) stringhe di lunghezza n che finiscono con numero diverso da zero
2) stringhe di lunghezza n che finiscono con zero

1) Prendi questa stringa e vedi che può finire con 9 diversi numeri(da 1 a 9); togli l'ultimo, quindi consideri le sotto-stringhe di lunghezza n-1.
Hai 9 stringhe e ognuna puoi abbinarla a una stringa di lunghezza n-1; quindi il contributo di questo caso è = $9*d_(n-1)$

2) Hai sempre una stringa di lunghezza n, ma stavolta finisce con zero.
Se le stringhe di lunghezza n-1 hanno un numero dispari di zeri, aggiungendo lo zero finale diventa pari; viceversa diventa dispari.
Quindi il contributo di questo caso si calcola trovando tutte le combinazioni di sotto-stringhe possibili($10^(n-1)$) e sottraendo le stringhe dispari (n-1).
In definitiva il contributo sarà = $10^(n-1) - d_(n-1)$

Ora sommi i contributi:
$9*d_(n-1) + 10^(n-1) - d_(n-1) = 8*d_(n-1) + 10^(n-1)$
Adesso devi specificare i dati iniziali: in questo caso basta $d_1 = 1$ che indica il numero di stringhe decimali di lunghezza 1 che contengono un numero dispari di zeri; ovvero:
1
2
3
4
5
6
7
8
9
0
come vedì c'è solo lo zero(stringa di lunghezza 1 con numero dispari di zeri)

Per finire metti a sistema:
$\{(d_n=8*d_(n-1) + 10^(n-1)),(d_1=1):} n>=2$

[Tommytop]

Sì avevo anch'io l'esame ahaha

Grazie mille, spiegazione perfetta!

Tutto chiaro!