Úloha o pokrývání
Pro každé nezáporné celé číslo n uvažujme částečně uspořádanou množinu An s diagramem
takže Aq je #.
Naším úkolem je zjistit, kolik existuje podmnožin množiny An neobsahujících žádné dva prvky, z nichž jeden pokrývá druhý v An-
K tomu účelu uvažme pro každé nezáporné celé číslo a? ještě částečně uspořádanou množinu Bn s diagramem
Pro každé nezáporné celé číslo n označme symbolem a(n) počet všech podmnožin v An neobsahujících žádné dva vzájemně se pokrývající prvky. Podobně označme symbolem b(n) počet všech podmnožin v Bn neobsahujících žádné dva vzájemně se pokrývající prvky.
Uvažme nyní libovolnou podmnožinu K v An+i splňující stanovenou podmínku. Obsahuje-li K největší prvek v An+i, pak ostatní prvky v K tvoří podmnožinu v An splňující danou podmínku. Neobsahuje-li však K tento největší prvek, je K podmnožinou v Bn splňující tuto podmínku. Podobně uvažme libovolnou podmnožinu l v Bn+i splňující stanovenou podmínku. Obsahuje-li l některý ze dvou maximálních prvků v Bn+i, případně obsahuje-li l oba tyto maximální prvky, pak zbývající prvky v l tvoří podmnožinu v Bn splňující danou podmínku. Neobsahuje-li však l žádný z obou maximálních prvků v Bn+i, je l podmnožinou v An+i splňující požadovanou podmínku. Z těchto úvah pak plynou rekurentní vztahy
a(a7 + l) = a(a7) + 6(a7),
b(a7 + l) = 3b(a7) + a(a7 + l),
které platí pro všechna nezáporná celá čísla n. Úpravou těchto vztahů dostáváme
b(n) = a(n + 1) — a(n),
a(a7+l) = 6(a7 + l)-36(a7),
opět pro všechna nezáporná celá čísla n. Odtud dosazením do druhého vztahu za b(n + 1) a za b(n) z prvního vztahu vychází
a(n + 1) = a(n + 2) - a(n + 1) - 3(a(a7 + 1) - a(n))
= a(n + 2) - Aa(n + 1) + 3a(a7),
takže zjišťujeme, že
a(n + 2) - 5a(n + 1) + 3a(n) = O
pro všechna nezáporná celá čísla n. To je ale homogenní lineární rekurentní formule s konstantními koeficienty pro posloupnost dosud neznámých hodnot {a(n)}^=o- Počáteční hodnoty přitom jsou
a(0) = 2,  a(l) = 7.
Řešíme tedy dále standardním způsobem tuto lineární rekurentní formuli. Charakteristický polynom této formule je
x2 - 5x + 3,
tento polynom má dva různé jednoduché reálné kořeny
5 + a/13 5-a/Í3
2 3        2 '
takže funkce
5 + v/Í3\" /5 - V^LŠ" "
—j  a (—
nezáporné celočíselné proměnné n tvoří bázi vektorového prostoru všech řešení této rekurentní formule. Posloupnost hodnot {3(n)}^L0, neboli hledaná funkce a(n) proměnné a? je lineární kombinací posledních dvou funkcí.
Jde o lineární kombinaci s jistými koeficienty c,d, pro něž z počátečních podmínek plynou rovnice
5 + VÍ3     , 5-\/Í3 c-----h d----= 7.
Řešením této soustavy lineárních rovnic vychází
c   + d
c-VÍŠ- d-VÍ3 = 4.
takže
a/13+ 2 , VŤ3-2 c =-==—.    d =
Dospíváme tak k výsledku, že
a(n) =
\/Í3
(2 + VÍŠ) • -^—    - (2 - VÍŠ) •
pro všechna nezáporná celá čísla n.