คณิตศาสตร์ไม่ต่อเนื่อง - ความสัมพันธ์การเกิดซ้ำ
ในบทนี้เราจะพูดถึงวิธีการที่เทคนิคการวนซ้ำสามารถหาลำดับและใช้ในการแก้ปัญหาการนับได้ ขั้นตอนในการค้นหาเงื่อนไขของลำดับในลักษณะเรียกซ้ำเรียกว่าrecurrence relation. เราศึกษาทฤษฎีความสัมพันธ์การเกิดซ้ำเชิงเส้นและวิธีแก้ปัญหา สุดท้ายเราแนะนำฟังก์ชันการสร้างสำหรับการแก้ปัญหาความสัมพันธ์ที่เกิดซ้ำ
คำจำกัดความ
ความสัมพันธ์การเกิดซ้ำคือสมการที่กำหนดลำดับซ้ำ ๆ โดยที่เทอมถัดไปเป็นฟังก์ชันของคำศัพท์ก่อนหน้า (การแสดง $ F_n $ เป็นการรวมกันของ $ F_i $ กับ $ i <n $)
Example - ซีรีส์ฟีโบนักชี - $ F_n = F_ {n-1} + F_ {n-2} $ หอคอยแห่งฮานอย - $ F_n = 2F_ {n-1} + 1 $
ความสัมพันธ์การเกิดซ้ำเชิงเส้น
สมการการเกิดซ้ำเชิงเส้นขององศา k หรือลำดับ k คือสมการการเกิดซ้ำซึ่งอยู่ในรูปแบบ $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_k x_ {nk} $ ($ A_n $ เป็นค่าคงที่และ $ A_k \ neq 0 $) ในลำดับของตัวเลขเป็นพหุนามระดับที่หนึ่ง
นี่คือตัวอย่างบางส่วนของสมการการเกิดซ้ำเชิงเส้น -
| ความสัมพันธ์ที่เกิดซ้ำ | ค่าเริ่มต้น | แนวทางแก้ไข |
|---|---|---|
| F n = F n-1 + F n-2 | ก1 = ก2 = 1 | หมายเลขฟีโบนักชี |
| F n = F n-1 + F n-2 | 1 = 1 เป็น2 = 3 | ลูคัสนัมเบอร์ |
| F n = F n-2 + F n-3 | ก1 = ก2 = ก3 = 1 | ลำดับ Padovan |
| F n = 2F n-1 + F n-2 | 1 = 0 เป็น2 = 1 | หมายเลขเพลล์ |
วิธีแก้ความสัมพันธ์การเกิดซ้ำเชิงเส้น
สมมติว่าความสัมพันธ์การเกิดซ้ำเชิงเส้นสองลำดับคือ - $ F_n = AF_ {n-1} + BF_ {n-2} $ โดยที่ A และ B เป็นจำนวนจริง
สมการลักษณะเฉพาะสำหรับความสัมพันธ์การเกิดซ้ำข้างต้นคือ -
$$ x ^ 2 - ขวาน - B = 0 $$
สามกรณีอาจเกิดขึ้นในขณะที่ค้นหาราก -
Case 1- ถ้าสมการนี้แยกตัวประกอบเป็น $ (x- x_1) (x- x_1) = 0 $ และสร้างรากจริงที่แตกต่างกันสองรูท $ x_1 $ และ $ x_2 $ ดังนั้น $ F_n = ax_1 ^ n + bx_2 ^ n $ คือคำตอบ [ในที่นี้ a และ b คือค่าคงที่]
Case 2 - ถ้าสมการนี้แยกตัวประกอบเป็น $ (x- x_1) ^ 2 = 0 $ และสร้างรูทจริงเพียงรูทเดียว $ x_1 $ ดังนั้น $ F_n = a x_1 ^ n + bn x_1 ^ n $ คือคำตอบ
Case 3 - ถ้าสมการสร้างรากที่ซับซ้อนที่แตกต่างกันสองราก $ x_1 $ และ $ x_2 $ ในรูปเชิงขั้ว $ x_1 = r \ angle \ theta $ และ $ x_2 = r \ angle (- \ theta) $ ดังนั้น $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ คือคำตอบ
Problem 1
แก้ความสัมพันธ์การเกิดซ้ำ $ F_n = 5F_ {n-1} - 6F_ {n-2} $ โดยที่ $ F_0 = 1 $ และ $ F_1 = 4 $
Solution
สมการลักษณะเฉพาะของความสัมพันธ์การเกิดซ้ำคือ -
$$ x ^ 2 - 5x + 6 = 0, $$
ดังนั้น $ (x - 3) (x - 2) = 0 $
ดังนั้นรากคือ -
$ x_1 = 3 $ และ $ x_2 = 2 $
รากมีจริงและแตกต่าง ดังนั้นนี่คือรูปแบบของกรณีที่ 1
ดังนั้นวิธีแก้ปัญหาคือ -
$$ F_n = ax_1 ^ n + bx_2 ^ n $$
ที่นี่ $ F_n = a3 ^ n + b2 ^ n \ (As \ x_1 = 3 \ and \ x_2 = 2) $
ดังนั้น,
$ 1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b $
$ 4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b $
การแก้สมการทั้งสองนี้เราจะได้ $ a = 2 $ และ $ b = -1 $
ดังนั้นทางออกสุดท้ายคือ -
$$ F_n = 2.3 ^ n + (-1) 2 ^ n = 2.3 ^ n - 2 ^ n $$
Problem 2
แก้ไขความสัมพันธ์การเกิดซ้ำ - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ โดยที่ $ F_0 = 3 $ และ $ F_1 = 17 $
Solution
สมการลักษณะเฉพาะของความสัมพันธ์การเกิดซ้ำคือ -
$$ x ^ 2 - 10x -25 = 0 $$
ดังนั้น $ (x - 5) ^ 2 = 0 $
ดังนั้นจึงมีรูทจริงเพียงรูทเดียว $ x_1 = 5 $
เนื่องจากมีรูทที่มีมูลค่าจริงเพียงตัวเดียวจึงอยู่ในรูปแบบของกรณีที่ 2
ดังนั้นวิธีแก้ปัญหาคือ -
$ F_n = ax_1 ^ n + bnx_1 ^ n $
$ 3 = F_0 = a.5 ^ 0 + (b) (0.5) ^ 0 = a $
$ 17 = F_1 = a.5 ^ 1 + b.1.5 ^ 1 = 5a + 5b $
การแก้สมการทั้งสองนี้เราจะได้ $ a = 3 $ และ $ b = 2/5 $
ดังนั้นทางออกสุดท้ายคือ - $ F_n = 3.5 ^ n + (2/5) .n.2 ^ n $
Problem 3
แก้ความสัมพันธ์การเกิดซ้ำ $ F_n = 2F_ {n-1} - 2F_ {n-2} $ โดยที่ $ F_0 = 1 $ และ $ F_1 = 3 $
Solution
สมการลักษณะเฉพาะของความสัมพันธ์การเกิดซ้ำคือ -
$$ x ^ 2 -2x -2 = 0 $$
ดังนั้นรากคือ -
$ x_1 = 1 + i $ และ $ x_2 = 1 - i $
ในรูปแบบขั้ว
$ x_1 = r \ angle \ theta $ และ $ x_2 = r \ angle (- \ theta), $ โดยที่ $ r = \ sqrt 2 $ และ $ \ theta = \ frac {\ pi} {4} $
รากเป็นจินตนาการ ดังนั้นนี่คือรูปแบบของกรณีที่ 3
ดังนั้นวิธีแก้ปัญหาคือ -
$ F_n = (\ sqrt 2) ^ n (a cos (n. \ sqcap / 4) + b บาป (n. \ sqcap / 4)) $
$ 1 = F_0 = (\ sqrt 2) ^ 0 (a cos (0. \ sqcap / 4) + b บาป (0. \ sqcap / 4)) = a $
$ 3 = F_1 = (\ sqrt 2) ^ 1 (a cos (1. \ sqcap / 4) + b บาป (1. \ sqcap / 4)) = \ sqrt 2 (a / \ sqrt 2 + b / \ sqrt 2 ) $
การแก้สมการทั้งสองนี้เราจะได้ $ a = 1 $ และ $ b = 2 $
ดังนั้นทางออกสุดท้ายคือ -
$ F_n = (\ sqrt 2) ^ n (cos (n. \ pi / 4) + 2 บาป (n. \ pi / 4)) $
ความสัมพันธ์การเกิดซ้ำที่ไม่เป็นเนื้อเดียวกันและการแก้ปัญหาเฉพาะ
ความสัมพันธ์การเกิดซ้ำเรียกว่าไม่เป็นเนื้อเดียวกันหากอยู่ในรูปแบบ
$ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ โดยที่ $ f (n) \ ne 0 $
ความสัมพันธ์ซ้ำที่เป็นเนื้อเดียวกันที่เกี่ยวข้องคือ $ F_n = AF_ {n – 1} + BF_ {n-2} $
วิธีแก้ปัญหา $ (a_n) $ ของความสัมพันธ์การเกิดซ้ำที่ไม่เป็นเนื้อเดียวกันมีสองส่วน
ส่วนแรกคือการแก้ปัญหา $ (a_h) $ ของความสัมพันธ์การเกิดซ้ำที่เป็นเนื้อเดียวกันที่เกี่ยวข้องและส่วนที่สองคือโซลูชันเฉพาะ $ (a_t) $
$$ a_n = a_h + a_t $$
การแก้ปัญหาในส่วนแรกทำได้โดยใช้ขั้นตอนที่กล่าวไว้ในหัวข้อก่อนหน้านี้
ในการค้นหาวิธีแก้ปัญหาโดยเฉพาะเราพบโซลูชันการทดลองที่เหมาะสม
ให้ $ f (n) = cx ^ n $; ให้ $ x ^ 2 = ขวาน + B $ เป็นสมการลักษณะเฉพาะของความสัมพันธ์การเกิดซ้ำที่เป็นเนื้อเดียวกันและให้ $ x_1 $ และ $ x_2 $ เป็นรากของมัน
ถ้า $ x \ ne x_1 $ และ $ x \ ne x_2 $ ดังนั้น $ a_t = Ax ^ n $
ถ้า $ x = x_1 $, $ x \ ne x_2 $ แล้ว $ a_t = Anx ^ n $
ถ้า $ x = x_1 = x_2 $ ดังนั้น $ a_t = An ^ 2x ^ n $
ตัวอย่าง
ให้ความสัมพันธ์การเกิดซ้ำที่ไม่เป็นเนื้อเดียวกันเป็น $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ ที่มีรากลักษณะเฉพาะ $ x_1 = 2 $ และ $ x_2 = 5 $ โซลูชันการทดลองสำหรับค่าที่เป็นไปได้ที่แตกต่างกันของ $ f (n) $ มีดังนี้ -
| ฉ (n) | โซลูชันทดลองใช้ |
|---|---|
| 4 | ก |
| 5.2 n | An2 n |
| 8.5 n | An5 n |
| 4 n | A4 n |
| 2n 2 + 3n + 1 | 2 + พันล้าน + C |
Problem
แก้ความสัมพันธ์การเกิดซ้ำ $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7.5 ^ n $ โดยที่ $ F_0 = 4 $ และ $ F_1 = 3 $
Solution
นี่คือความสัมพันธ์ที่ไม่เป็นเนื้อเดียวกันเชิงเส้นโดยสมการเอกพันธ์ที่เกี่ยวข้องคือ $ F_n = 3F_ {n-1} + 10F_ {n-2} $ และ $ f (n) = 7.5 ^ n $
สมการลักษณะเฉพาะของความสัมพันธ์ที่เป็นเนื้อเดียวกันที่เกี่ยวข้องคือ -
$$ x ^ 2 - 3x -10 = 0 $$
หรือ, $ (x - 5) (x + 2) = 0 $
หรือ$ x_1 = 5 $ และ $ x_2 = -2 $
ดังนั้น $ a_h = a.5 ^ n + b. (- 2) ^ n $ โดยที่ a และ b เป็นค่าคงที่
เนื่องจาก $ f (n) = 7.5 ^ n $ นั่นคือในรูปแบบ $ cx ^ n $ วิธีการทดลองที่เหมาะสมจะเป็น $ Anx ^ n $
$ a_t = Anx ^ n = An5 ^ n $
หลังจากวางคำตอบในความสัมพันธ์การเกิดซ้ำเราจะได้ -
$ An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7.5 ^ n $
หารทั้งสองข้างด้วย $ 5 ^ {n-2} $ เราจะได้
$ An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7.5 ^ 2 $
หรือ$ 25An = 15An - 15A + 10An - 20A + 175 $
หรือ$ 35A = 175 $
หรือ$ A = 5 $
ดังนั้น$ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $
คำตอบของความสัมพันธ์การเกิดซ้ำสามารถเขียนเป็น -
$ F_n = a_h + a_t $
$ = a.5 ^ n + b. (- 2) ^ n + n5 ^ {n + 1} $
การใส่ค่า $ F_0 = 4 $ และ $ F_1 = 3 $ ในสมการด้านบนเราจะได้ $ a = -2 $ และ $ b = 6 $
ดังนั้นวิธีแก้ปัญหาคือ -
$ F_n = n5 ^ {n + 1} + 6. (- 2) ^ n -2.5 ^ n $
การสร้างฟังก์ชัน
Generating Functions แสดงถึงลำดับที่แต่ละเทอมของลำดับแสดงเป็นค่าสัมประสิทธิ์ของตัวแปร x ในอนุกรมกำลังที่เป็นทางการ
ในทางคณิตศาสตร์สำหรับลำดับที่ไม่มีที่สิ้นสุดพูด $ a_0, a_1, a_2, \ dots, a_k, \ dots, $ ฟังก์ชันสร้างจะเป็น -
$$ G_x = a_0 + a_1x + a_2x ^ 2 + \ dots + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k $$
บางพื้นที่การใช้งาน
การสร้างฟังก์ชันสามารถใช้เพื่อวัตถุประสงค์ดังต่อไปนี้ -
สำหรับการแก้ปัญหาการนับที่หลากหลาย ตัวอย่างเช่นจำนวนวิธีในการเปลี่ยนแปลงสำหรับ Rs 100 บันทึกย่อของนิกาย Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 และ Rs.50
สำหรับการแก้ไขความสัมพันธ์ที่เกิดซ้ำ
สำหรับการพิสูจน์อัตลักษณ์บางอย่างของ Combinatorial
สำหรับการค้นหาสูตรที่ไม่แสดงอาการสำหรับเงื่อนไขของลำดับ
Problem 1
อะไรคือฟังก์ชันที่สร้างขึ้นสำหรับลำดับ $ \ lbrace {a_k} \ rbrace $ กับ $ a_k = 2 $ และ $ a_k = 3k $?
Solution
เมื่อ $ a_k = 2 $ สร้างฟังก์ชัน $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ จุด $
เมื่อ $ a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ dots \ จุด $
Problem 2
อะไรคือฟังก์ชั่นการสร้างของอนุกรมอนันต์ $ 1, 1, 1, 1, \ dots $?
Solution
ที่นี่ $ a_k = 1 $ สำหรับ $ 0 \ le k \ le \ infty $
ดังนั้น $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $
ฟังก์ชันการสร้างที่มีประโยชน์บางอย่าง
สำหรับ $ a_k = a ^ {k}, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ dots \ dots \ dots = 1 / (1 - ขวาน) $
สำหรับ $ a_ {k} = (k + 1), G (x) = \ sum_ {k = 0} ^ {\ infty} (k + 1) x ^ {k} = 1 + 2x + 3x ^ {2} \ dots \ dots \ dots = \ frac {1} {(1 - x) ^ {2}} $
สำหรับ $ a_ {k} = c_ {k} ^ {n}, G (x) = \ sum_ {k = 0} ^ {\ infty} c_ {k} ^ {n} x ^ {k} = 1 + c_ {1} ^ {n} x + c_ {2} ^ {n} x ^ {2} + \ dots \ dots \ dots + x ^ {2} = (1 + x) ^ {n} $
สำหรับ $ a_ {k} = \ frac {1} {k!}, G (x) = \ sum_ {k = 0} ^ {\ infty} \ frac {x ^ {k}} {k!} = 1 + x + \ frac {x ^ {2}} {2!} + \ frac {x ^ {3}} {3!} \ dots \ dots \ dots = e ^ {x} $