Lukasov niz

Lukasov niz je niz brojeva dobijen na osnovu datog pravila. Engleski matematičar iz 19. veka Edvard Lukas je kumovao Fibonačijevim brojevima (on ih je nazvao po Fibonačiju zbog Problema zečeva). Takođe, po njemu je ime dobio i jedan niz koji je veoma sličan sa Fibonačijevim nizom i po rekurentnoj jednačini, kao i po nekim osobinama.

Definicija

Lukasov niz (Ln) je zadat sledećom rekurentnom jednačinom: L1 = 1, L2 = 3 i Ln+2 = Ln+1 + Ln. Ponekad su početni uslovi zadati i kao L0 = 2, L1 = 1 (nećemo se osvrtati na pomerene Lukasove nizove). Ovo L0 će nam trebati kad budemo odredjivali funkcije generatrise.

Teorema

Funkcija generatrisa L(x) Lukasovog niza iznosi: L(x) =(2−x)/(1 − x − x^2) U Tabeli 1 je dato prvih nekoliko članova Lukasovog niza.
Tabela 1 Lukasov niz:

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Ln	2	1	3	4	7	11	18	29	47	76	123	199	322	521	843

Sledeća teorema nam daje vezu Fibonačijevih i Lukasovih brojeva

Teorema 1

Za svaki n ∈ N vaжi jednakost Ln = Fn+1 + Fn−1.

U sledećoj teoremi je sadržana kombinatorna definicija Lukasovih brojeva.

Teorema 2

Skup Nn = 1, 2, . . . , n sadrži tačno Ln podskupova u kojima se ne nalaze 2 uzastopna prirodna broja, kao ni 1 i n istovremeno.

Dokaz

Označimo sa An broj podskupova skupa Nn koji ne sadrže 2 uzastopna prirodna broja (isto kao u Teoremi 1.6.1), a sa Bn broj podskupova skupa Nn koji ne sadrže 2 uzastopna prirodna broja, kao ni 1 i n istovremeno. Za svaki skup S, koji brojimo u Bn, imamo 2 mogućnosti: 1◦ n ƒ∈ S. Kako broj n nije u S u njemu mogu biti svi brojevi iz Nn−1, ali uz uslov da nema 2 uzastopna. Takvih podskupova ima An−1. 2◦ n ∈ S. Kako je broj n u S u njemu ne moжe biti ni 1 ni n − 1, te je stoga S \ {n} ⊆ Nn−2 \ {1}, opet uz uslov da nema 2 uzastopna. Takvih podskupova ima An−3. Stoga na osnovu Teorema 1.6.1 i 1.6.6 dobijamo da važi Bn = An−1 + An−3 = Fn+1 + Fn−1 = Ln.