Числа Люка

Не следует путать с последовательностями Люка.

Числа Люка задаются рекуррентной формулой

$L_{n}=L_{n-1}+L_{n-2}$$L_{n}=L_{n-1}+L_{n-2}$

с начальными значениями $L_{0}=2$$L_{0}=2$ и $L_{1}=1$$L_{1}=1$.

Последовательность чисел Люка начинается так:

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, … (последовательность A000032 в OEIS)

Формула общего члена

Последовательность $L_{n}$$L_{n}$ можно выразить как функцию от n:

$L_{n}=\varphi ^{n}+(1-\varphi )^{n}=\varphi ^{n}+(-\varphi )^{-n}=\left({1+{\sqrt {5}} \over 2}\right)^{n}+\left({1-{\sqrt {5}} \over 2}\right)^{n}\,,$$L_{n}=\varphi ^{n}+(1-\varphi )^{n}=\varphi ^{n}+(-\varphi )^{-n}=\left({1+{\sqrt {5}} \over 2}\right)^{n}+\left({1-{\sqrt {5}} \over 2}\right)^{n}\,,$

где $\varphi ={\frac {1+{\sqrt {5}}}{2}}$$\varphi ={\frac {1+{\sqrt {5}}}{2}}$ — золотое сечение.

Проверка простоты числа с помощью чисел Люка

Пусть надо проверить, является ли число $p$$p$ простым. Возьмём p-й член ряда Люка, вычтем из оного единицу, и если полученное число 'не' делится на $p$$p$ нацело, то $p$$p$ - гарантированно 'не' простое. Числа, которые делятся нацело, называются кандидатами в простые числа и требуют более тщательной проверки.

Например, проверим, является ли число 14 простым. 14-й член ряда - это число 843.

${\cfrac {843-1}{14}}=60.142857\ldots$${\cfrac {843-1}{14}}=60.142857\ldots$

Значит, 14 - гарантированно не простое.

Связь с числами Фибоначчи

Числа Люка связаны с числами Фибоначчи следующим формулами

• $L_{n}=F_{n-1}+F_{n+1}=F_{n}+2F_{n-1}$$L_{n}=F_{n-1}+F_{n+1}=F_{n}+2F_{n-1}$
• $L_{m+n}=L_{m+1}F_{n}+L_{m}F_{n-1}$$L_{m+n}=L_{m+1}F_{n}+L_{m}F_{n-1}$
• $L_{n}^{2}=5F_{n}^{2}+4(-1)^{n}$$L_{n}^{2}=5F_{n}^{2}+4(-1)^{n}$, и при стремлении $n$$n$ к +∞ отношение ${\frac {L_{n}}{F_{n}}}$${\frac {L_{n}}{F_{n}}}$ стремится ${\sqrt {5}}.$${\sqrt {5}}.$
• $F_{2n}=L_{n}F_{n}$$F_{2n}=L_{n}F_{n}$
• $F_{n+k}+(-1)^{k}F_{n-k}=L_{k}F_{n}$$F_{n+k}+(-1)^{k}F_{n-k}=L_{k}F_{n}$
• $F_{n}={L_{n-1}+L_{n+1} \over 5}$$F_{n}={L_{n-1}+L_{n+1} \over 5}$

Другие свойства

Для $n>1$$n>1$ величина $(-\varphi )^{-n}$$(-\varphi )^{-n}$ меньше 1/2, $L_{n}$$L_{n}$ - ближайшее целое к $\varphi ^{n}$$\varphi ^{n}$ или, что эквивалентно, $L_{n}$$L_{n}$ - это целая часть $\varphi ^{n}+1/2$$\varphi ^{n}+1/2$, что можно записать как $\lfloor \varphi ^{n}+1/2\rfloor$$\lfloor \varphi ^{n}+1/2\rfloor$.

Обобщения

Числа Люка можно также определить для отрицательных индексов по формуле:

$L_{-n}=(-1)^{n}L_{n}$$L_{-n}=(-1)^{n}L_{n}$

Эдуард Люка ввел понятие «обобщённых последовательностей Фибоначчи», частным случаем которых являются числа Фибоначчи и числа Люка

${\begin{matrix}F_{n}=U_{n}(1,-1)\\L_{n}=V_{n}(1,-1)\end{matrix}}$${\begin{matrix}F_{n}=U_{n}(1,-1)\\L_{n}=V_{n}(1,-1)\end{matrix}}$