rekurencja kamil: niech u_n oznacza ilosc ciagow dlugosci n zlozonych z liczb ze zbioru {1,2,3} takich ze 1 i 2 nie moga stac obok siebie ( czyli nie moze byc sytuacji 12, 21 np. 312, 1121) uloz odpowiednia zaleznosc rekurencyjna. Bardzo prosze o rozwiazanie ...

Adamm: a_n − długości n z ostatnią trójką b_n − długości n z ostatnią dwójką c_n − długości n z ostatnią jedynką b_n=c_n co jest oczywiste a₁=1, b₁=1, c₁=1, u₁=3 u_n+1=3a_n+2b_n+2c_n=3a_n+4b_n a_n+1=u_n b_n+1=a_n+b_n stąd udało mi się wyznaczyć niestety jedynie zależność rekurencyjną na b_n

Adamm: ale w sumie to można też na u_n

Mariusz: Adam mamy układ równań rekurencyjnych więc wartości i wektory własne oraz postać rozwiązania a_n+1=Aⁿa₀

kamil: totalnie nie rozumiem nic z tego.. moze po mojemu: PIERWSZY PRZYPADEK:zaczynamy od 1. Wtedy mozemy dolozyc 1 lub 3 DRUGI PRZYPADEK:zaczynamy 2. Wtedy mozemy dolozyc 2 lub 3 TRZECI PRZYPADEK:zaczynamy od 3. Wtedy mozemy dolozyc 1 lub 2 lub 3 a wiec gdy zaczniemy od tej 3 to zostanie nam n−1 miejsc do wypelnienia. Sprawa bylaby okej gdyby nie to , iż gdy zaczynamy na przyklad od tej 1 tak jak w pierwszym przypadku co pisalem to potem mozemy nadal dolozyc 1 i potem znowu i znowu i znowu i mozemy miec ciag postaci 111111111..... 1. I chodzi o to ze nie bardzo wiem jak za ta czesc zadania sie zabrac . To samo tyczy sie gdy zaczynamy od 2

Adamm: może nie po twojemu po prostu się zastanów czemu tak, rozwiązanie masz na wyciągnięcie ręki u_n można jednak łatwo wyznaczyć z tego układu

Mariusz: 0 3 4 1 0 0 0 1 1 Za pomocą wartości i wektorów własnych znaleźć n. potęgę tej macierzy i pomnożyć przez wektor początkowy 3 1 1

kamil: zauwaz ze w zadaniu takim samym z tym ze ciagi sa binarne (skladaja sie z 0 i 1 ) , dlugosci n , oraz warunku ze dwa zera nie moga stac obok siebie mamy: zaczynamy od 1 i zostalo nam n−1 miejsc (mozemy dolozyc dowolnie 0 lub 1 na druga pozycje) zaczynamy od 0. Potem mozemy dolozyc tylko 1. Czyli zostaje nam n−2 miejsc do wypelnienia. A wiec mamy : zaleznosc u_n= u₍n−1) + u₍n−2) , gdzie u_n − to dlugosc naszego ciagu binarnego.

kamil: i tutaj mamy doczynienia z ciagiem fibonacciego. Ta sama metoda chce zrobic tamto zadanie....

Adamm: ok, to zrób tą metodą i powiedz nam kiedy się uda powodzenia

kamil: kwestionujesz ta metode akurat w tym przypadku czy ogolnie ?

Adamm: w tym przypadku i ogólnie

Adamm: ja nie mówię że się tak nie da, ale skoro mam sprawdzony sposób to nie widzę sensu by próbować inaczej

kamil: to zadanie jest z matematyki stosowanej na AGH i wcale nie wydaje sie na takie proste na jakie wyglada. Rozwiazuje sie pozniej metoda funkcji tworzacej lub rownaniami charakterystycznymi. To co ty napisales to jest czysto kombitoryczne i nie wyznacza wzoru rekurencyjnego , mysle ze najpierw musisz doczytac troszke jesli chcesz pomoc , bo Twoja metoda zupelnie nie jest nalezna w tym problemie

Adamm: to powiedz jak to zrobić twoim sposobem masz jakiś? z mojego można wyznaczyć wzór rekurencyjny na u_n

Adamm: przedstaw mi jakiś lepszy sposób i się dogadamy

Mariusz: wartości własne dla układu Adama nie przypominają tych dla ciągu Fibonacciego

kamil: dokladnie takim samym jak przy zadaniu gdzie: mamy ciagi binarne dlugosci n takie ze dwa zera nie stoja obok siebie. i gdzie u_n oznacza liczbe takich ciagow dlugosci n. Zadanie analogiczne z tym ze warunek latwiejszy. Sposob jego jest wlasnie taki jak napisalem juz wczesniej. Tak samo probuje zrobic z tym zadaniem ale metoda nie dziala wtedy gdy na przyklad jest opcja gdzie mamy ciag 1111111.... ( awiec nie wystepuje taki moment w ktorym mozemy dodac "cokolwiek do niego") powiedz mi tylko prosze o co chodzi w Twoim rozwiazaniu w 6 linijce , tam gdize jest u_n+1...

kamil: Metoda Adama jest dla mnie urwana jak " z choinki " ze tak powiem... w kazdym bądz razie nie tak to sie robi... no nic , gdyby ktos byl w stanie mi pomoc to bylbym wdzieczny

Adamm: u_n+1=3a_n+2b_n+2c_n tak jak powiedziałeś jest to kombinatoryka mamy a_n i dołączamy do końca 1, 2 lub 3 mamy b_n i dołączamy do końca 2 lub 3 mamy c_n i dołączamy do końca 1 lub 3

Adamm: nie tak to się robi... ehh ty ograniczony człowieku wyrwany prosto spot systemu edukacji

Adamm: spod, nie wiem czemu napisałem spot

Daniel: Ok mamy Twoj b_n ciag konczacy sie dwojka. Napisales ze potem poprzedza ja 2 lub 3. A jesli poprzedza ja zalozmy ta 2 to co potem Jaka poprzedza nastepna liczba Moze 1 ? I widzisz... o to cjchodzi zeby dojsc do sytuacji gdzie ma poprzedzac cokolwiek.. a Twoj pomysl jest ze tak powiem "beznadziejny".

Adamm: ja też umiem zmieniać nicki

Daniel: Kamil sam nie wiem kurcze , pomysl mialem ten sam co Ty w sumie.. dam.znac jak na cos wpadne

Adamm: ok, koniec tej zabawy

Pytający: Kamilu, ale zadaniem jest ułożenie odpowiedniej zależności rekurencyjnej, a nie podanie wzoru ogólnego dla n−tego wyrazu (więc raczej obędzie bez funkcji tworzących). Zależność rekurencyjna wygląda następująco:

⎧	u1=3
⎨	u2=7
⎩	un=2un−1+un−2 dla n≥3

O dziwo, zależność tę można wyprowadzić sposobem Adamma. Gdybyś jednak chciał, ot tak dla hecy, pobawić się w szukanie wzoru ogólnego funkcjami tworzącymi powinno Ci wyjść:

	x2+3x
− funkcja tworząca ciągu un:
	1−2x−x2

	(1−√2)n+1+(1+√2)n+1
− wzór ogólny: un=		.
	2

Mariusz: Pytający Adam napisał układ równań którego rozwiązanie prowadzi przez równanie trzeciego stopnia aby znaleźć wartości własne

jc: Ja bym napisał taką macierz [1 0 1] [0 1 1] = M [1 1 1] bo mamy zabronione (1,2) i (2,1), a reszta jest dozwolona. a_n = [1,1,1] Mⁿ [1,1,1]^t Wartości własne = 1, 1 + √2, 1 − √2. a_n = A(1+√2)ⁿ + B(1−√2)ⁿ + C = jak u Pytającego

a: Mariusz, nie neguję, że są inne sposoby prowadzące do rozwiązania (każdy poprawny sposób jest dobry), ale sposób Adamma dla mnie wydaje się najbardziej intuicyjny − przypomnę, że zadaniem było wyprowadzenie zależności rekurencyjnej, a nie wzoru ogólnego. a_n − ostatnia 1 b_n − ostatnia 2 c_n − ostatnia 3 a_n=b_n=c_n=1 dla n≥2:

⎧	an=an−1+cn−1
⎨	bn=bn−1+cn−1
⎩	cn=an−1+bn−1+cn−1

jednak a_n=b_n, stąd:

⎧	an=an−1+cn−1
⎨	bn=an
⎩	cn=2an−1+cn−1

a₂=b₂=2 c₂=3 dla n≥3: a_n=a_n−1+c_n−1=a_n−1+(2a_n−2+c_n−2)=a_n−1+a_n−2+(a_n−2+c_n−2)= =2a_n−1+a_n−2 c_n=2a_n−1+c_n−1=2(a_n−2+c_n−2)+c_n−1=c_n−1+c_n−2+(2a_n−2+c_n−2)= =2c_n−1+c_n−2 u_n=a_n+b_n+c_n=2a_n+c_n u₁=3 u₂=7 dla n≥3: u_n=2a_n+c_n=2(2a_n−1+a_n−2)+2c_n−1+c_n−2=2(2a_n−1+c_n−1)+(2a_n−2+c_n−2)= =2u_n−1+u_n−2

Pytający: .

Mariusz: jc czyli Adam źle napisał układ równań ? bo wg niego mamy układ [0 3 4] [1 0 0]=M [0 1 1] M₀=[3 1 1]^T Patrz wpis 3 cze 21:50 Żeby znaleźć wartość własne tej macierzy trzeba rozwiązać równanie trzeciego stopnia do tego jeszcze układ równań liniowych aby znaleźć wektory własne

Pytający: Mariusz, układ równań jest dobry, ale: Mⁿ*M₀=[u_n+1 a_n+1 b_n+1]^T // M, M₀ wg Twoich oznaczeń, ciągi wg oznaczeń Adamma Zatem: u_n+1=[1 0 0]*Mⁿ*M₀