סדרת לוקאס

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

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

לאחר בחירת הקבועים P,Q, סדרת לוקאס מוגדרת באמצעות נוסחת הנסיגה $\ L_{n}=PL_{n-1}-QL_{n-2}$ , ותנאי ההתחלה הקובעים את $\ L_{0},\,L_{1}$ . בפרט, סדרות לוקאס עם תנאי ההתחלה $\ U_{0}(P,Q)=0,U_{1}(P,Q)=1$ (ונוסחת הנסיגה $\ U_{n}=PU_{n-1}(P,Q)-QU_{n-2}(P,Q)$ ) נקראת סדרת לוקאס מהסוג הראשון, וסדרת לוקאס עם תנאי ההתחלה $\ V_{0}(P,Q)=2,V_{1}(P,Q)=P$ (ונוסחת הנסיגה $\ V_{n}=PV_{n-1}(P,Q)-QV_{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}-QV_{n-1}}=2V_{n+1}-PV_{n}\,$	$5F_{n}={L_{n+1}+L_{n-1}}=2L_{n+1}-L_{n}\,$
$V_{n}=U_{n+1}-QU_{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}-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}={\frac {F_{n}L_{m}+F_{m}L_{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}\,$