notes.npwitknpwitk.com ↗

06 Recurrence Relations

Updated 4 Oct 2026

ต้องบอกก่อนว่าบทนี้จะไม่เหมือนกับ Sequence & Series ในมอปลายนะ จริง ๆ ก็เหมือนนั่นแหละ แต่ว่าอันนี้จะมองในภาพกว้าง ไม่ได้มีสมการมาให้ตรง ๆ ต้องวิเคราะห์เอง โดยใช้ Tool ที่สอนในบทนี้

  • Tool for analyzing properties of recursive algorithm
  • A recurrence a relation for the sequence a0,a1,a2,…a_0, a_1, a_2,\dotso is an equation that relates ana_n to certain of its predecessors a0,a1,… ,an−1a_0, a_1,\dotso, a_{n-1}
  • Initial Conditions for the sequence a0,a1,a2,…a_0, a_1, a_2,\dotso are explicitly given values for a finite number of terms of the sequence.
  • สิ่งที่ควรรู้
an=an−1+d\boxed{a_n=a_{n-1}+d}

Recurrence Relation ต้อง depend on กับ พจน์ก่อนหน้า ด้วยนะ!

  • ถ้าสมมติว่าเป็น An=(1.12)n(1000)A_n=(1.12)^n(1000) แบบนี้ไม่ไช่ จะเรียกว่า Explicit formula

Solving Recurrence Relations

Derive Explicit Formula

  • To solve a recurrence relation involving a0,a1,a2,…a_0, a_1, a_2,\dotso is to find an “explicit formula” for the general term ana_n
  • In this section we discuss two methods of solving recurrence relations

Iterative Unfolding

  • We use the recurrence relation to write the nn-th term ana_n in terms of certain of its predecessors an−1,… ,a0a_{n−1},\dotso,a_0

    • We then successively use the recurrence relation to replace each of an−1,…a_{n−1},\dotso by certain of their predecessors. We continue until an explicit formula is obtained.
    • หรือว่าทำไปเรื่อย ๆ จนกว่าจะเจอ Pattern แล้วสามารถเขียนใน Term kk ได้นะ

  • ต้องใช้

    1. Recurrence Relation
    2. Initial Conditions
      ทั้งคู่เพื่อให้ได้ Explicit Formula

Example

an=an−1+3a_n=a_{n-1}+3
  • โดยมี Initial condition เป็น a1=2a_1=2
  • เรียกขั้นตอนแรกว่า Iteratively unfold the recurrence relation
an=an−1+3=an−2+3+3=an−3+3+3+3an=an−k+3k (In general)\begin{aligned} a_n&=a_{n-1}+3 \\ &=a_{n-2}+3+3 \\ &=a_{n-3}+3+3+3 \\ \\ a_n&=a_{n-k}+3k \text{ (In general)} \end{aligned}
  • ต่อไปเราก็จะ make use จาก a1a_1 นะ โดยให้ n−k=1n-k=1 → k=n−1k=n-1 (เรียกขั้นตอนนี้ว่า Make use of the initial condition)
an=a1+3(n−1)=2+3(n−1)\begin{aligned} a_n&=a_1+3(n-1) \\ &=2+3(n-1) \end{aligned}

Things You Should Know

Sn=a1(1−rn)1−rS_n=\frac{a_1(1-r^n)}{1-r}

Linear Homogeneous Recurrence Relations with Constant Coefficients (LHRRCC)

  • A linear homogeneous recurrence relation of order k with constant coefficients is a recurrence relation of the form an=c1an−1+c2an−2+…+ckan−k; ck≠0a_n=c_1a_{n-1}+c_2a_{n-2}+\dotso+c_ka_{n-k}\quad\quad ;\text{ }c_k\ne0
    • ส่วน c1,c2,… ,ckc_1,c_2,\dotso,c_k เป็น Real number แต่ข้อห้ามคือ ck≠0c_k\ne 0
  • The following are linear homogenous
    • Pn=1.11Pn−1P_n=1.11P_{n-1} (degree 1)
    • fn=fn−1+fn−2f_n=f_{n-1}+f_{n-2} (degree 2)
    • an=an−5a_n=a_{n-5} (degree 5)
  • The following are NOT linear homogenous
    • an=an−1+(an−2)2a_n=a_{n-1}+(a_{n-2})^2 (not linear)
    • Hn=2Hn−1+1H_n=2H_{n-1}+1 (not homogenous เพราะมี +1+1)
    • Bn=nBn−1B_n=nB_{n-1} (non-constant coefficients)

Solving LHRRCC of Order 2 with Constant Coefficients

  • To solve an=c1an−1+c2an−2a_n=c_1a_{n-1}+c_2a_{n-2} do the following:
    1. Determine the roots r1r_1 and r2r_2 of the quadratic equation (คำตอบจากสมการที่จะแก้ต่อไปนี้!) t2−c1t−c2=0t^2-c_1t-c_2=0
    2. If r1≠r2r_1\ne r_2, an explicit formula for ana_n has the form an=br1n+dr2n\boxed{a_n=br_{1}^n+dr_{2}^n}
    If r1=r2r_1=r_2, an explicit formula for ana_n has the form
    an=br1n+dnr2n \boxed{a_n=br_{1}^n+dnr_{2}^n}
    3. Determine bb and dd using the initial conditions
    - จริง ๆ อาจจะงง ๆ วิธีก็คือหา bb กับ dd โดยใช้ Initial conditions a0a_0 กับ a1a_1 ที่ให้มา ตั้งสมการดังนี้
    a0=br10+dr20a1=br11+dr21 \begin{aligned} a_0=b r_{1}^0+dr_2^{0} \\ a_1=b r_{1}^1+dr_2^{1} \end{aligned}
    - แล้วก็แก้สมการ 2 ตัวแปรเพื่อหาค่า b,db,d
    4. แทนกลับเข้าสมการ เสร็จแล้ววววว!