This site is supported by donations to The OEIS Foundation.

Lucas sequences

A Lucas sequence is a particular generalization of sequences like the Fibonacci numbers, Lucas numbers, Pell numbers or Jacobsthal numbers. Lucas sequences have one common characteristic: they can be generated over quadratic equations of the form

${\displaystyle x^{2}-Px+Q=0,\ P^{2}-4Q\neq 0.\,}$

There exist two kinds of Lucas sequences:

• Sequences ${\displaystyle \scriptstyle U(P,Q)\,=\,\{U_{n}(P,Q)\}_{n\geq 0}}$ with
${\displaystyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}}$,
• Sequences ${\displaystyle \scriptstyle V(P,Q)\,=\,\{V_{n}(P,Q)\}_{n\geq 0}}$ with
${\displaystyle V_{n}(P,Q)=a^{n}+b^{n}\ }$,

where

${\displaystyle a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}},\ b={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}}$

are the solutions of the quadratic equation

${\displaystyle x^{2}-Px+Q=0\,}$.

Properties

• The variables ${\displaystyle \scriptstyle a\ }$ and ${\displaystyle \scriptstyle b\ }$, and the parameter ${\displaystyle \scriptstyle P\ }$ and ${\displaystyle \scriptstyle Q\ }$ are interdependent. In particular, ${\displaystyle \scriptstyle P=a+b\ }$ and ${\displaystyle \scriptstyle Q=a\cdot b.}$.
• For every sequence ${\displaystyle \scriptstyle U(P,Q)=(U_{n}(P,Q))_{n\geq 0}}$ it holds that ${\displaystyle \scriptstyle U_{0}=0\ }$ and ${\displaystyle U_{1}=1}$.
• For every sequence ${\displaystyle \scriptstyle V(P,Q)=(V_{n}(P,Q))_{n\geq 0}}$ is holds that ${\displaystyle \scriptstyle V_{0}=2\ }$ and ${\displaystyle V_{1}=P}$.

For every Lucas sequence the following are true:

• ${\displaystyle \scriptstyle U_{2n}=U_{n}\cdot V_{n}\ }$
• ${\displaystyle \scriptstyle V_{n}=U_{n+1}-QU_{n-1}\ }$
• ${\displaystyle \scriptstyle V_{2n}=V_{n}^{2}-2Q^{n}\ }$
• ${\displaystyle \scriptstyle \operatorname {gcd} (U_{m},U_{n})=U_{\operatorname {gcd} (m,n)}}$
• ${\displaystyle \scriptstyle m\mid n\implies U_{m}\mid U_{n}}$ for all ${\displaystyle \scriptstyle U_{m}\neq 1}$

Recurrence relation

The Lucas sequences ${\displaystyle \scriptstyle U(P,Q)\,}$ and ${\displaystyle \scriptstyle V(P,Q)\,}$ are defined by the recurrence relations

${\displaystyle U_{0}(P,Q)=0\,}$
${\displaystyle U_{1}(P,Q)=1\,}$
${\displaystyle U_{n}(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q){\mbox{ for }}n>1\,}$

and

${\displaystyle V_{0}(P,Q)=2\,}$
${\displaystyle V_{1}(P,Q)=P\,}$
${\displaystyle V_{n}(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q){\mbox{ for }}n>1\,}$

Fibonacci numbers and Lucas numbers

The two best known Lucas sequences are the Fibonacci numbers ${\displaystyle \scriptstyle U(1,-1)\ }$ and the Lucas numbers ${\displaystyle \scriptstyle V(1,-1)\ }$ with ${\displaystyle \scriptstyle a={\frac {1+{\sqrt {5}}}{2}}}$ and ${\displaystyle \scriptstyle b={\frac {1-{\sqrt {5}}}{2}}}$.

Lucas sequences and the prime numbers

If the natural number ${\displaystyle \scriptstyle p\ }$ is a prime number then it holds that

• ${\displaystyle \scriptstyle p\ }$ divides ${\displaystyle \scriptstyle U_{p}(P,Q)-\left({\frac {D}{p}}\right)}$
• ${\displaystyle \scriptstyle p\ }$ divides ${\displaystyle \scriptstyle V_{p}(P,Q)-P\ }$

Fermat's little theorem can then be seen as a special case of ${\displaystyle \scriptstyle p\ }$ divides ${\displaystyle \scriptstyle (V_{n}(P,Q)-P)\ }$ because ${\displaystyle \scriptstyle a^{p}\equiv a{\pmod {p}}}$ is equivalent to ${\displaystyle \scriptstyle V_{p}(a+1,a)\equiv V_{1}(a+1,a){\pmod {p}}}$.

The converse pair of statements that if ${\displaystyle \scriptstyle n\ }$ divides ${\displaystyle \scriptstyle U_{n}(P,Q)-\left({\frac {D}{n}}\right)}$ then is ${\displaystyle \scriptstyle n\ }$ a prime number and if ${\displaystyle m\ }$ divides ${\displaystyle \scriptstyle V_{m}(P,Q)-P\ }$ then is ${\displaystyle m\ }$ a prime number) are individually false and lead to Fibonacci pseudoprimes and Lucas pseudoprimes, respectively.

Sequences

Sequences are ordered by increasing ${\displaystyle \scriptstyle P\,}$, then subordered by decreasing ${\displaystyle \scriptstyle Q\,}$, since

${\displaystyle \{U_{n}(P,Q)\}_{n\geq 0}=\{0,1,P,P^{2}-Q,...\}\,}$

and

${\displaystyle \{V_{n}(P,Q)\}_{n\geq 0}=\{2,P,P^{2}-2Q,...\}\,}$.
Lucas sequences
${\displaystyle U(P,Q)\,}$

and

${\displaystyle V(P,Q)\,}$

Description OEIS

number

Sequence

${\displaystyle \{U_{n}(P,Q)\}_{n\geq 0}\,}$ or ${\displaystyle \{V_{n}(P,Q)\}_{n\geq 0}\,}$

${\displaystyle \scriptstyle U(1,-1)\,}$ Fibonacci numbers A000045 {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, ...}
${\displaystyle \scriptstyle V(1,-1)\,}$ Lucas numbers A000032 {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, ...}
${\displaystyle \scriptstyle U(1,-2)\,}$ Jacobthal numbers A001045 {0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, ...}
${\displaystyle \scriptstyle V(1,-2)\,}$ Jacobsthal-Lucas numbers A014551 {2, 1, 5, 7, 17, 31, 65, 127, 257, 511, 1025, 2047, 4097, 8191, 16385, 32767, 65537, 131071, 262145, 524287, 1048577, 2097151, 4194305, ...}
${\displaystyle \scriptstyle U(1,-3)\,}$ A006130(n-1)
n ≥ 1
{0, 1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689, 75316, 173383, 399331, 919480, 2117473, 4875913, 11228332, 25856071, 59541067, ...}
${\displaystyle \scriptstyle V(1,-3)\,}$ A075118 {2, 1, 7, 10, 31, 61, 154, 337, 799, 1810, 4207, 9637, 22258, 51169, 117943, 271450, 625279, 1439629, 3315466, 7634353, 17580751, 40483810, ...}
${\displaystyle \scriptstyle U(2,-1)\,}$ Pell numbers A000129 {0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428, 38613965, 93222358, ...}
${\displaystyle \scriptstyle V(2,-1)\,}$ Pell-Lucas numbers A002203 {2, 2, 6, 14, 34, 82, 198, 478, 1154, 2786, 6726, 16238, 39202, 94642, 228486, 551614, 1331714, 3215042, 7761798, 18738638, 45239074, 109216786, ...}
${\displaystyle \scriptstyle U(3,2)\,}$ Repunits base 2 A000225 {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, ...}
${\displaystyle \scriptstyle V(3,2)\,}$ ${\displaystyle \scriptstyle 2^{n}+1\,}$ A000051 {2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, ...}
${\displaystyle \scriptstyle U(3,-10)\,}$ A015528 {0, 1, 3, 19, 87, 451, 2223, 11179, 55767, 279091, 1394943, 6975739, 34876647, 174387331, 871928463, 4359658699, 21798260727, 108991369171, ...}
${\displaystyle \scriptstyle V(3,-10)\,}$ A?????? {2, 3, 29, ...}
${\displaystyle \scriptstyle U(3,-11)\,}$ A015529 {0, 1, 3, 20, 93, 499, 2520, 13049, 66867, 344140, 1767957, 9089411, 46715760, 240130801, 1234265763, 6344236100, 32609631693, 167615492179, ...}
${\displaystyle \scriptstyle V(3,-11)\,}$ A?????? {2, 3, 31, ...}
${\displaystyle \scriptstyle U(4,3)\,}$ Repunits base 3 A003462 {0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, ...}
${\displaystyle \scriptstyle V(4,3)\,}$ ${\displaystyle \scriptstyle 3^{n}+1\,}$ A034472 {2, 4, 10, 28, 82, 244, 730, 2188, 6562, 19684, 59050, 177148, 531442, 1594324, 4782970, 14348908, 43046722, 129140164, 387420490, 1162261468, ...}
${\displaystyle \scriptstyle U(4,-3)\,}$ A015530 {0, 1, 4, 19, 88, 409, 1900, 8827, 41008, 190513, 885076, 4111843, 19102600, 88745929, 412291516, 1915403851, 8898489952, 41340171361, ...}
${\displaystyle \scriptstyle V(4,-3)\,}$ A?????? {2, 4, 22, ...}
${\displaystyle \scriptstyle U(4,-5)\,}$ A015531 {0, 1, 4, 21, 104, 521, 2604, 13021, 65104, 325521, 1627604, 8138021, 40690104, 203450521, 1017252604, 5086263021, 25431315104, 127156575521, ...}
${\displaystyle \scriptstyle V(4,-5)\,}$ A?????? {2, 4, 26, ...}
${\displaystyle \scriptstyle U(5,4)\,}$ Repunits base 4 A002450 {0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, ...}
${\displaystyle \scriptstyle V(5,4)\,}$ ${\displaystyle \scriptstyle 4^{n}+1\,}$ A052539 {2, 5, 17, 65, 257, 1025, 4097, 16385, 65537, 262145, 1048577, 4194305, 16777217, 67108865, 268435457, 1073741825, 4294967297, 17179869185, ...}
${\displaystyle \scriptstyle U(5,-6)\,}$ A015540 {0, 1, 5, 31, 185, 1111, 6665, 39991, 239945, 1439671, 8638025, 51828151, 310968905, 1865813431, 11194880585, 67169283511, 403015701065, ...}
${\displaystyle \scriptstyle V(5,-6)\,}$ A?????? {2, 5, 37, ...}
${\displaystyle \scriptstyle U(6,5)\,}$ Repunits base 5 A003463 {0, 1, 6, 31, 156, 781, 3906, 19531, 97656, 488281, 2441406, 12207031, 61035156, 305175781, 1525878906, 7629394531, 38146972656, 190734863281, ...}
${\displaystyle \scriptstyle V(6,5)\,}$ ${\displaystyle \scriptstyle 5^{n}+1\,}$ A034474 {2, 6, 26, 126, 626, 3126, 15626, 78126, 390626, 1953126, 9765626, 48828126, 244140626, 1220703126, 6103515626, 30517578126, 152587890626, ...}
${\displaystyle \scriptstyle U(7,6)\,}$ Repunits base 6 A003464(n)
n ≥ 1
{0, 1, 7, 43, 259, 1555, 9331, 55987, 335923, 2015539, 12093235, 72559411, 435356467, 2612138803, 15672832819, 94036996915, 564221981491, ...}
${\displaystyle \scriptstyle V(7,6)\,}$ ${\displaystyle \scriptstyle 6^{n}+1\,}$ A062394 {2, 7, 37, 217, 1297, 7777, 46657, 279937, 1679617, 10077697, 60466177, 362797057, 2176782337, 13060694017, 78364164097, 470184984577, ...}
${\displaystyle \scriptstyle U(8,7)\,}$ Repunits base 7 A023000 {0, 1, 8, 57, 400, 2801, 19608, 137257, 960800, 6725601, 47079208, 329554457, 2306881200, 16148168401, 113037178808, 791260251657, 5538821761600, ...}
${\displaystyle \scriptstyle V(8,7)\,}$ ${\displaystyle \scriptstyle 7^{n}+1\,}$ A034491 {2, 8, 50, 344, 2402, 16808, 117650, 823544, 5764802, 40353608, 282475250, 1977326744, 13841287202, 96889010408, 678223072850, 4747561509944, ...}
${\displaystyle \scriptstyle U(8,-9)\,}$ A015577 {0, 1, 8, 73, 656, 5905, 53144, 478297, 4304672, 38742049, 348678440, 3138105961, 28242953648, 254186582833, 2287679245496, 20589113209465, ...}
${\displaystyle \scriptstyle V(8,-9)\,}$ A?????? {2, 8, 82, ...}
${\displaystyle \scriptstyle U(9,8)\,}$ Repunits base 8 A023001 {0, 1, 9, 73, 585, 4681, 37449, 299593, 2396745, 19173961, 153391689, 1227133513, 9817068105, 78536544841, 628292358729, 5026338869833, ...}
${\displaystyle \scriptstyle V(9,8)\,}$ ${\displaystyle \scriptstyle 8^{n}+1\,}$ A062395 {2, 9, 65, 513, 4097, 32769, 262145, 2097153, 16777217, 134217729, 1073741825, 8589934593, 68719476737, 549755813889, 4398046511105, ...}
${\displaystyle \scriptstyle U(10,9)\,}$ Repunits base 9 A002452(n)
n ≥ 1
{0, 1, 10, 91, 820, 7381, 66430, 597871, 5380840, 48427561, 435848050, 3922632451, 35303692060, 317733228541, 2859599056870, 25736391511831, ...}
${\displaystyle \scriptstyle V(10,9)\,}$ ${\displaystyle \scriptstyle 9^{n}+1\,}$ A062396 {2, 10, 82, 730, 6562, 59050, 531442, 4782970, 43046722, 387420490, 3486784402, 31381059610, 282429536482, 2541865828330, 22876792454962, ...}
${\displaystyle \scriptstyle U(11,10)\,}$ Repunits base 10 A002275 {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111, 111111111111111, ...}
${\displaystyle \scriptstyle V(11,10)\,}$ ${\displaystyle \scriptstyle {10}^{n}+1\,}$ A062397 {2, 11, 101, 1001, 10001, 100001, 1000001, 10000001, 100000001, 1000000001, 10000000001, 100000000001, 1000000000001, 10000000000001, ...}
${\displaystyle \scriptstyle U(12,11)\,}$ Repunits base 11 A016123(n-1)
n ≥ 1
{0, 1, 12, 133, 1464, 16105, 177156, 1948717, 21435888, 235794769, 2593742460, 28531167061, 313842837672, 3452271214393, 37974983358324, ...}
${\displaystyle \scriptstyle V(12,11)\,}$ ${\displaystyle \scriptstyle {11}^{n}+1\,}$ A034524 {2, 12, 122, 1332, 14642, 161052, 1771562, 19487172, 214358882, 2357947692, 25937424602, 285311670612, 3138428376722, 34522712143932, ...}
${\displaystyle \scriptstyle U(13,12)\,}$ Repunits base 12 A016125(n-1)
n ≥ 1
{0, 1, 13, 157, 1885, 22621, 271453, 3257437, 39089245, 469070941, 5628851293, 67546215517, 810554586205, 9726655034461, 116719860413533, ...}
${\displaystyle \scriptstyle V(13,12)\,}$ ${\displaystyle \scriptstyle {12}^{n}+1\,}$ Axxxxxx {2, 13, 1729, 20737, ...}

References

• P. Ribenboim, The New Book of Prime Number Records (3 ed.), Springer, 1996, ISBN 0-387-94457-5.
• P. Ribenboim, My Numbers, My Friends, Springer, 2000, ISBN 0-387-98911-0.