Równanie rekurencyjne

[szaduj]

Równanie pojawiło się w zadaniu "na ile sposobów można pokryć prostokąt 2 x N kostkami domina".
Ja w odpowiedzi miałem ze można go pokryć na
\(\displaystyle{ S_{n} = S_{n-1}+ S_{n-2}}\)

gdzie Sn - liczba sposobów,
\(\displaystyle{ S_{n-1}}\)- liczba sposób gdy jedno domino jest pionowo
\(\displaystyle{ S_{n-2}}\)- liczba sposób gdy jedno domina są poziomo
I niby wszystko ładnie i dobrze ale moja pani Dr stwierdziła że to jeszcze nie koniec zadania, bo
trzeba jeszcze rozwiązać równanie rekurencyjne (nigdy tego w szkole/uczelni nie miałem )


\(\displaystyle{ T(n)\begin{cases} \ 1\ \ \ n=1\\ 2 \ \ \ n=2\\ T(n-1)+T(n-2) \ \ \ n\ge 3 \end{cases}}\)

Może mi ktoś z nim pomóc?

[Qń]

Sprawdź co to są liczby Fibonacciego.

Q.

[szaduj]

szczerze mówiąc to mi nie bardzo to pomogło

[Qń]

To jesteś mało spostrzegawczy, skoro nie zauważyłeś, że \(\displaystyle{ S_n=F_{n+1}}\)

Q.

[szaduj]

Jeśli Ci chodziło o to , to zauważyłem że liczby układają sie w ciąg Fibbonaciego, z przesunięciem.
Ale co z tego że to wiem jak nie mam bladego pojęcia jak ruszyć te równanie rekurenycjne.

[Qń]

Ale co jeszcze chcesz ruszać? Przecież masz rozwiązanie: \(\displaystyle{ S_n=F_{n+1}}\). Chyba, że chcesz jeszcze wzoru zwartego, to wystarczy użyć wzoru Bineta.

Q.

[szaduj]

To na prawdę nie jest mój wymysł z tym równaniem, tylko mojej chorej pani DR ,
dzisiaj usłyszałem ze takie oto równanie muszę rozwiązać żeby mieć zaliczone zadanie :/
Domyślam się ze chyba o jakiś wzór zwarty...nie mam już siły do tych zadań...

[Qń]

Powtórzę trzeci, ale już ostatni raz. Rozwiązaniem Twojej rekurencji jest \(\displaystyle{ F_{n+1}}\). Możesz zostawić to rozwiązanie w takiej postaci (co wydaje mi się najsensowniejsze), a możesz też przedstawić je w postaci zwartej (używając wzoru Bineta).

Q.

[szaduj]

Wzór bineta jest już "gotowy " dla przesuniętego ciągu Fibbonaciego czy trzeba go zmodyfikować i do każdego n dodać 1 ?

[Qń]

Jeśli dobrze zrozumiałem: tak, do każdego \(\displaystyle{ n}\) we wzorze Bineta trzeba dodać \(\displaystyle{ 1}\).

Q.