Ez a feladat teljesen homály nekem, valaki levezetné kérem?

Ha jól értem, akkor

s1 = 3,

s(n+1) = sn + 7, ahol n>=1 egész

Feltételezem, hogy a papír tetszőlegesen nagy, nem szab határt az utaknak.

Vegyük észre, hogy:

- minden szabályos n hosszú út első n-1 lépése egy szabályos n-1 hosszú út, nevezzük ezt az elődjének.

- minden szabályos n-1 hosszú út után megtett szabályos lépés szabályos n hosszú utat eredményez.

- két út biztosan különböző, ha elődjeik különbözőek.

- ha egy út utolsó lépése vízszintes, akkor 2 szabályos lépés tehető, ha függőleges, akkor 3.

Legyen v(n) az olyan n hosszú utak száma, ahol az utolsó lépés vízszintes, f(n) pedig azok száma, ahol függőleges. Ekkor:

- S(n)=f(n)+v(n)

- f(n)= S(n-1), hiszen bármelyik n-1 hosszú út végére tehetünk egy függőleges lépést, és minden különböző függőlegesen végződő n hosszú séta elődje különböző n-1 hosszú séta.

- v(n)= v(n-1)+2f(n-1), mivel minden vízszintesen végződő n-1 hosszú séta csak 1 módon folytatható, viszont minden függőlegesen végződő n-1 séta 2 különböző n sétát eredményezhet vízszintes lépéssel.

Ekkor S(n)=S(n-1)+v(n-1)+2f(n-1)=2S(n-1)+f(n-1)=2S(n-1)+S(n-2)

Már csak a sorozat első két eleme kell: S(1)=3 és S(2)=7.