Dunque ...
Supponiamo di avere un sentiero lungo $n-2$ metri il quale può essere formato in $a_(n-2)$ modi diversi.
Se alla fine del sentiero posiamo una piastrella $1 xx 2$ otteniamo un sentiero lungo $n$ metri.
Le piastrelle di questo tipo sono di tre colori diversi quindi possiamo "completare" ciascuno degli $a_(n-2)$ diversi sentieri lunghi $n-2$ metri in tre modi, ottenendo perciò $3a_(n-2)$ sentieri diversi lunghi $n$ metri.
Però, invece di una piastrella da due metri, potremmo usarne due $1 xx 1$ per completare il sentiero; in questo caso ci sono $4$ modi per farlo portando quindi il totale a $7a_(n-2)$ modi per ottenere un sentiero lungo $n$ metri.
E questo giustifica il primo addendo della relazione ricorsiva.
Se ponessimo la piastrella lunga (o due corte) all'inizio del sentiero di $n-2$ metri otterremmo ancora uno dei percorsi precedenti, nessuno nuovo; la stessa cosa accadrebbe se la intercalassimo tra una piastrella e l'altra.
Se invece sovrapponessimo una piastrella lunga (o due corte) a quelle esistenti avremmo due possibilità: o la piastrella si sovrappone esattamente a una doppia o a due corte (e ricadremmo ancora nei casi precedenti) oppure ricoprirebbe una corta e mezza lunga.
In tal caso, togliendo quella corta, la lunga si sovrapporrebbe ad una lunga formando un sentiero lungo $n-3$ metri che si può completare aggiungendo una piastrella lunga ed una corta, in sei combinazioni diverse ovvero, in tal caso, otterremmo $6a_(n-3)$ modi diversi per costruire un sentiero lungo $n$ metri.
Altre possibilità non ci sono quindi sommando le due modalità avremo la relazione ricorsiva vista prima.
Lo so, è un po' complicato ma che ci volete fare, questo mi è venuto
C'è una relazione più semplice, oltre a una forma chiusa, che altri (
) hanno trovato, quindi lascio a loro ...
Cordialmente, Alex
