Последовательность Лукаса - Lucas sequence

В математике , то Лукас последовательности и определенные постоянная рекурсии целые последовательности , удовлетворяющие рекуррентное соотношение${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$

${\ displaystyle x_ {n} = P \ cdot x_ {n-1} -Q \ cdot x_ {n-2}}$

где и - фиксированные целые числа. Любая последовательность, удовлетворяющая этому рекуррентному соотношению, может быть представлена ​​как линейная комбинация последовательностей Люка и . ${\ displaystyle P}$${\ displaystyle Q}$${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$

В более общем смысле , Лукас последовательность и представляет собой последовательность полиномов в и с целыми коэффициентами. ${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$${\ displaystyle P}$${\ displaystyle Q}$

Известные примеры Лукас последовательностей включают числа Фибоначчей , число Мерсено , номер Пеллы , номер Лукаса , номер Якобсталь и супернабор чисел Ферма . Последовательности Лукаса названы в честь французского математика Эдуара Лукаса .

Повторяющиеся отношения

Для двух целочисленных параметров P и Q последовательности Люка первого типа U _n ( P , Q ) и второго типа V _n ( P , Q ) определяются рекуррентными соотношениями :

${\ displaystyle {\ begin {align} U_ {0} (P, Q) & = 0, \\ U_ {1} (P, Q) & = 1, \\ U_ {n} (P, Q) & = P \ cdot U_ {n-1} (P, Q) -Q \ cdot U_ {n-2} (P, Q) {\ mbox {for}} n> 1, \ end {выровнено}}}$

а также

${\ Displaystyle {\ begin {align} V_ {0} (P, Q) & = 2, \\ V_ {1} (P, Q) & = P, \\ V_ {n} (P, Q) & = P \ cdot V_ {n-1} (P, Q) -Q \ cdot V_ {n-2} (P, Q) {\ mbox {for}} n> 1. \ End {align}}}$

Не трудно показать , что для , ${\ displaystyle n> 0}$

${\ Displaystyle {\ begin {align} U_ {n} (P, Q) & = {\ frac {P \ cdot U_ {n-1} (P, Q) + V_ {n-1} (P, Q) } {2}}, \\ V_ {n} (P, Q) & = {\ frac {(P ^ {2} -4Q) \ cdot U_ {n-1} (P, Q) + P \ cdot V_ {n-1} (P, Q)} {2}}. \ end {align}}}$

Приведенные выше отношения можно представить в матричной форме следующим образом:

${\ displaystyle {\ begin {bmatrix} U_ {n} (P, Q) \\ U_ {n + 1} (P, Q) \ end {bmatrix}} = {\ begin {bmatrix} 0 & 1 \\ - Q&P \ конец {bmatrix}} \ cdot {\ begin {bmatrix} U_ {n-1} (P, Q) \\ U_ {n} (P, Q) \ end {bmatrix}},}$

${\ displaystyle {\ begin {bmatrix} V_ {n} (P, Q) \\ V_ {n + 1} (P, Q) \ end {bmatrix}} = {\ begin {bmatrix} 0 & 1 \\ - Q&P \ конец {bmatrix}} \ cdot {\ begin {bmatrix} V_ {n-1} (P, Q) \\ V_ {n} (P, Q) \ end {bmatrix}},}$

${\ displaystyle {\ begin {bmatrix} U_ {n} (P, Q) \\ V_ {n} (P, Q) \ end {bmatrix}} = {\ begin {bmatrix} P / 2 & 1/2 \\ ( P ^ {2} -4Q) / 2 & P / 2 \ end {bmatrix}} \ cdot {\ begin {bmatrix} U_ {n-1} (P, Q) \\ V_ {n-1} (P, Q) \ end {bmatrix}}.}$

Примеры

Начальные члены последовательностей Люка U _n ( P , Q ) и V _n ( P , Q ) приведены в таблице:

${\ displaystyle {\ begin {array} {r | l | l} n & U_ {n} (P, Q) & V_ {n} (P, Q) \\\ hline 0 & 0 & 2 \\ 1 & 1 & P \\ 2 & P & {P} ^ { 2} -2Q \\ 3 & {P} ^ {2} -Q & {P} ^ {3} -3PQ \\ 4 & {P} ^ {3} -2PQ & {P} ^ {4} -4 {P} ^ {2} Q + 2 {Q} ^ {2} \\ 5 & {P} ^ {4} -3 {P} ^ {2} Q + {Q} ^ {2} & {P} ^ {5} -5 {P} ^ {3} Q + 5P {Q} ^ {2} \\ 6 & {P} ^ {5} -4 {P} ^ {3} Q + 3P {Q} ^ {2} & {P} ^ {6} -6 {P} ^ {4} Q + 9 {P} ^ {2} {Q} ^ {2} -2 {Q} ^ {3} \ end {array}}}$

Явные выражения

Характеристическое уравнение рекуррентного соотношения для последовательностей Люка и имеет вид: ${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$

${\ Displaystyle х ^ {2} -Px + Q = 0 \,}$

У него есть дискриминант и корни: ${\ Displaystyle D = P ^ {2} -4Q}$

${\ displaystyle a = {\ frac {P + {\ sqrt {D}}} {2}} \ quad {\ text {and}} \ quad b = {\ frac {P - {\ sqrt {D}}} { 2}}. \,}$

Таким образом:

${\ Displaystyle а + Ь = п \ ,,}$

${\ displaystyle ab = {\ frac {1} {4}} (P ^ {2} -D) = Q \ ,,}$

${\ displaystyle ab = {\ sqrt {D}} \ ,.}$

Обратите внимание, что последовательность и последовательность также удовлетворяют рекуррентному соотношению. Однако это могут быть не целые последовательности. ${\ Displaystyle а ^ {п}}$${\ displaystyle b ^ {n}}$

Отчетливые корни

Когда , a и b различны, и быстро проверяется, что ${\ displaystyle D \ neq 0}$

${\ displaystyle a ^ {n} = {\ frac {V_ {n} + U_ {n} {\ sqrt {D}}} {2}}}$

${\ displaystyle b ^ {n} = {\ frac {V_ {n} -U_ {n} {\ sqrt {D}}} {2}}}$.

Отсюда следует, что члены последовательностей Люка могут быть выражены через a и b следующим образом

${\ displaystyle U_ {n} = {\ frac {a ^ {n} -b ^ {n}} {ab}} = {\ frac {a ^ {n} -b ^ {n}} {\ sqrt {D }}}}$

${\ Displaystyle V_ {п} = а ^ {п} + Ь ^ {п} \,}$

Повторный корень

Случай возникает именно тогда, когда для некоторого целого S так, что . В этом случае легко найти, что ${\ displaystyle D = 0}$${\ Displaystyle P = 2S {\ text {и}} Q = S ^ {2}}$${\ displaystyle a = b = S}$

${\ Displaystyle U_ {n} (P, Q) = U_ {n} (2S, S ^ {2}) = nS ^ {n-1} \,}$

${\ Displaystyle V_ {n} (P, Q) = V_ {n} (2S, S ^ {2}) = 2S ^ {n} \,}$.

Характеристики

Производящие функции

Обычные производящие функции :

${\ displaystyle \ sum _ {n \ geq 0} U_ {n} (P, Q) z ^ {n} = {\ frac {z} {1-Pz + Qz ^ {2}}};}$

${\ displaystyle \ sum _ {n \ geq 0} V_ {n} (P, Q) z ^ {n} = {\ frac {2-Pz} {1-Pz + Qz ^ {2}}}.}$

Уравнения Пелла

Когда , последовательности Лукаса и удовлетворяют определенным уравнениям Пелла : ${\ Displaystyle Q = \ pm 1}$${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$

${\ Displaystyle V_ {n} (P, 1) ^ {2} -D \ cdot U_ {n} (P, 1) ^ {2} = 4,}$

${\ Displaystyle V_ {2n} (P, -1) ^ {2} -D \ cdot U_ {2n} (P, -1) ^ {2} = 4,}$

${\ displaystyle V_ {2n + 1} (P, -1) ^ {2} -D \ cdot U_ {2n + 1} (P, -1) ^ {2} = - 4.}$

Отношения между последовательностями с разными параметрами

• Для любого числа c последовательности и с${\ displaystyle U_ {n} (P ', Q')}$${\ displaystyle V_ {n} (P ', Q')}$

${\ Displaystyle P '= P + 2c}$

${\ displaystyle Q '= cP + Q + c ^ {2}}$

имеют тот же дискриминант, что и и : ${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$

${\ displaystyle P '^ {2} -4Q' = (P + 2c) ^ {2} -4 (cP + Q + c ^ {2}) = P ^ {2} -4Q = D.}$

• Для любого числа c также имеем

${\ Displaystyle U_ {n} (cP, c ^ {2} Q) = c ^ {n-1} \ cdot U_ {n} (P, Q),}$

${\ displaystyle V_ {n} (cP, c ^ {2} Q) = c ^ {n} \ cdot V_ {n} (P, Q).}$

Прочие отношения

Условия Лукаса последовательностей удовлетворяют соотношениям , которые являются обобщением тех , между числами Фибоначчи и Люка . Например: ${\ displaystyle F_ {n} = U_ {n} (1, -1)}$ ${\ Displaystyle L_ {n} = V_ {n} (1, -1)}$

${\ displaystyle {\ begin {array} {r | l} {\ text {Общий случай}} & (P, Q) = (1, -1) \\\ hline (P ^ {2} -4Q) U_ { n} = {V_ {n + 1} -QV_ {n-1}} = 2V_ {n + 1} -PV_ {n} & 5F_ {n} = {L_ {n + 1} + L_ {n-1}} = 2L_ {n + 1} -L_ {n} \\ V_ {n} = U_ {n + 1} -QU_ {n-1} = 2U_ {n + 1} -PU_ {n} & L_ {n} = F_ {n + 1} + F_ {n-1} = 2F_ {n + 1} -F_ {n} \\ U_ {2n} = U_ {n} V_ {n} & F_ {2n} = F_ {n} L_ { n} \\ V_ {2n} = V_ {n} ^ {2} -2Q ^ {n} & L_ {2n} = L_ {n} ^ {2} -2 (-1) ^ {n} \\ U_ { m + n} = U_ {n} U_ {m + 1} -QU_ {m} U_ {n-1} = {\ frac {U_ {m} V_ {n} + U_ {n} V_ {m}} { 2}} & F_ {m + n} = F_ {n} F_ {m + 1} + F_ {m} F_ {n-1} = {\ frac {F_ {m} L_ {n} + F_ {n} L_ {m}} {2}} \\ V_ {m + n} = V_ {m} V_ {n} -Q ^ {n} V_ {mn} = DU_ {m} U_ {n} + Q ^ {n} V_ {mn} & L_ {m + n} = L_ {m} L_ {n} - (- 1) ^ {n} L_ {mn} = 5F_ {m} F_ {n} + (- 1) ^ {n} L_ {mn} \\ V_ {n} ^ {2} -DU_ {n} ^ {2} = 4Q ^ {n} & L_ {n} ^ {2} -5F_ {n} ^ {2} = 4 (- 1) ^ {n} \\ U_ {n} ^ {2} -U_ {n-1} U_ {n + 1} = Q ^ {n-1} & F_ {n} ^ {2} -F_ {n- 1} F_ {n + 1} = (- 1) ^ {n-1} \\ V_ {n} ^ {2} -V_ {n-1} V_ {n + 1} = DQ ^ {n-1} & L_ {n} ^ {2} -L_ {n-1} L_ {n + 1} = 5 (-1) ^ {n-1} \\ DU_ {n} = V_ {n + 1} -QV_ {n -1} & F_ {n} = {\ frac {L_ {n + 1} + L_ {n-1}} {5}} \\ V_ {m + n} = {\ frac {V_ {m} V_ {n } + DU_ {m} U_ {n}} {2}} & L_ {m + n} = {\ frac {L_ {m} L_ {n} + 5F_ {m} F_ {n}} {2}} \\ U_ {m + n} = U_ {m} V_ {n} -Q ^ {n} U_ {mn} & F_ {n + m} = F_ {m} L_ {n} - (- 1) ^ {n } F_ {mn} \\ 2 ^ {n-1} U_ {n} = {n \ choose 1} P ^ {n-1} + {n \ choose 3} P ^ {n-3} D + \ cdots & 2 ^ {n-1} F_ {n} = {n \ choose 1} +5 {n \ choose 3} + \ cdots \\ 2 ^ {n-1} V_ {n} = P ^ {n} + {n \ choose 2} P ^ {n-2} D + {n \ choose 4} P ^ {n-4} D ^ {2} + \ cdots & 2 ^ {n-1} L_ {n} = 1 + 5 {n \ choose 2} + 5 ^ {2} {n \ choose 4} + \ cdots \ end {array}}}$

Свойства делимости

Среди последствий - то, что последовательность является кратной , т. Е. Последовательность является последовательностью делимости . Отсюда, в частности, следует, что он может быть простым только тогда, когда n простое. Другим следствием является аналог возведения в степень возведением в квадрат, который позволяет быстро вычислить для больших значений n . Более того, если , то - последовательность сильной делимости. ${\ displaystyle U_ {км} (P, Q)}$${\ displaystyle U_ {m} (P, Q)}$${\ displaystyle (U_ {m} (P, Q)) _ {m \ geq 1}}$${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle U_ {n} (P, Q)}$${\ Displaystyle \ НОД (P, Q) = 1}$${\ displaystyle (U_ {m} (P, Q)) _ {m \ geq 1}}$

Другие свойства делимости следующие:

• Если n / m нечетное, то делится .${\ displaystyle V_ {m}}$${\ displaystyle V_ {n}}$
• Пусть N целое число , взаимно простое с 2 Q . Если существует наименьшее положительное целое число r, для которого N делится , то набор n, для которого N делится, является в точности множеством, кратным r .${\ displaystyle U_ {r}}$${\ displaystyle U_ {n}}$
• Если P и Q четные, то всегда четные, кроме .${\ displaystyle U_ {n}, V_ {n}}$${\ displaystyle U_ {1}}$
• Если P четно, а Q нечетно, то четность равна n и всегда четна.${\ displaystyle U_ {n}}$${\ displaystyle V_ {n}}$
• Если P нечетно, а Q четно, то всегда нечетные для .${\ displaystyle U_ {n}, V_ {n}}$${\ Displaystyle п = 1,2, \ ldots}$
• Если P и Q нечетные, то четные тогда и только тогда, когда n кратно 3.${\ displaystyle U_ {n}, V_ {n}}$
• Если p - нечетное простое число, то (см. Символ Лежандра ).${\ Displaystyle U_ {p} \ Equiv \ left ({\ tfrac {D} {p}} \ right), V_ {p} \ Equiv P {\ pmod {p}}}$
• Если p нечетное простое число и делит P и Q , то p делится для каждого .${\ displaystyle U_ {n}}$${\ displaystyle n> 1}$
• Если p нечетное простое число и делит P, но не Q , то p делится тогда и только тогда, когда n четно.${\ displaystyle U_ {n}}$
• Если p нечетное простое число и делит не P, а Q , то p никогда не делится на .${\ displaystyle U_ {n}}$${\ Displaystyle п = 1,2, \ ldots}$
• Если p нечетное простое число и делит не PQ, а D , то p делится тогда и только тогда, когда p делит n .${\ displaystyle U_ {n}}$
• Если p нечетное простое число и не делит PQD , то p делит , где .${\ displaystyle U_ {l}}$${\ displaystyle l = p- \ left ({\ tfrac {D} {p}} \ right)}$

Последний факт обобщает малую теорему Ферма . Эти факты используются в тесте простоты Лукаса – Лемера . Обратное к последнему факту неверно, как и обратное к малой теореме Ферма. Существует составное n, взаимно простое с D и делящее , где . Такой состав называется псевдопростом Лукаса . ${\ displaystyle U_ {l}}$${\ Displaystyle л = п- \ влево ({\ tfrac {D} {п}} \ вправо)}$

Главный фактор термина в последовательности Лукаса , который не делится на более ранний члена в последовательности называется примитивным . Теорема Кармайкла утверждает, что все, кроме конечного числа членов в последовательности Лукаса, имеют примитивный простой множитель . Действительно, Кармайкл (1913) показал, что если D положительно, а n не равно 1, 2 или 6, то имеет примитивный простой множитель. В случае отрицательного значения D глубокий результат Билу, Ханро, Вотье и Миньотта показывает, что если n > 30, то имеет примитивный простой множитель и определяет, что все случаи не имеют примитивного простого множителя. ${\ displaystyle U_ {n}}$${\ displaystyle U_ {n}}$${\ displaystyle U_ {n}}$

Конкретные имена

Последовательности Лукаса для некоторых значений P и Q имеют определенные имена:

U _n (1, −1)  : числа Фибоначчи

V _n (1, −1)  : числа Люка

U _n (2, −1)  : числа Пелла

V _n (2, −1)  : числа Пелла – Лукаса (сопутствующие числа Пелла)

U _n (1, −2)  : числа Якобсталя

V _n (1, −2)  : числа Якобсталя – Лукаса

U _n (3, 2)  : числа Мерсенна 2 ⁿ  - 1

V _n (3, 2)  : числа вида 2 ⁿ  + 1, которые включают числа Ферма

U _n (6, 1)  : квадратные корни из квадратных треугольных чисел .

U _n ( x , −1)  : многочлены Фибоначчи

V _n ( x , −1)  : многочлены Люка

U _n (2 x , 1)  : многочлены Чебышева второго рода

V _n (2 x , 1)  : многочлены Чебышева первого рода, умноженные на 2

U _n ( x +1, x )  : объединяет базу x

V _n ( x +1, x )  : x ⁿ + 1

Некоторые последовательности Лукаса имеют записи в Он-лайн энциклопедии целочисленных последовательностей :

${\ Displaystyle P \,}$	${\ Displaystyle Q \,}$	${\ Displaystyle U_ {п} (P, Q) \,}$	${\ Displaystyle V_ {п} (P, Q) \,}$
−1	3	OEIS :  A214733
1	−1	OEIS :  A000045	OEIS :  A000032
1	1	OEIS :  A128834	OEIS :  A087204
1	2	OEIS :  A107920	OEIS :  A002249
2	−1	OEIS :  A000129	OEIS :  A002203
2	1	OEIS :  A001477
2	2	OEIS :  A009545	OEIS :  A007395
2	3	OEIS :  A088137
2	4	OEIS :  A088138
2	5	OEIS :  A045873
3	−5	OEIS :  A015523	OEIS :  A072263
3	−4	OEIS :  A015521	OEIS :  A201455
3	−3	OEIS :  A030195	OEIS :  A172012
3	−2	OEIS :  A007482	OEIS :  A206776
3	−1	OEIS :  A006190	OEIS :  A006497
3	1	OEIS :  A001906	OEIS :  A005248
3	2	OEIS :  A000225	OEIS :  A000051
3	5	OEIS :  A190959
4	−3	OEIS :  A015530	OEIS :  A080042
4	−2	OEIS :  A090017
4	−1	OEIS :  A001076	OEIS :  A014448
4	1	OEIS :  A001353	OEIS :  A003500
4	2	OEIS :  A007070	OEIS :  A056236
4	3	OEIS :  A003462	OEIS :  A034472
4	4	OEIS :  A001787
5	−3	OEIS :  A015536
5	−2	OEIS :  A015535
5	−1	OEIS :  A052918	OEIS :  A087130
5	1	OEIS :  A004254	OEIS :  A003501
5	4	OEIS :  A002450	OEIS :  A052539
6	1	OEIS :  A001109	OEIS :  A003499

Приложения

• Последовательности Лукаса используются в вероятностных тестах псевдоперминала Лукаса , которые являются частью широко используемого критерия простоты Бейли – PSW .
• Последовательности Лукаса используются в некоторых методах доказательства простоты, включая тест Лукаса-Лемера-Ризеля , а также N + 1 и гибридный N-1 / N + 1 методы, такие как методы Брилхарта-Лемера-Селфриджа 1975 г.
• LUC является открытым ключом криптосистемы на основе последовательностей Lucas , который реализует аналоги ElGamal (LUCELG), Диффи-Хеллмана (LUCDIF), и RSA (LUCRSA). Шифрование сообщения в LUC вычисляется как член определенной последовательности Лукаса, вместо использования модульного возведения в степень, как в RSA или Диффи – Хеллмана. Однако в статье Bleichenbacher et al. показывает, что многие из предполагаемых преимуществ безопасности LUC над криптосистемами, основанными на модульном возведении в степень, либо отсутствуют, либо не столь существенны, как заявлено.

Смотрите также

• Лукас псевдопрайм
• Псевдопросто Фробениуса
• Псевдопреступление Сомера – Лукаса

Примечания

использованная литература

• Кармайкл, РД (1913), "О численных факторов арифметических форм & alpha ; ^п ± & beta ; ^п ", Анналы математики , 15 (1/4): 30-70, DOI : 10,2307 / 1967797 , JSTOR  1967797
• Лемер, Д.Х. (1930). «Расширенная теория функций Лукаса». Анналы математики . 31 (3): 419–448. Bibcode : 1930AnMat..31..419L . DOI : 10.2307 / 1968235 . JSTOR  1968235 .
• Уорд, Морган (1954). «Простые делители повторяющихся последовательностей второго порядка». Duke Math. Дж . 21 (4): 607–614. DOI : 10.1215 / S0012-7094-54-02163-8 . hdl : 10338.dmlcz / 137477 . Руководство по ремонту  0064073 .
• Сомер, Лоуренс (1980). «Свойства делимости первичных повторений Лукаса относительно простых чисел» (PDF) . Ежеквартальный отчет Фибоначчи . 18 : 316.
• Лагариас, JC (1985). «Множество простых чисел, делящих числа Лукаса, имеет плотность 2/3». Pac. J. Math . 118 (2): 449–461. DOI : 10,2140 / pjm.1985.118.449 . Руководство по ремонту  0789184 .
• Ханс Ризель (1994). Простые числа и компьютерные методы факторизации . Успехи в математике. 126 (2-е изд.). Birkhäuser. С. 107–121. ISBN 0-8176-3743-5.
• Рибенбойм, Пауло; МакДэниел, Уэйн Л. (1996). «Квадратные члены в последовательностях Лукаса» . J. Теория чисел . 58 (1): 104–123. DOI : 10,1006 / jnth.1996.0068 .
• Joye, M .; Quisquater, J.-J. (1996). «Эффективное вычисление полных последовательностей Лукаса» (PDF) . Письма об электронике . 32 (6): 537–538. DOI : 10.1049 / эл: 19960359 . Архивировано из оригинального (PDF) 02 февраля 2015 года.
• Рибенбойм, Пауло (1996). Новая книга рекордов простых чисел (электронная книга). Спрингер-Верлаг , Нью-Йорк. DOI : 10.1007 / 978-1-4612-0759-7 . ISBN 978-1-4612-0759-7.
• Рибенбойм, Пауло (2000). Мои числа, мои друзья: Популярные лекции по теории чисел . Нью-Йорк: Springer-Verlag . С. 1–50. ISBN 0-387-98911-0.
• Лука, Флориан (2000). «Совершенные числа Фибоначчи и Лукаса». Ренд. Circ Matem. Палермо . 49 (2): 313–318. DOI : 10.1007 / BF02904236 . S2CID  121789033 .
• Ябута, М. (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF) . Ежеквартальный отчет Фибоначчи . 39 : 439–443.
• Бенджамин, Артур Т .; Куинн, Дженнифер Дж. (2003). Доказательства, которые действительно важны: искусство комбинаторного доказательства . Математические экспозиции Дольчиани. 27 . Математическая ассоциация Америки . п. 35 . ISBN 978-0-88385-333-7.
• Последовательность Лукаса в энциклопедии математики .
• Вайсштейн, Эрик В. «Последовательность Лукаса» . MathWorld .
• Вэй Дай . «Последовательности Лукаса в криптографии» .