מתוך ויקיפדיה, האנציקלופדיה החופשית
במתמטיקה , סדרת לוקאס היא סדרה של מספרים שלמים שאיבריה מקיימים נוסחת נסיגה מהצורה
a
n
+
2
=
P
⋅
a
n
+
1
−
Q
⋅
a
n
{\displaystyle \ a_{n+2}=P\cdot a_{n+1}-Q\cdot a_{n}}
, כאשר
P
{\displaystyle \ P}
ו-
Q
{\displaystyle \ Q}
קבועים. דוגמאות מוכרות לסדרות לוקאס הן סדרת פיבונאצ'י , מספרי מרסן , מספרי לוקאס וסדרת פל . הסדרות נקראות על שם אדוארד לוקאס , דוגמה: 1,3,4,7,11,18,29......
לאחר בחירת הקבועים P,Q, סדרת לוקאס מוגדרת באמצעות נוסחת הנסיגה
L
n
=
P
L
n
−
1
−
Q
L
n
−
2
{\displaystyle \ L_{n}=PL_{n-1}-QL_{n-2}}
, ותנאי ההתחלה הקובעים את
L
0
,
L
1
{\displaystyle \ L_{0},\,L_{1}}
. בפרט, סדרות לוקאס עם תנאי ההתחלה
U
0
(
P
,
Q
)
=
0
,
U
1
(
P
,
Q
)
=
1
{\displaystyle \ U_{0}(P,Q)=0,U_{1}(P,Q)=1}
(ונוסחת הנסיגה
U
n
=
P
U
n
−
1
(
P
,
Q
)
−
Q
U
n
−
2
(
P
,
Q
)
{\displaystyle \ U_{n}=PU_{n-1}(P,Q)-QU_{n-2}(P,Q)}
) נקראת סדרת לוקאס מהסוג הראשון , וסדרת לוקאס עם תנאי ההתחלה
V
0
(
P
,
Q
)
=
2
,
V
1
(
P
,
Q
)
=
P
{\displaystyle \ V_{0}(P,Q)=2,V_{1}(P,Q)=P}
(ונוסחת הנסיגה
V
n
=
P
V
n
−
1
(
P
,
Q
)
−
Q
V
n
−
2
(
P
,
Q
)
{\displaystyle \ V_{n}=PV_{n-1}(P,Q)-QV_{n-2}(P,Q)}
) נקראת סדרת לוקאס מהסוג השני .
למשל,
U
n
(
1
,
−
1
)
{\displaystyle \ U_{n}(1,-1)}
היא סדרת פיבונאצ'י ,
V
n
(
1
,
−
1
)
{\displaystyle \ V_{n}(1,-1)}
הם מספרי לוקאס ,
U
n
(
2
,
−
1
)
{\displaystyle \ U_{n}(2,-1)}
היא סדרת פל ,
V
n
(
2
,
−
1
)
{\displaystyle \ V_{n}(2,-1)}
היא סדרת פל-לוקאס ,
U
n
(
3
,
2
)
{\displaystyle \ U_{n}(3,2)}
הם מספרי מרסן ו-
U
n
(
6
,
8
)
=
2
n
−
1
(
2
n
−
1
)
{\displaystyle U_{n}(6,8)=2^{n-1}\left(2^{n}-1\right)}
היא סדרה בה נמצאים כל המספרים המשוכללים הזוגיים.
את נוסחת הנסיגה של סדרת לוקאס אפשר לכתוב בעזרת מטריצות:
(
L
n
L
n
−
1
)
=
(
P
Q
1
0
)
(
L
n
−
1
L
n
−
2
)
{\displaystyle \left({\begin{array}{c}L_{n}\\L_{n-1}\end{array}}\right)=\left({\begin{array}{cc}P&Q\\1&0\end{array}}\right)\left({\begin{array}{c}L_{n-1}\\L_{n-2}\end{array}}\right)}
. לכסון המטריצה מאפשר להגיע במהירות לנוסחה מפורשת של האיבר הכללי, התלויה בערכי ההתחלה. המשוואה האופיינית של סדרת לוקאס היא
x
2
−
P
x
+
Q
=
0
{\displaystyle x^{2}-Px+Q=0\,}
. נסמן את הדיסקרימיננטה
D
=
P
2
−
4
Q
{\displaystyle \ D=P^{2}-4Q}
, לפי נוסחת השורשים פתרון המשוואה הוא:
a
=
P
+
D
2
and
b
=
P
−
D
2
{\displaystyle a={\frac {P+{\sqrt {D}}}{2}}\quad {\text{and}}\quad b={\frac {P-{\sqrt {D}}}{2}}\,}
ולכן אם שני השורשים שונים אז
U
n
=
a
n
−
b
n
a
−
b
=
a
n
−
b
n
D
{\displaystyle U_{n}={\frac {a^{n}-b^{n}}{a-b}}={\frac {a^{n}-b^{n}}{\sqrt {D}}}}
ו-
V
n
=
a
n
+
b
n
{\displaystyle V_{n}=a^{n}+b^{n}\,}
ואם שני השורשים זהים,
U
n
=
n
S
n
−
1
{\displaystyle U_{n}=nS^{n-1}\,}
ו-
V
n
=
2
S
n
{\displaystyle V_{n}=2S^{n}\,}
כאשר מתקיים ש-
S
=
Q
=
P
2
{\displaystyle \ S={\sqrt {Q}}={\tfrac {P}{2}}}
.
סדרות לוקאס משני הסוגים עם אותם פרמטרים קשורות ביניהן בכמה זהויות בסיסיות. להלן טבלת זהויות עם המקרה הפרטי של סדרת פיבונאצ'י ומספרי לוקאס כדוגמה.
F
n
=
U
n
(
1
,
−
1
)
{\displaystyle F_{n}=U_{n}(1,-1)}
,
L
n
=
V
n
(
1
,
−
1
)
{\displaystyle L_{n}=V_{n}(1,-1)}
.
זהות כללית
מקרה פרטי
(
P
2
−
4
Q
)
U
n
=
V
n
+
1
−
Q
V
n
−
1
=
2
V
n
+
1
−
P
V
n
{\displaystyle (P^{2}-4Q)U_{n}={V_{n+1}-QV_{n-1}}=2V_{n+1}-PV_{n}\,}
5
F
n
=
L
n
+
1
+
L
n
−
1
=
2
L
n
+
1
−
L
n
{\displaystyle 5F_{n}={L_{n+1}+L_{n-1}}=2L_{n+1}-L_{n}\,}
V
n
=
U
n
+
1
−
Q
U
n
−
1
=
2
U
n
+
1
−
P
U
n
{\displaystyle V_{n}=U_{n+1}-QU_{n-1}=2U_{n+1}-PU_{n}\,}
L
n
=
F
n
+
1
+
F
n
−
1
=
2
F
n
+
1
−
F
n
{\displaystyle L_{n}=F_{n+1}+F_{n-1}=2F_{n+1}-F_{n}\,}
U
2
n
=
U
n
V
n
{\displaystyle U_{2n}=U_{n}V_{n}\,}
F
2
n
=
F
n
L
n
{\displaystyle F_{2n}=F_{n}L_{n}\,}
V
2
n
=
V
n
2
−
2
Q
n
{\displaystyle V_{2n}=V_{n}^{2}-2Q^{n}\,}
L
2
n
=
L
n
2
−
2
(
−
1
)
n
{\displaystyle L_{2n}=L_{n}^{2}-2(-1)^{n}\,}
U
n
+
m
=
U
n
U
m
+
1
−
Q
U
m
U
n
−
1
=
U
n
V
m
+
U
m
V
n
2
{\displaystyle U_{n+m}=U_{n}U_{m+1}-QU_{m}U_{n-1}={\frac {U_{n}V_{m}+U_{m}V_{n}}{2}}\,}
F
n
+
m
=
F
n
F
m
+
1
+
F
m
F
n
−
1
=
F
n
L
m
+
F
m
L
n
2
{\displaystyle F_{n+m}=F_{n}F_{m+1}+F_{m}F_{n-1}={\frac {F_{n}L_{m}+F_{m}L_{n}}{2}}\,}
V
n
+
m
=
V
n
V
m
−
Q
m
V
n
−
m
{\displaystyle V_{n+m}=V_{n}V_{m}-Q^{m}V_{n-m}\,}
L
n
+
m
=
L
n
L
m
−
(
−
1
)
m
L
n
−
m
{\displaystyle L_{n+m}=L_{n}L_{m}-(-1)^{m}L_{n-m}\,}