Лукасов низ

Лукасов низ је низ бројева добијен на основу датог правила. Енглески математичар из 19. века Едвард Лукас је кумовао Фибоначијевим бројевима (он их је назвао по Фибоначију због Проблема зечева). Такође, по њему је име добио и један низ који је веома сличан са Фибоначијевим низом и по рекурентној једначини, као и по неким особинама.

Дефиниција

Лукасов низ (Лн) је задат следећом рекурентном једначином: Л1 = 1, Л2 = 3 и Лн+2 = Лн+1 + Лн. Понекад су почетни услови задати и као Л0 = 2, Л1 = 1 (нећемо се освртати на померене Лукасове низове). Ово Л0 ће нам требати кад будемо одредјивали функције генератрисе.

Теорема

Функција генератриса L(x) Лукасовог низа износи: L(x) =(2−x)/(1 − x − x^2) У Табели 1 је дато првих неколико чланова Лукасовог низа.
Табела 1 Лукасов низ:

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

Следећа теорема нам даје везу Фибоначијевих и Лукасових бројева

Теорема 1

За сваки н ∈ Н важи једнакост Лн = Фн+1 + Фн−1.

У следећој теореми је садржана комбинаторна дефиниција Лукасових бројева.

Теорема 2

Скуп Нн = 1, 2, . . . , н садржи тачно Лн подскупова у којима се не налазе 2 узастопна природна броја, као ни 1 и н истовремено.

Доказ

Означимо са Ан број подскупова скупа Нн који не садрже 2 узастопна природна броја (исто као у Теореми 1.6.1), а са Бн број подскупова скупа Нн који не садрже 2 узастопна природна броја, као ни 1 и н истовремено. За сваки скуп С, који бројимо у Бн, имамо 2 могућности: 1◦ н ƒ∈ С. Како број н није у С у њему могу бити сви бројеви из Нн−1, али уз услов да нема 2 узастопна. Таквих подскупова има Ан−1. 2◦ н ∈ С. Како је број н у С у њему не може бити ни 1 ни н − 1, те је стога С \ {н} ⊆ Нн−2 \ {1}, опет уз услов да нема 2 узастопна. Таквих подскупова има Ан−3. Стога на основу Теорема 1.6.1 и 1.6.6 добијамо да важи Бн = Ан−1 + Ан−3 = Фн+1 + Фн−1 = Лн.