סדרת לוקאס

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

במתמטיקה, סדרת לוקאס היא סדרה של מספרים שלמים שאיבריה מקיימים את נוסחת הנסיגה \ 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} \,