Sequenze di elementi

[Hawk]

Trovare $ f(n) $, cioè il numero di sequenze di $ n $ elementi dall'insieme $ A=\{0,1,2\} $ in modo tale che non vi siano due $ 0 $ vicini.

[spugna]

Sia $S_n$ l'insieme delle sequenze di $n$ elementi che soddisfano l'ipotesi (tanto per intenderci abbiamo $f(n)=|S_n|$) e $g(n)$ il numero di sequenze appartenenti a $S_n$ che non iniziano con uno $0$
Detto questo, una sequenza appartenente a $S_n$ può:
-iniziare con $0$ ed essere seguita da una sequenza di $S_{n-1}$ che non inizia con $0$;
-iniziare con $1$ o $2$ ed essere seguita da una qualunque sequenza di $S_{n-1}$.

Da queste due osservazioni ricaviamo $f(n)=g(n-1)+2f(n-1)$ e dalla seconda $g(n)=2f(n-1)$: per sostituzione segue immediatamente $f(n)=2f(n-1)+2f(n-2)$
Per trovare la formula generale dobbiamo risolvere l'equazione $x^2-2x-2=0$, che ci dà $x=1 \pm \sqrt{3}$, per cui si ha $f(n)=a(1+\sqrt{3})^n+b(1-\sqrt{3})^n$
A questo punto si impone $f(1)=3$ e $f(2)=8$ (valori che si trovano in modo quasi banale): abbiamo così un sistema di equazioni che ha come soluzione $a=\dfrac{3+2 \sqrt{3}}{6}$ e $b=\dfrac{3-2 \sqrt{3}}{6}$

[Hawk]

Ecco, puoi spiegarmi come ricavi l'equazione?

[spugna]

Ecco, puoi spiegarmi come ricavi l'equazione?

Non so quanto sia noto questo fatto: data una successione $a_1,a_2,a_3,...$ tale che $a_{n+1}=ha_n+ka_{n-1}$ dove $h$ e $k$ sono due costanti, esistono $\alpha,\beta,p,q$ tali che

$a_n=\alpha p^n+\beta q^n$ $\forall n \in \mathbb{N}^+$

Infatti sostituendo nella formula ricorsiva si ha

$\alpha p^{n-1} \cdot p^2+\beta q^{n-1} \cdot q^2=h(\alpha p^{n-1} \cdot p+\beta q^{n-1} \cdot q)+k(\alpha p^{n-1}+\beta q^{n-1})$

Ora si porta tutto al primo membro:

$\alpha p^{n-1}(p^2-hp-k)+\beta q^{n-1}(q^2-hq-k)=0$

A questo punto basta imporre che $p$ e $q$ siano le soluzioni dell'equazione $x^2-hx-k=0$ (nel nostro caso $h=k=2$)