סדרת לוקאס

במתמטיקה, סדרת לוקאס היא סדרה של מספרים שלמים שאיבריה מקיימים נוסחת נסיגה מהצורה $\ a_{n+2} = P\cdot a_{n+1}-Q\cdot a_n$, כאשר $\ P$ ו-$\ Q$ קבועים. דוגמאות מוכרות לסדרות לוקאס הן סדרת פיבונאצ'י, מספרי מרסן, מספרי לוקאס וסדרת פל. הסדרות נקראות על שם אדוארד לוקאס.

הגדרה פורמלית

לאחר בחירת הקבועים P,Q, סדרת לוקאס מוגדרת באמצעות נוסחת הנסיגה $\ L_n = P L_{n-1}-Q L_{n-2}$, ותנאי ההתחלה הקובעים את $\ L_0,\, L_1$. בפרט, סדרות לוקאס עם תנאי ההתחלה $\ U_0(P,Q) = 0, U_1(P,Q) = 1$ (ונוסחת הנסיגה $\ U_n = P U_{n-1}(P,Q)-Q U_{n-2}(P,Q)$) נקראת סדרת לוקאס מהסוג הראשון, וסדרת לוקאס עם תנאי ההתחלה $\ V_0(P,Q) = 2, V_1(P,Q) = P$ (ונוסחת הנסיגה $\ V_n = P V_{n-1}(P,Q)-Q V_{n-2}(P,Q)$) נקראת סדרת לוקאס מהסוג השני.

למשל, $\ U_n(1,-1)$ היא סדרת פיבונאצ'י, $\ V_n(1,-1)$ הם מספרי לוקאס, $\ U_n(2,-1)$ היא סדרת פל, $\ V_n(2,-1)$ היא סדרת פל-לוקאס, $\ U_n(3,2)$ הם מספרי מרסן ו-$U_n(6,8)=2^{n-1}\left(2^n-1\right)$ היא סדרה בה נמצאים כל המספרים המשוכללים הזוגיים.

נוסחה מפורשת

את נוסחת הנסיגה של סדרת לוקאס אפשר לכתוב בעזרת מטריצות: $\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 - Px + Q=0 \,$. נסמן את הדיסקרימיננטה $\ D=P^2 - 4Q$, לפי נוסחת השורשים פתרון המשוואה הוא:

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

ולכן אם שני השורשים שונים אז

$U_n= \frac{a^n-b^n}{a-b} = \frac{a^n-b^n}{ \sqrt{D}}$ ו-

$V_n=a^n+b^n \,$

ואם שני השורשים זהים, $U_n = nS^{n-1}\,$ ו- $V_n=2S^n\,$ כאשר מתקיים ש-$\ S = \sqrt{Q} = \tfrac{P}2$.

זהויות

סדרות לוקאס משני הסוגים עם אותם פרמטרים קשורות ביניהן בכמה זהויות בסיסיות. להלן טבלת זהויות עם המקרה הפרטי של סדרת פיבונאצ'י ומספרי לוקאס כדוגמה.

$F_n=U_n(1,-1)$ , $L_n=V_n(1,-1)$.

זהות כללית	מקרה פרטי
$(P^2-4Q) U_n = {V_{n+1} - Q V_{n-1}}=2V_{n+1}-P V_n \,$	$5F_n = {L_{n+1} + L_{n-1}}=2L_{n+1} - L_{n} \,$
$V_n = U_{n+1} - Q U_{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_{n+m} = U_n U_{m+1} - Q U_m U_{n-1}=\frac{U_nV_m+U_mV_n}{2} \,$	$F_{n+m} = F_n F_{m+1} + F_m F_{n-1}=\frac{F_nL_m+F_mL_n}{2} \,$
$V_{n+m} = V_n V_m - Q^m V_{n-m} \,$	$L_{n+m} = L_n L_m - (-1)^m L_{n-m} \,$