help pawel: Niech t_n (dla n>=0) oznacza liczbe slow dlugosci n nad alfabetem {a,b}, ktore nie maja ciagu kolejnych liter ab (tzn litera a stoi kolo litery b w kolejnosci ab). Jaka jest postac jawna ciagu t_n?

Basia: mnie to nie daje spokoju za diabła nie umiem tego zapisać pewnie coś knocę, może trzeba przespać

Basia: wydaje mi się, że t_n = n+1, ale nie potrafię tego porządnie udowodnić

Basia: t₁ = 2 (oczywiste "a" i "b") t₂ = 3 ("aa" "bb" "ba") t₃ = 4 z każdego z poprzednich mogę zrobić dwa z "aa" mam "aaa" i "baa" z "bb" mam "bba" i "bbb" z "ba" mam "baa" i "bba" ale "baa" i "bba" mam dwa razy czyli t₃ = 2*t₂−2 = 2*3−2 = 6−2 = 4 = 3+1 t_n−1 = n−1+1 = n liczę t_n z każdego zrobię 2 czyli 2*t_n−1 ale n−1 mi się powtórzy t_n = 2t_n − (n−1) = 2n−n+1 = n+1 tylko, ze to nie jest taki naprawdę porządny dowód

Basia: Dobrze myślałam, że trzeba to przespać. Proste to jak..... buduję ciąg n−elementowy jeżeli na miejscu k wystąpi "a", to już na żadnym następnym nie mogę wstawić "b" ⇒ możliwości jest tyle na ile sposobów mogę w tym ciągu wstawić pierwszy raz "a" pierwsze "a" może znaleźć się na miejscu 0 (same "b"), 1,2,3,...,n ⇒ mamy n+1 możliwości ⇒ t_n = n+1 c.b.d.o.