ความสัมพันธ์ เวียนเกิด (Recurence Relation)

ตัวอย่าง 1 ให้ {a_n} เป็นลำดับที่สอดคล้องความสัมพันธ์เวียนเกิด
                   a_n = a_n-1 + a_n-2 เมื่อ n > 1
ถ้า a₀ = 1 และ  a₁ = 1  จงหา a₂, a₃, a₄, a₅, a₆

ตัวอย่าง 2  ผลเฉลยของความสัมพันธ์เวียนเกิด { a_n} เมื่อ a₀ = 3, a₁ =6 และ
  a_n = 2 a_n-1 - a_n-2  เมื่อ n > 1
     คือ (จะเรียนทีหลัง )  ลำดับ {b_n} เมื่อ b_n = 3n
    เพราะ b₁ = 3 , b₂ = 6 และได้ว่า
             2 b_n-1 - b_n-2 = 2(3(n-1)) - 3(n-2) = 3n = b_n

ตัวอย่าง 3 ลำดับฟิโบนักชี (Fibonacci ' saquence) ชาว อิตาลี ค.ศ. 1170-1240
     คือลำดับ {a_n} ที่เขียนอยู่ในรูปแบบความสัมพันธ์เวียนเกิด
   a_n = a_n-1 + a_n-2  ทุก n > 1และ a₀ = 1 , a₁ = 1

ตัวอย่าง 4 ปัญหา หอคอยฮานอย (The Tower of Hanoi )  เป็นเกมในการเคลื่อนย้ายวงกลม 3 วง
     ที่มีขนาดต่างกันที่อยู่ในเสาต้นที่1  ไปยังต้นที่ 2 โดยมีเงื่อนไขว่า มีเสา 3 ต้น
     (เสาต้นที่1 มีวงกลมซ้อนกัน 3 วง  วงใหญ่สุดอยู่ด้านล่างสุด และวงเล็กสุดอยู่บนสุด
      เสาต้นที่2 และต้นที่ 3 ว่างเปล่า )  และในการเคลื่อนย้ายวงกลมสามารถเคลื่อนย้าย
      วงกลมทีละวงไปยังเสาทั้ง 3 ต้น  แต่ห้ามวงกลมขนาดใหญ่ซ้อนทับวงกลมขนาดเล็ก
      ถามว่าจำนวนครั้งที่น้อยที่สุดที่ทำได้จะเป็นเท่าไร
จากปัญหานี้สามารถสร้างเป็นลำดับที่เป็นความสัมพันธ์เวียนเกิดได้ว่า
ให้ ลำดับ {H_n} เป็นลำดับของจำนวนครั้งในการทำสำเร็จเมื่อมีวงกลมอยู่ n วง ด้วยกัน
จะได้ว่า  H1 = 1
และ H_n = H_n-1 + 1 + H_n-1  ( ย้ายวงกลม n-1 วง จากเสาต้นที่ 1 ไปยังต้นที่3 ต้องใช้จำนวน H_n-1 ครั้ง จากนั้นย้ายวงกลมที่ใหญ่ที่สุดในเสาที่ 1 ไปยังเสาที่ 2 ซึ่งใช้จำนวน 1 ครั้ง หลังจากนั้นย้ายวงกลม n-1 วง จากเสาต้นที่ 3 ไปยังต้นที่ 2 ต้องใช้จำนวน H_n-1 ครั้ง )
จึงได้ว่า    H_n = 2 H_n-1 + 1
 

การหาผลเฉลยของความสัมพันธ์เวียนเกิด

1. โดยวิธีการทำซ้ำ

=  2(2S_n-2)  =  2²S_n-2
=  2²(2S_n-3)) = 2³S_n-3
=   2³(2S_n-4) = 2⁴S_n-4
 =  ....
= 2^n-2 (2S₁) = 2^n-1S₁
=  2^n-1(2S0) =2ⁿ

  = 2(2H_n-2 +1) +1  = 2² H_n-2 + 2 +1
  = 2²(2H_n-3 + 1) +2+1 = 2³H_n-3 + 2² + 2 + 1
  =  2³(2H_n-4 +1) +2² + 2 +1 = 2⁴H_n-4 + 2³ + 2² + 2 + 1
   =...
  =  2^n-1H₁ + 2^n-2 + 2^n-3 + ... + 2 + 1
  = 2^n-1 + 2^n-2 + ... + 2 + 1
                = 2ⁿ -1

2. การหาผลเฉลย ของความสัมพันธ์เวียนเกิดเอกพันธ์เชิงเส้น

 a_n = c₁a_n-1 +c₂a_n-2 + ... + c_ka_n-k  เมื่อ c₁, c₂,  ... , c_k เป้นค่าคงตัว ที่ c_k น 0

1. P_n= (1.11)P_n-1 เป็นความสัมพันธ์เวียนเกิดเอกพันธ์เชิงเส้นอันดับ 1
   2. f_n = f_n-1 + f_n-2     เป็นความสัมพันธ์เวียนเกิดเอกพันธ์เชิงเส้นอันดับ 2
     3. a_n = a_n-1 + 2 a_n-3   เป็นความสัมพันธ์เวียนเกิดเอกพันธ์เชิงเส้นอันดับ 3
   4. a_n = a_n-5     เป็นความสัมพันธ์เวียนเกิดเอกพันธ์เชิงเส้นอันดับ 5

ตัวอย่าง  a_n = 2a_n-1 - a_n-2 ทุก n > 1 เป็นความสัมพันธ์เวียนเกิดเอกพันธ์เชิงเส้นอันดับ 2

จะได้ว่า ลำดับ {b_n} ที่ b_n = 3n ทุก  n  และ ลำดับ {c_n} ที่ c_n = 5  ทุก n
ต่างเป็นผลเฉลย  แต่ b_n  น  c_n ทุก n

ทฤษฎีบท  ให้ c₁, c₂ เป็นจำนวนจริง ถ้า r² - c₁r - c₂  = 0 (เรียกสมการลักษณะเฉพาะ)   มีผลเฉลยที่แตกต่างกัน r₁, r₂

แล้วลำดับ {b_n} จะเป็นผลเฉลยของความสัมพันธ์เวียนเกิด a_n = c₁a_n-1 + c₂a_n-2 ก็ต่อเมื่อ b_n = d₁r₁ⁿ + d₂r₂ⁿ
ทุก n   โดยที่ d₁ , d₂ เป็นค่าคงตัว

ตัวอย่าง  จงหาผลเฉลยของความสัมพันธ์เวียนเกิด

  a_n = a_n-1 + 2a_n-2  เมื่อ a₀ = 2 , a₁ = 7

ผลเฉลยของสมการลักษณะเฉพาะ r² - (1)r - 2 = 0  คือ r = 2, -1
 ดังนั้น ลำดับ {b_n} จะเป็นผลเฉลยของความสัมพันธ์เวียนเกิด ก็ต่อเมื่อ
b_n = d₁2ⁿ + d₂(-1)ⁿ  ทุก n โดยที่ d₁, d₂ เป็นค่าคงตัว
 หา d₁ ,d₂ จาก เงื่อนไขเริ่มต้น a₀ = 2 และ a₁ = 7
 ดังนั้น     2 = a₀ = b₀ = d₁ + d₂ ...(1)
 และ     7 = a₁ = b₁ = d₁(2) + d₂ (-1)   ...(2)
 จากสมการ (1) และ (2)  จะได้ว่า d₁ = 3 และ d₂ = -1
 ดังนั้น  b_n = 3 2ⁿ - (-1)ⁿ ทุก n เป็นผลเฉลยของความสัมพันธ์เวียนเกิด

ตัวอย่าง จงหาผลเฉลยของลำดับ ฟิโบนักชี (Fibonacci)

  a_n = a_n-1 + a_n-2  เมื่อ a₀ = 1 และ a₁ = 1

ทฤษฎีบท  ให้ c₁, c₂ เป็นจำนวนจริง ถ้า r² - c₁r - c₂  = 0 มีผลเฉลยเพียงค่าเดียว  r₀, r₀

แล้วลำดับ {b_n} จะเป็นผลเฉลยของความสัมพันธ์เวียนเกิด a_n = c₁a_n-1 + c₂a_n-2 ก็ต่อเมื่อ b_n = d₁r₀ⁿ + d₂nr₀ⁿ ทุก n
 โดยที่ d₁ , d₂ เป็นค่าคงตัว

ตัวอย่าง  จงหาผลเฉลยของความสัมพันธ์เวียนเกิด

  a_n = 6a_n-1 - 9a_n-2  เมื่อ a₀ = 1 , a₁ = 6

ผลเฉลยของสมการลักษณะเฉพาะ r² - (6)r - (-9) = 0  คือ r = 3, 3
 ดังนั้น ลำดับ {b_n} จะเป็นผลเฉลยของความสัมพันธ์เวียนเกิด ก็ต่อเมื่อ
 b_n = d₁3ⁿ + d₂n(3)ⁿ  ทุก n โดยที่ d₁, d₂ เป็นค่าคงตัว
 หา d₁ ,d₂ จาก เงื่อนไขเริ่มต้น a₀ = 1 และ a₁ = 6
 ดังนั้น   1 = a₀ = b₀ = d₁         .....(1)
 และ   6 = a₁ = b₁ = d₁(3) + d₂ (1) (3)    ....(2)
 จากสมการ (1) และ (2)  จะได้ว่า d₁ = 1 และ d₂ = 1
 ดังนั้น  b_n = 3ⁿ +  n 3ⁿ = (n+1)3ⁿ ทุก n เป็นผลเฉลยของความสัมพันธ์เวียนเกิด

ผลเฉลยที่แตกต่างกันทั้งหมด k ผลเฉลย   r₁, r₂  , ... , r_k
 แล้วลำดับ {b_n} จะเป็นผลเฉลยของความสัมพันธ์เวียนเกิด
a_n = c₁a_n-1 + c₂a_n-2 +  ...  + c_ka_k-1 ก็ต่อเมื่อ
 b_n = d₁r₁ⁿ + d₂r₂ⁿ + ... + d_k r_kⁿ ทุก n  โดยที่ d₁ , d₂ , ... , d_k เป็นค่าคงตัว

ตัวอย่าง  จงหาผลเฉลยของความสัมพันธ์เวียนเกิด

  a_n = 6a_n-1 - 11a_n-2 + 6a_n-3  เมื่อ a₀ = 2 , a₁ = 5, a₂ = 15

ผลเฉลยของสมการลักษณะเฉพาะ r³ - 6r² + 11r - 6 = 0  คือ r = 1, 2, 3
 ดังนั้น ลำดับ {b_n} จะเป็นผลเฉลยของความสัมพันธ์เวียนเกิด ก็ต่อเมื่อ
 b_n = d₁1ⁿ + d₂ 2ⁿ + d₃ 3ⁿ  ทุก n โดยที่ d₁, d₂, d₃ เป็นค่าคงตัว
 หา d₁, d₂, d₃  จาก เงื่อนไขเริ่มต้น a₀ = 2 , a₁ = 5 และ a₂ = 15
 ดังนั้น     2 = a₀ = b₀ = d₁ + d₂ + d₃     .......(1)
     5 = a₁ = b₁ = d₁ + d₂ (2) + d₃ (3)   ......(2)
            15 =  a₂ = b₂ = d₁ + d₂ (4) + d₃(9) .......(3)
 จากสมการ (1) , (2) และ (3)  จะได้ว่า d₁ = 1 , d₂ = -1 และ d₃ = 2
 ดังนั้น  b_n = 1 -  2ⁿ  + 2 3ⁿ  ทุก n เป็นผลเฉลยของความสัมพันธ์เวียนเกิด