... basia: Dla n>=0 niech c_n oznacza liczbę ciągów złożonych z n liczb wybranych ze zbioru {0, 1, 2}, nie zawierających ani dwóch kolejnych jedynek, ani dwóch kolejnych dwójek. (a) Pokazać, że c_n spełnia rekurencję c₀ = 1, c₁ = 3, c_n = 2 c_n−1 + c_n−2. (b) Znaleźć rozwiązanie tego równania rekurencyjnego. Proszę bardzo o pomoc.

Blee: mogę Cię naprowadzić wyjaśniając jak do tego problemu podszedłem ( chodzi o (a) )

Blee: Mamy wszystkie ciągi długości (n−1) które spełniają warunki zadania. Zapiszmy, że: a) 'x' z nich kończy się cyfrą 0 b) 'y' z nich kończy się cyfrą 1 c) 'z' z nich kończy się cyfrą 2 oczywiście to oznacza, że x + y + z = c_n−1 Teraz sprawdzamy jakie cyfry można dopisać na koniec (aby podstał ciąg n cyfrowy), aby spełniał warunki zadania a) można dopisać 0, 1 lub 2 (3 możliwości) b) można dopisać 0 lub 2 (2 możliwości) c) można dopisać 0 lub 1 (2 możliwości) czyli c_n = 3x + 2y + 2z = x + 2(x+y+z) = x + 2c_n−1 no to jesteśmy 'prawie w domu', wróćmy do tego co oznaczyliśmy jako 'x'. 'x' to liczba takich ciągów długości (n−1), które zakończone są cyfrą 0. No dobrze, ale ile to jest. To się cofnijmy o krok wcześniej i spójrzmy na ciągi długości (n−2). Jest ich dokładnie c_n−2 i kończą się cyfrą 0, 1 lub 2. Ile z tych ciągów powstanie takich ciągów długości (n−1) aby kończyły się cyfrą 0? Dokładnie c_n−2 ... no bo w końcu po prostu dopiszemy cyfrę 0 do każdego z tych ciągów. czyli x = c_n−2 Stąd: c_n = 2c_n−1 + c_n−2 Mam nadzieję, że w miarę przystępnie pokazałem swoje rozumowanie.

Blee: (b) można wyliczyć (i zapewne tego chciał autor zadania) przez równanie charakterystyczne i takie tam, ale ... można też inaczej zauważ, że wiemy, że z każdego ciągu długości (n−1) powstają: a) 3 nowe ciągi o ile ciąg długości (n−1) kończył się cyfrą 0 b) 2 nowe ciągi o ile ciąg długości (n−1) kończył się cyfrą 1 c) 2 nowe ciągi o ile ciąg długości (n−1) kończył się cyfrą 2 więc: c₂ = 3*x₁ + 2*y₁ + 2*z₁ ; gdzie x₁,y₁,z₁ to są ilości ciągów długości '1' kończące się (odpowiednio) cyfrą 0,1,2 c₃ = 3*x₂ + 2*y₂ + 2*z₂ itd. początkowa proporcja (c₁) czyli x₁: y₁:z₁ wynosiła 1:1:1 więc proporcja w c₂, czyli: x₂ : y₂ : z₂ będzie wynosić 3:2:2 więc proporcja w c₃, czyli x₃ : y₃ : z₃ będzie wynosić 3² : 2² : 2² więc: c_n = 3ⁿ⁻¹ + 2ⁿ⁻¹ + 2ⁿ⁻¹ = 3ⁿ⁻¹ + 2ⁿ (dla n≥1)

Anon: przy n−1 pozycji ciągi wyglądają tak: (x1,x2..,x(n−1)) i jest ich c(n−1) przy n pozycji: (x1,x2...,x(n−1),a) Liczbę "a" możemy wybrać na 2 sposoby mając pewność,że ciąg spełnia warunki bo musi być po prostu inną liczbą niż x(n−1). takich ciągów jest więc 2*c(n−1). nie policzyliśmy tylko przypadku gdzie na końcu ciągu są dwa zera koło siebie. przy n−2 pozycji: (x1,x2...,x(n−2)) i jest ich c(n−2) po dopisaniu 2 zer na końcu będą miały n pozycji w takiej postaci: (x1,x2...,x(n−2),0,0) takich jest po prostu c(n−2) bo do każdego dopisujemy 2 zera. Więc liczba ciągów c(n)=2*c(n−1)+c(n−2) *Wszystkich znaków w nawiasach używam jako indeksów bo nie wiem jak się je robi