Esercizi equazioni ricorsive

[~Rose16]

Allora, l'esercizio è questo:

Denotiamo con $S_n$ il numero di stringhe con n bit che non contengono due 0 consecutive. Per n=6 una tale stringa è ad esempio 111010. Si trovino un'equazione ricorsiva e delle condizioni iniziali per la successione {$S_n$}.

Mio tentativo:

Se n=1: (1) o (0) quindi $S_1$=2
Se n=2: (10) o (01) o (11) quindi $S_2$=3
Se n=3: (101) o (111) o (010) o (011) o (110) quindi $S_3$=5

Poi il prof ci ha anticipato che per $S_4$ avremo 8 stringhe... Quindi in teoria, l'equazione ricorsiva dovrebbe essere questa

$F_n$=$F_n_-1$+$F_n_-2$
$F_1$=2
$F_2$=3


E' corretto?


Il secondo è questo:

$a_n$=$3^n$ * $a_n_-1$, n>0
$a_0$=1

Applicando la teoria

$a_n$=b* $a_n_-1$
$a_m$=c

Ho la soluzione $a_n$=c*$b^(n-m)$

e dovrei ottenere $a_n$=1*$3^n$, è possibile? non sono proprio convinta che sia la formula giusta da applicare ma è l'unica che mi sembrava utile...

Ps. Scusate ma non mi accettava il codice per le parentesi graffe da sistema... Dove ho scritto in colonna sono tutti sistemi!

[digitaldestiny]

Salve...

Per il secondo questito ti dico che devi utilizzare la formula risolutiva nel caso il coefficente b sia variabile di n. (Visto che in questo caso è 3 elevato n il coefficente).

nel tuo caso quindi il termine ennesimo è: $ c(prod_(i = 1)^(n) b(i)) $ dove c è il termine iniziale.

Ciao e buona fortuna con la provetta di domani, collega..

[~Rose16]

Grazie mille L'ho scoperto anch'io chiedendolo direttamente per e-mail al prof... Buona fortuna anche a te!