Toán học rời rạc - Mối quan hệ lặp lại

Trong chương này, chúng ta sẽ thảo luận về cách các kỹ thuật đệ quy có thể lấy ra các chuỗi và được sử dụng để giải các bài toán đếm. Thủ tục tìm các số hạng của một dãy theo cách đệ quy được gọi làrecurrence relation. Chúng tôi nghiên cứu lý thuyết về quan hệ tuần hoàn tuyến tính và các giải pháp của chúng. Cuối cùng, chúng tôi giới thiệu các hàm tạo để giải quyết các quan hệ lặp lại.

Định nghĩa

Quan hệ lặp lại là một phương trình xác định một cách đệ quy một chuỗi trong đó số hạng tiếp theo là hàm của các số hạng trước đó (Biểu diễn $ F_n $ dưới dạng một số kết hợp của $ F_i $ với $ i <n $).

Example - Chuỗi Fibonacci - $ F_n = F_ {n-1} + F_ {n-2} $, Tháp Hà Nội - $ F_n = 2F_ {n-1} + 1 $

Mối quan hệ lặp lại tuyến tính

Phương trình lặp lại tuyến tính bậc k hoặc bậc k là phương trình lặp lại có định dạng $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ chấm A_k x_ {nk} $ ($ A_n $ là hằng số và $ A_k \ neq 0 $) trên một dãy số dưới dạng đa thức bậc nhất.

Đây là một số ví dụ về phương trình lặp lại tuyến tính -

Quan hệ lặp lại	Giá trị ban đầu	Các giải pháp
F _n = F _n-1 + F _n-2	a ₁ = a ₂ = 1	Số Fibonacci
F _n = F _n-1 + F _n-2	a ₁ = 1, a ₂ = 3	Số Lucas
F _n = F _n-2 + F _n-3	a ₁ = a ₂ = a ₃ = 1	Chuỗi Padovan
F _n = 2F _n-1 + F _n-2	a ₁ = 0, a ₂ = 1	Pell số

Cách giải quyết mối quan hệ lặp lại tuyến tính

Giả sử, một quan hệ lặp lại tuyến tính hai có thứ tự là - $ F_n = AF_ {n-1} + BF_ {n-2} $ trong đó A và B là các số thực.

Phương trình đặc trưng cho quan hệ lặp lại ở trên là -

$$ x ^ 2 - Ax - B = 0 $$

Ba trường hợp có thể xảy ra khi tìm ra gốc rễ -

Case 1- Nếu phương trình này thừa số là $ (x- x_1) (x- x_1) = 0 $ và nó tạo ra hai nghiệm thực phân biệt $ x_1 $ và $ x_2 $ thì $ F_n = ax_1 ^ n + bx_2 ^ n $ là nghiệm. [Ở đây, a và b là hằng số]

Case 2 - Nếu phương trình này thừa số là $ (x- x_1) ^ 2 = 0 $ và nó tạo ra một nghiệm thực duy nhất $ x_1 $, thì $ F_n = a x_1 ^ n + bn x_1 ^ n $ là nghiệm.

Case 3 - Nếu phương trình tạo ra hai nghiệm phức phân biệt, $ x_1 $ và $ x_2 $ ở dạng cực $ x_1 = r \ angle \ theta $ và $ x_2 = r \ angle (- \ theta) $ thì $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ là nghiệm.

Problem 1

Giải quan hệ lặp lại $ F_n = 5F_ {n-1} - 6F_ {n-2} $ trong đó $ F_0 = 1 $ và $ F_1 = 4 $

Solution

Phương trình đặc trưng của quan hệ tái diễn là -

$$ x ^ 2 - 5x + 6 = 0, $$

Vì vậy, $ (x - 3) (x - 2) = 0 $

Do đó, rễ là -

$ x_1 = 3 $ và $ x_2 = 2 $

Rễ là có thật và khác biệt. Vì vậy, đây là trường hợp 1

Do đó, giải pháp là -

$$ F_n = ax_1 ^ n + bx_2 ^ n $$

Ở đây, $ F_n = a3 ^ n + b2 ^ n \ (Như \ x_1 = 3 \ và \ x_2 = 2) $

Vì thế,

$ 1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b $

$ 4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b $

Giải hai phương trình này, ta được $ a = 2 $ và $ b = -1 $

Do đó, giải pháp cuối cùng là -

$$ F_n = 2.3 ^ n + (-1). 2 ^ n = 2.3 ^ n - 2 ^ n $$

Problem 2

Giải quan hệ lặp lại - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ trong đó $ F_0 = 3 $ và $ F_1 = 17 $

Solution

Phương trình đặc trưng của quan hệ tái diễn là -

$$ x ^ 2 - 10x -25 = 0 $$

Vậy $ (x - 5) ^ 2 = 0 $

Do đó, có một gốc thực duy nhất $ x_1 = 5 $

Vì chỉ có một gốc có giá trị thực duy nhất nên nó ở dạng trường hợp 2

Do đó, giải pháp là -

$ 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 $

Giải hai phương trình này, ta được $ a = 3 $ và $ b = 2/5 $

Do đó, nghiệm cuối cùng là - $ F_n = 3.5 ^ n + (2/5) .n.2 ^ n $

Problem 3

Giải quan hệ lặp lại $ F_n = 2F_ {n-1} - 2F_ {n-2} $ trong đó $ F_0 = 1 $ và $ F_1 = 3 $

Solution

Phương trình đặc trưng của quan hệ tái diễn là -

$$ x ^ 2 -2x -2 = 0 $$

Do đó, rễ là -

$ x_1 = 1 + i $ và $ x_2 = 1 - i $

Ở dạng cực,

$ x_1 = r \ angle \ theta $ và $ x_2 = r \ angle (- \ theta), $ trong đó $ r = \ sqrt 2 $ và $ \ theta = \ frac {\ pi} {4} $

Rễ là tưởng tượng. Vì vậy, đây là dạng trường hợp 3.

Do đó, giải pháp là -

$ F_n = (\ sqrt 2) ^ n (a cos (n. \ Sqcap / 4) + b sin (n. \ Sqcap / 4)) $

$ 1 = F_0 = (\ sqrt 2) ^ 0 (a cos (0. \ Sqcap / 4) + b sin (0. \ Sqcap / 4)) = a $

$ 3 = F_1 = (\ sqrt 2) ^ 1 (a cos (1. \ Sqcap / 4) + b sin (1. \ Sqcap / 4)) = \ sqrt 2 (a / \ sqrt 2 + b / \ sqrt 2 ) $

Giải hai phương trình này ta được $ a = 1 $ và $ b = 2 $

Do đó, giải pháp cuối cùng là -

$ F_n = (\ sqrt 2) ^ n (cos (n. \ Pi / 4) + 2 sin (n. \ Pi / 4)) $

Mối quan hệ lặp lại không đồng nhất và các giải pháp cụ thể

Một quan hệ lặp lại được gọi là không thuần nhất nếu nó ở dạng

$ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ trong đó $ f (n) \ ne 0 $

Quan hệ lặp lại đồng nhất được kết hợp của nó là $ F_n = AF_ {n – 1} + BF_ {n-2} $

Giải pháp $ (a_n) $ của một quan hệ lặp lại không thuần nhất có hai phần.

Phần đầu tiên là giải pháp $ (a_h) $ của quan hệ lặp lại đồng nhất được liên kết và phần thứ hai là nghiệm cụ thể $ (a_t) $.

$$ a_n = a_h + a_t $$

Giải pháp cho phần đầu tiên được thực hiện bằng cách sử dụng các thủ tục đã thảo luận trong phần trước.

Để tìm ra giải pháp cụ thể, chúng tôi tìm một giải pháp dùng thử thích hợp.

Cho $ f (n) = cx ^ n $; đặt $ x ^ 2 = Ax + B $ là phương trình đặc trưng của quan hệ lặp lại thuần nhất liên quan và đặt $ x_1 $ và $ x_2 $ là gốc của nó.

Nếu $ x \ ne x_1 $ và $ x \ ne x_2 $ thì $ a_t = Ax ^ n $
Nếu $ x = x_1 $, $ x \ ne x_2 $ thì $ a_t = Anx ^ n $
Nếu $ x = x_1 = x_2 $ thì $ a_t = An ^ 2x ^ n $

Thí dụ

Cho quan hệ lặp lại không thuần nhất là $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ với các gốc đặc trưng $ x_1 = 2 $ và $ x_2 = 5 $. Các giải pháp thử nghiệm cho các giá trị có thể có khác nhau của $ f (n) $ như sau:

f (n)	Giải pháp thử nghiệm
4	A
5,2 ⁿ	An2 ⁿ
8,5 ⁿ	An5 ⁿ
4 ⁿ	A4 ⁿ
2n ² + 3n + 1	An ² + Bn + C

Problem

Giải quan hệ lặp lại $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7,5 ^ n $ trong đó $ F_0 = 4 $ và $ F_1 = 3 $

Solution

Đây là một quan hệ tuyến tính không thuần nhất, trong đó phương trình thuần nhất liên quan là $ F_n = 3F_ {n-1} + 10F_ {n-2} $ và $ f (n) = 7,5 ^ n $

Phương trình đặc trưng của quan hệ thuần nhất liên kết của nó là -

$$ x ^ 2 - 3x -10 = 0 $$

Hoặc, $ (x - 5) (x + 2) = 0 $

Hoặc, $ x_1 = 5 $ và $ x_2 = -2 $

Do đó $ a_h = a.5 ^ n + b. (- 2) ^ n $, trong đó a và b là hằng số.

Vì $ f (n) = 7,5 ^ n $, tức là có dạng $ cx ^ n $, một giải pháp thử hợp lý tùy ý sẽ là $ Anx ^ n $

$ a_t = Anx ^ n = An5 ^ n $

Sau khi đặt giải pháp trong mối quan hệ lặp lại, chúng tôi nhận được -

$ An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7,5 ^ n $

Chia cả hai vế cho $ 5 ^ {n-2} $, ta được

$ An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7,5 ^ 2 $

Hoặc, $ 25An = 15An - 15A + 10An - 20A + 175 $

Hoặc, $ 35A = 175 $

Hoặc, $ A = 5 $

Vì vậy, $ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $

Giải pháp của quan hệ lặp lại có thể được viết dưới dạng:

$ F_n = a_h + a_t $

$ = a.5 ^ n + b. (- 2) ^ n + n5 ^ {n + 1} $

Đặt các giá trị $ F_0 = 4 $ và $ F_1 = 3 $, trong phương trình trên, chúng ta nhận được $ a = -2 $ và $ b = 6 $

Do đó, giải pháp là -

$ F_n = n5 ^ {n + 1} + 6. (- 2) ^ n -2,5 ^ n $

Tạo chức năng

Generating Functions đại diện cho các chuỗi trong đó mỗi số hạng của một chuỗi được biểu thị dưới dạng hệ số của một biến x trong chuỗi lũy thừa chính thức.

Về mặt toán học, đối với một chuỗi vô hạn, giả sử $ a_0, a_1, a_2, \ dot, a_k, \ dot, $ hàm tạo sẽ là -

$$ G_x = a_0 + a_1x + a_2x ^ 2 + \ dot + a_kx ^ k + \ dot = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k $$

Một số lĩnh vực ứng dụng

Các hàm tạo có thể được sử dụng cho các mục đích sau:

Để giải quyết một loạt các bài toán đếm. Ví dụ, số cách thay đổi đối với Rs. 100 tờ tiền với các mệnh giá Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 và Rs.50
Để giải quyết các quan hệ lặp lại
Để chứng minh một số đặc điểm tổ hợp
Để tìm công thức tiệm cận cho các số hạng của chuỗi

Problem 1

Hàm tạo cho chuỗi $ \ lbrace {a_k} \ rbrace $ với $ a_k = 2 $ và $ a_k = 3k $ là gì?

Solution

Khi $ a_k = 2 $, hàm tạo, $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ chấm $

Khi $ a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ chấm \ chấm $

Problem 2

Hàm sinh của chuỗi vô hạn là gì; $ 1, 1, 1, 1, \ chấm $?

Solution

Đây, $ a_k = 1 $, với $ 0 \ le k \ le \ infty $

Do đó, $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dot \ dot = \ frac {1} {(1 - x)} $

Một số chức năng tạo hữu ích

Với $ a_k = a ^ {k}, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ dot \ dot \ dot = 1 / (1 - ax) $
Với $ a_ {k} = (k + 1), G (x) = \ sum_ {k = 0} ^ {\ infty} (k + 1) x ^ {k} = 1 + 2x + 3x ^ {2} \ dot \ dot \ dot = \ frac {1} {(1 - x) ^ {2}} $
Đối với $ 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} + \ dot \ dot \ dot + x ^ {2} = (1 + x) ^ {n} $
Đối với $ 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!} \ dot \ dot \ dot = e ^ {x} $