postac zwarta dla T(n)

[buzzek90]

Witam,
Chcialbym prosic o pomoc w pewnym zadaniu, a dokladnie o wyznaczenie postaci zwartej dla T(n).
Szukalem jakis materialow, jednak nic nie znalazlem wartosciowego na ten temat.
Oto tresc zadania:


Dana jest szachownica rozmiaru 1×n (jeden rząd pól). Załóżmy, że pola tej szachownicy kolorujemy
na niebiesko lub czerwono. Niech T(n) będzie liczbę kolorowań, w których żadne dwa przyległe do
siebie pola nie są koloru czerwonego.
(a) Znajdź dla T(n) zależność rekurencyjną.
(b) Wyznacz postać zwartą dla T(n).

Jezeli chodzi o moje "dokanania do tej pory":
T(n)=\(\displaystyle{ \begin{cases} 2 dla n=1\\T(n-1) + n-1 dla n>1\end{cases}}\)
\(\displaystyle{ a_{1}=2}\)
\(\displaystyle{ a_{n}=a_{n}-1+n-1}\)

czyli przykladowo
\(\displaystyle{ a_{3}=3+2=5}\)
\(\displaystyle{ a_{4}=5+3=8}\)

rysunkow kratek nie bede tutaj moze pokazywal:D


W sumie to moglby ktos sie wypowiedziec na temat poprawnosci tego co do tej pory zrobilem rowniez;p
pozdrawiam

[porfirion]

Szachownice imo łatwiej myśli się na ciągach 0/1-kowych.

A więc \(\displaystyle{ T(n)}\) to liczba ciągów o \(\displaystyle{ n}\) wyrazach 0/1-kowych, w których nie ma dwóch jedynek koło siebie. Wprowadźmy dodatkowe oznaczenia:

\(\displaystyle{ 0(n)}\) - liczba ciągów o \(\displaystyle{ n}\) wyrazach 0/1-kowych, w których nie ma dwóch jedynek koło siebie i kończą się zerem.
\(\displaystyle{ 1(n)}\) -... i kończą się jedynką.

Więc oczywiście (1): \(\displaystyle{ T(n)=0(n)+1(n)}\)
Mamy też (2): \(\displaystyle{ 0(n+1)=T(n)}\) - do każdego dobrego ciągu n-elementowego można dopisać \(\displaystyle{ 0}\) i dostać w ten sposób dobry ciąg.
I w końcu (3): \(\displaystyle{ 1(n+1)=0(n)}\) - bo tylko po zerze można dopisać jedynkę.

Z (1)+(2) dostajemy (4): \(\displaystyle{ T(n+1)=T(n)+1(n+1)}\)
Z (4)+(3) dostajemy (5): \(\displaystyle{ T(n+1)=T(n)+0(n)}\)
Z (5)+(2) dostajemy finalnie (6)!: \(\displaystyle{ T(n+1)=T(n)+T(n-1)}\)
Co jest bardzo piękną i znaną rekurencją (ciąg Fibonacciego - jego rozwiązanie jest bardzo znane - wzór Bineta (tylko uwaga!: \(\displaystyle{ T(n)=F(n+1)}\)))

[buzzek90]

Na początku chciałbym podziękować za odpowiedz:).
Załapałem Twój tok rozumowania z ciągami, jednak nie do końca rozumiem :

Więc oczywiście (1): \(\displaystyle{ T(n)=0(n)+1(n)}\)
Mamy też (2): \(\displaystyle{ 0(n+1)=T(n)}\) - do każdego dobrego ciągu n-elementowego można dopisać \(\displaystyle{ 0}\) i dostać w ten sposób dobry ciąg.
I w końcu (3): \(\displaystyle{ 1(n+1)=0(n)}\) - bo tylko po zerze można dopisać jedynkę.

Z (1)+(2) dostajemy (4): \(\displaystyle{ T(n+1)=T(n)+1(n+1)}\)
Z (4)+(3) dostajemy (5): \(\displaystyle{ T(n+1)=T(n)+0(n)}\)
Z (5)+(2) dostajemy finalnie (6)!: \(\displaystyle{ T(n+1)=T(n)+T(n-1)}\)
Co jest bardzo piękną i znaną rekurencją (ciąg Fibonacciego - jego rozwiązanie jest bardzo znane - wzór Bineta (tylko uwaga!: \(\displaystyle{ T(n)=F(n+1)}\)))

Oraz czy zależność rekurencyjna to nie jest to co napisałem ?:D,
jak również dalej nie wiem jak wyznaczyć postać zwarta;(

Niestety jutro mija termin zaliczenia tego zadania, a dalej nie mam rozwiązania, dlatego też dziękuję z góry za pomoc.



PS: wlasnie znalazlem zaleznosc rekurencyjna dzieki Tobie, mianowicie \(\displaystyle{ a_n_+_2=a_n_+_1+a_1}\),
i teraz jak odejme 2 po obu stronach to wyjdzie wzor Bineta ?

[porfirion]

Sprawdź co to jest ciąg fibonacciego. Zobacz jak się ma do \(\displaystyle{ a_{n}}\). Nie musisz wyprowadzać wzoru jawnego na \(\displaystyle{ F_{n}}\) bo jest to bardzo znany wzór.

-- 20 cze 2014, o 18:21 --

PS: wlasnie znalazlem zaleznosc rekurencyjna dzieki Tobie, mianowicie \(\displaystyle{ a_n_+_2=a_n_+_1+a_1}\)

Nie jest on prawidłowy.-- 20 cze 2014, o 18:24 --

dostajemy finalnie (6)!: \(\displaystyle{ T(n+1)=T(n)+T(n-1)}\)
Co jest bardzo piękną i znaną rekurencją (ciąg Fibonacciego - jego rozwiązanie jest bardzo znane - wzór Bineta (tylko uwaga!: \(\displaystyle{ T(n)=F(n+1)}\)))

[buzzek90]

Muszę coś w związku ze wzorem jawnym zrobić, taki prowadzący. Nie mogę powiedzieć, że jest bardzo znany i już.

Formalnie \(\displaystyle{ F_{n}= F_n_-_1+F_n_-_2}\), ale przecież po przestawieniu to wychodzi tak samo z a, czy nie ?

[porfirion]

Tu jest napisane jak rozwiązać to równanie.

Po przestawieniu wychodzi to samo, tak - ale ciąg nie jest zadany wyłącznie przez równanie rekurencyjne, ale też przez startowe wartości. I dlatego musisz przesunąć, żeby wartości się zgadzały.

[buzzek90]

Rozmawialem dzisiaj z pania profesor, okazalo sie ze to zadanie to nie jest ciag fibonacciego, jak rowniez, ze zaleznosc rekurencyjna ktora podalem jest prawidlowa. Teraz musze policzyc reszte

[porfirion]

Nigdy nie napisałem, że rozwiązaniem jest ciąg fibonacciego, tylko przesunięty ciąg fibonacciego.

IMO moja rekurencja jest poprawna, a twoja nie. I dopóki nie pokażesz mi dowodu swojej, bądź ktoś nie wskaże błędu w moim rozumowaniu, to nie zmienię zdania.

Autorytet profesorski to ważna rzecz, ale warto też umieć rozumować samodzielne...

p.s. wskazana przez Ciebie rekurencja nie zgadza się nawet z wypisanymi też przez ciebie pierwszymi wartościami ciągu (bo \(\displaystyle{ a_{4}=a_{3}+a_{2} \neq a_{3}+a_{1}}\))

[buzzek90]

o kurcze, wlasnie zauwazylem dlaczego sie zw mna nie zgadzasz! tam nie powinno byc \(\displaystyle{ a_n_+_2=a_n_+_1+a_1}\)
tylko
\(\displaystyle{ a_n_+_2=a_n_+_1+a_n}\) !! Wkradla mi sie literowka:D Czy teraz dobrze? Pani profesor oczywiscie pokazalem ta wersje bez literowki.

[porfirion]

tak

[buzzek90]

Probowalem obliczyc funkcje tworzaca, czy wynik jest prawidlowy? \(\displaystyle{ F \left( x \right) = \frac{1}{1-2x-x^2}}\)
Jezeli tak to jak teraz powinienem obliczyc reszte?

\(\displaystyle{ x_1=\frac{2-\sqrt{8}}{-2}}\)
\(\displaystyle{ x_2=\frac{2+\sqrt{8}}{-2}}\)

czyli

\(\displaystyle{ F \left( n \right) = \frac{1}{\sqrt{8}} \left( \frac{2+\sqrt{8}}{-2} \right) ^n - \frac{1}{\sqrt{8}} \left( \frac{2-\sqrt{8}}{-2} \right) ^n}\)

czy to jest dobrze?-- 23 cze 2014, o 22:26 --czy moze jednak taka odp ? :

\(\displaystyle{ a_n=\frac{\sqrt{2}-2}{2\sqrt{2}}(2+\sqrt{2})^n+
\frac{2+\sqrt{2}}{2\sqrt{2}}(2-\sqrt{2})^n}\)