Olimpiadi della Matematica Torino - OliMaTO - Forum

Considera le parole che terminano per BN, NB, BB, NN

Il numero di parole che terminano con BN è uguale al numero di quelle che terminano con NB per simmetria del problema. Analogamente quelle che terminano per NN e BB

Chiamiamo [tex]a_n = \mbox{numero di parole che terminano con NN} = \mbox{numero di parole che terminano con BB}[/tex]
e [tex]b_n = \mbox{numero di parole che terminano con NB} = \mbox{numero di parole che terminano con BN}[/tex]
\begin{equation} a_n = b_{n-1} \end{equation}
\begin{equation} b_n = a_{n-1} + b_{n-1} \end{equation}
Ora chiamiamo [tex]S_n = 2a_n + 2b_n[/tex]
\begin{equation}S_n=2a_n+2b_n=2b_{n-1}+2(a_{n-1}+b_{n-1})=2a_{n-1}+2b_{n-1}+2(a_{n-2}+b_{n-2})=S_{n-1}+S_{n-2} \end{equation}
Poi ricaviamo [tex]S_1=2[/tex] e [tex]S_2=4[/tex] e abbiamo così ottenuto la successione:
\begin{equation}\begin{cases}
S_1=2 \\
S_2=4 \\
S_n=S_{n-1}+S_{n-2}
\end{cases}\end{equation}

Che è il doppio di Fibonacci...