การแก้สมการเวียนบังเกิดเชิงเส้น

พิจารณาความสัมพันธ์เวียนบังเกิด (recurrence relations): $F(n) = A\cdot F(n-1) + B\cdot F(n-2)$ และมีค่าเริ่มต้น $F(0)$ และ $F(1)$

ข้อสังเกต 1: ถ้าฟังก์ชัน $f$ และ $g$ สอดคล้องกับความสัมพันธ์เวียนบังเกิดข้างต้น $f+g$ ก็จะสอดคล้องด้วย
บทพิสูจน์: พิสูจน์โดยการแทนค่า

[X]

ข้อสังเกต 2: ฟังก์ชันดังกล่าวเป็นฟังก์ชัน exponential ถ้า $A> 0$ และ $B\geq 0$
บทพิสูจน์:
(lowerbound): เราจะแสดงว่า $F$ มีค่ามากกว่า exponential function บางอัน

สามารถตรวจสอบได้ว่า $F$ เป็นฟังก์ชันไม่ลดลง นั่นคือ $F(n')\geq F(n)$ เมื่อ $n'\geq n$

ให้ $k$ เป็นจำนวนเต็มที่มากกว่า $2\cdot(2/A)$ (จริง ๆ ควรใช้สัญลักษณ์ ceiling แต่ยังหาไม่เจอว่าทำใน ASCIIMathMLได้อย่างไร) พิจารณา
$F(n+k)=AF(n+k-1) + BF(n+k-2) $
$= AF(n+k-1) + AF(n+k-3) + BF(n+k-4)$
$= AF(n+k-1) + AF(n+k-3) + AF(n+k-5) + BF(n+k-6)$
$=\sum_{i=1}^{k//2} AF(n+k+1-2i) + BF(n) \geq (k/2)\cdot AF(n+1) \geq 2F(n)$
นั่นคือ $F(n+k)\geq 2F(n)$ หรือ $F(n)\geq C\cdot 2^(n//k)$ สำหรับค่า $C$ บางค่า

(upperbound): เราจะแสดงว่า $F$ มีค่าไม่เกิน exponential function บางอันเช่นกัน
$F(n)=AF(n-1)+BF(n-2)\leq AF(n-1)+BF(n-1)=(A+B)F(n-1)$ หรือ
$F(n)\leq C'\cdot (A+B)^n$ สำหรับค่าคงที่ $C'$ บางค่า

[X]

ดังนั้นวิธีการที่เราจะพิจารณาต่อไปก็คือการพยายามหา exponential function ที่สอดคล้องกับเงื่อนไขดังกล่าว

คราวหน้ามาต่อครับ...