Nuly a jedničky
Úloha číslo: 3294
Dokažte, že počet posloupností nul a jedniček délky \(n\), které neobsahují dvě nuly těsně vedle sebe, je roven \(F_{n+2}\).
Řešení
Označme \(p_n\) počet posloupností délky \(n\), které neobsahují dvě nuly vedle sebe.
Pro první dvě hodnoty \(n\) platí \(p_1=|\{1{,}0\}|=2=F_3\) a \(p_2=|\{11{,}10,01\}|=3=F_4\).
Pro \(n\ge 3\) postupujeme indukcí.
Uvažované posloupnosti délky \(n\) rozdělíme na dvě skupiny: Ty, které končí jedničkou a ty, které končí nulou.
Velikost první skupiny je \(p_{n-1}\), neboť každá posloupnost délky \(n\) končící jedničkou lze získat z posloupnosti délky \(n-1\) neobsahující dvě nuly vedle sebe připsáním jedničky na konec.
U druhé skupiny si nejprve všimneme, že nutně končí dvojicí 10. Předchozích \(n-2\) symbolů je libovolná posloupnost bez dvou nul vedle sebe. Těchto posloupností, tedy i velikost druhé skupiny, je \(p_{n-2}\).
Dostali jsme rekurentní vztah \(p_n=p_{n-1}+p_{n-2}\). Podle indukčního předpokladu můžeme předpokládat, že dokazovaný vztah platí pro všechna čísla menší než \(n\), mimo jiné i pro \(p_{n-1}=F_{n-3}\) a \(p_{n-2}=F_{n-4}\). Dosadíme-li vpravo odpovídající Fibonacciho čísla, dostaneme \(p_n=p_{n-1}+p_{n-2}=F_{n-3}+F_{n-4}=F_{n-2}\).