Homogeneous Linear Recurrence Relation

11-02-2025

Homogeneous Linear Recurrence Relation

Homogeneous Linear Recurrence Relation คือ สมการเวียนเกิดเชิงเส้นที่มีความสัมพันธ์เชิงเส้นระหว่างสมาชิกในลำดับ โดยสมการเวียนเกิดเชิงเส้นที่เป็น Homogeneous จะมีรูปแบบดังนี้

an=c1an−1+c2an−2+⋯+ckan−ka_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k}

Solve with Hands

เนื่องจาก an=c1an−1+c2an−2+⋯+ckan−ka_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k} สามารถทำให้อยู่ในรูป an=D1r1n+D2r2n+⋯+Dkrkna_{n} = D_{1}r_{1}^{n} + D_{2}r_{2}^{n} + \dots + D_{k}r_{k}^{n} โดยที่ r1,r2,…,rkr_{1}, r_{2}, \dots, r_{k} คือรากของสมการเชิงเส้นที่เป็น Homogeneous และ D1,D2,…,DkD_{1}, D_{2}, \dots, D_{k} คือค่าคงที่ที่ต้องหา

Solve with Matrix Exponentiation

สำหรับ Homogeneous Linear Recurrence Relation ที่ดีกรี kk สามารถใช้การหา Linear Transformation จาก aba_{b} ไปยัง ab+ka_{b+k} ได้ดังนี้

[ab+1ab+2ab+3⋮ab+k]=[c1c2…ck−1ck10…0001…00⋮⋮⋱⋮⋮00…10][abab+1ab+2⋮ab+k−1]\begin{bmatrix} a_{b+1} \\ a_{b+2} \\ a_{b+3} \\ \vdots \\ a_{b+k} \end{bmatrix} = \begin{bmatrix} c_{1} & c_{2} & \dots & c_{k-1} & c_{k} \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 \end{bmatrix} \begin{bmatrix} a_{b} \\ a_{b+1} \\ a_{b+2} \\ \vdots \\ a_{b+k-1} \end{bmatrix}

Reference