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}\).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze