סדרת לוקאס

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

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

לכל שני פרמטרים שלמים P ו-Q סדרת לוקאס מהסוג הראשון $\ U_n(P,Q)$ מוגדרת באופן רקורסיבי:

$U_n(P,Q)=\begin{cases}0&\mbox{if }n=0;\\1&\mbox{if }n=1;\\P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)&\mbox{otherwise.}\end{cases}$

סדרת לוקאס מהסוג השני $\ V_n(P,Q)$ מוגדרת:

$V_n(P,Q)=\begin{cases}2&\mbox{if }n=0;\\P&\mbox{if }n=1;\\P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q)&\mbox{otherwise.}\end{cases}$

למשל, $\ U_n(1,-1)$ היא סדרת פיבונאצ'י, $\ V_n(1,-1)$ הם מספרי לוקאס, $\ U_n(2,-1)$ היא סדרת פל, $\ V_n(2,-1)$ היא סדרת פל-לוקאס ו-$\ U_n(3,2)$ הם מספרי מרסן.

נוסחה מפורשת

בשל הלינאריות של סדרת לוקאס קל למצוא נוסחה מפורשת סגורה לאיבר הכללי שלה. המשוואה האופיינית של סדרת לוקאס היא $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 \,$

ואם שני השורשים זהים מתקיים ש-$\ \tfrac{P}2 = \sqrt Q = S$ מקיים:

$U_n = nS^{n-1}\,$

$V_n=2S^n\,$

זהויות

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

זהות כללית	מקרה פרטי
$(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} \,$