סדרת לוקאס

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

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

נוסחה מפורשת[עריכת קוד מקור | עריכה]

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

זהויות[עריכת קוד מקור | עריכה]

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

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