rekurencja
JSNZ: Niech sn oznacza liczbę ciągów ternarnych (składających się z cyfr 0, 1 i 2) o
długości n, w których nie występują podciągi 00 oraz 01. Wyznacz rekurencyjną
zależność dla sn , n ≥ 1.
19 sty 14:59
kerajs: Sn=2Sn−1+Sn−2 ∧ S1=3 ∧ S2=7
19 sty 16:04
JSNZ: Mógłbyś uzasadnić?
19 sty 16:33
kerajs: Niech an, bn i cn będą liczbą ciągów ternarnych zakończonych cyfrą 0, 1 i 2
ponadto:
an=bn−1 +cn−1
bn=bn−1 +cn−1
cn=an−1+bn−1 +cn−1
Sn=an+bn +cn=(bn−1 +cn−1)+(bn−1 +cn−1 )+(an−1+bn−1 +cn−1 )=
=2Sn−1−an−1+bn−1 +cn−1 = 2Sn−1−(bn−2 +cn−2 )+(bn−2 +cn−2 )+cn−1=
=2Sn−1+cn−1= 2Sn−1+(an−1+bn−2 +cn−2 )=2Sn−1+Sn−2
19 sty 19:57