Matematika Diskrit - Relasi Perulangan

Dalam bab ini, kita akan membahas bagaimana teknik rekursif dapat memperoleh urutan dan digunakan untuk menyelesaikan masalah penghitungan. Prosedur untuk menemukan suku-suku urutan secara rekursif disebutrecurrence relation. Kami mempelajari teori hubungan kekambuhan linier dan solusinya. Akhirnya, kami memperkenalkan fungsi pembangkit untuk menyelesaikan hubungan pengulangan.

Definisi

Relasi perulangan adalah persamaan yang secara rekursif mendefinisikan urutan di mana suku berikutnya adalah fungsi dari suku-suku sebelumnya (Mengekspresikan $ F_n $ sebagai kombinasi $ F_i $ dengan $ i <n $).

Example - Deret Fibonacci - $ F_n = F_ {n-1} + F_ {n-2} $, Menara Hanoi - $ F_n = 2F_ {n-1} + 1 $

Hubungan Perulangan Linier

Persamaan pengulangan linier derajat k atau orde k adalah persamaan pengulangan yang berformat $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ titik A_k x_ {nk} $ ($ A_n $ adalah konstanta dan $ A_k \ neq 0 $) pada urutan angka sebagai polinomial tingkat pertama.

Ini adalah beberapa contoh persamaan pengulangan linier -

Relasi perulangan	Nilai awal	Solusi
F _n = F _n-1 + F _n-2	a ₁ = a ₂ = 1	Angka Fibonacci
F _n = F _n-1 + F _n-2	a ₁ = 1, a ₂ = 3	Nomor Lucas
F _n = F _n-2 + F _n-3	a ₁ = a ₂ = a ₃ = 1	Urutan Padovan
F _n = 2F _n-1 + F _n-2	a ₁ = 0, a ₂ = 1	Nomor pell

Bagaimana mengatasi hubungan kekambuhan linier

Misalkan, dua relasi pengulangan linier yang berurutan adalah - $ F_n = AF_ {n-1} + BF_ {n-2} $ di mana A dan B adalah bilangan real.

Persamaan karakteristik untuk relasi perulangan di atas adalah -

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

Tiga kasus dapat terjadi saat menemukan akar -

Case 1- Jika persamaan ini difaktorkan sebagai $ (x- x_1) (x- x_1) = 0 $ dan menghasilkan dua akar nyata berbeda $ x_1 $ dan $ x_2 $, maka $ F_n = ax_1 ^ n + bx_2 ^ n $ adalah solusinya. [Di sini, a dan b adalah konstanta]

Case 2 - Jika persamaan ini difaktorkan sebagai $ (x- x_1) ^ 2 = 0 $ dan menghasilkan akar nyata tunggal $ x_1 $, maka $ F_n = a x_1 ^ n + bn x_1 ^ n $ adalah solusinya.

Case 3 - Jika persamaan menghasilkan dua akar kompleks yang berbeda, $ x_1 $ dan $ x_2 $ dalam bentuk kutub $ x_1 = r \ angle \ theta $ dan $ x_2 = r \ angle (- \ theta) $, maka $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ adalah solusinya.

Problem 1

Selesaikan relasi pengulangan $ F_n = 5F_ {n-1} - 6F_ {n-2} $ di mana $ F_0 = 1 $ dan $ F_1 = 4 $

Solution

Persamaan karakteristik dari relasi perulangan adalah -

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

Jadi, $ (x - 3) (x - 2) = 0 $

Oleh karena itu, akarnya adalah -

$ x_1 = 3 $ dan $ x_2 = 2 $

Akarnya nyata dan berbeda. Jadi, ini dalam bentuk kasus 1

Oleh karena itu, solusinya adalah -

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

Di sini, $ F_n = a3 ^ n + b2 ^ n \ (As \ x_1 = 3 \ dan \ x_2 = 2) $

Karena itu,

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

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

Memecahkan dua persamaan ini, kita mendapatkan $ a = 2 $ dan $ b = -1 $

Oleh karena itu, solusi akhirnya adalah -

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

Problem 2

Selesaikan relasi pengulangan - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ di mana $ F_0 = 3 $ dan $ F_1 = 17 $

Solution

Persamaan karakteristik dari relasi perulangan adalah -

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

Jadi $ (x - 5) ^ 2 = 0 $

Oleh karena itu, hanya ada satu akar nyata $ x_1 = 5 $

Karena ada satu akar bernilai riil, ini dalam bentuk kasus 2

Oleh karena itu, solusinya adalah -

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

Memecahkan dua persamaan ini, kita mendapatkan $ a = 3 $ dan $ b = 2/5 $

Oleh karena itu, solusi akhirnya adalah - $ F_n = 3,5 ^ n + (2/5). N.2 ^ n $

Problem 3

Selesaikan relasi pengulangan $ F_n = 2F_ {n-1} - 2F_ {n-2} $ di mana $ F_0 = 1 $ dan $ F_1 = 3 $

Solution

Persamaan karakteristik dari relasi perulangan adalah -

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

Oleh karena itu, akarnya adalah -

$ x_1 = 1 + i $ dan $ x_2 = 1 - i $

Dalam bentuk kutub,

$ x_1 = r \ angle \ theta $ dan $ x_2 = r \ angle (- \ theta), $ di mana $ r = \ sqrt 2 $ dan $ \ theta = \ frac {\ pi} {4} $

Akarnya adalah khayalan. Jadi, ini dalam bentuk kasus 3.

Oleh karena itu, solusinya adalah -

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

Memecahkan dua persamaan ini kita mendapatkan $ a = 1 $ dan $ b = 2 $

Oleh karena itu, solusi akhirnya adalah -

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

Relasi Pengulangan Non-Homogen dan Solusi Khusus

Relasi pengulangan disebut non-homogen jika sudah berbentuk

$ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ di mana $ f (n) \ ne 0 $

Hubungan pengulangan homogen terkait adalah $ F_n = AF_ {n – 1} + BF_ {n-2} $

Solusi $ (a_n) $ dari relasi pengulangan yang tidak homogen memiliki dua bagian.

Bagian pertama adalah solusi $ (a_h) $ dari relasi pengulangan homogen terkait dan bagian kedua adalah solusi khusus $ (a_t) $.

$$ a_n = a_h + a_t $$

Solusi untuk bagian pertama dilakukan dengan menggunakan prosedur yang dibahas di bagian sebelumnya.

Untuk menemukan solusi tertentu, kami menemukan solusi uji coba yang sesuai.

Misal $ f (n) = cx ^ n $; misalkan $ x ^ 2 = Ax + B $ menjadi persamaan karakteristik dari relasi pengulangan homogen yang terkait dan misalkan $ x_1 $ dan $ x_2 $ menjadi akarnya.

Jika $ x \ ne x_1 $ dan $ x \ ne x_2 $, maka $ a_t = Ax ^ n $
Jika $ x = x_1 $, $ x \ ne x_2 $, maka $ a_t = Anx ^ n $
Jika $ x = x_1 = x_2 $, maka $ a_t = An ^ 2x ^ n $

Contoh

Misalkan relasi perulangan non-homogen menjadi $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ dengan akar karakteristik $ x_1 = 2 $ dan $ x_2 = 5 $. Solusi percobaan untuk berbagai kemungkinan nilai $ f (n) $ adalah sebagai berikut -

f (n)	Solusi uji coba
4	SEBUAH
5,2 ⁿ	An2 ⁿ
8,5 ⁿ	An5 ⁿ
4 ⁿ	A4 ⁿ
2n ² + 3n + 1	Sebuah ² + Bn + C

Problem

Selesaikan relasi pengulangan $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7,5 ^ n $ di mana $ F_0 = 4 $ dan $ F_1 = 3 $

Solution

Ini adalah relasi non-homogen linier, dengan persamaan homogen terkait adalah $ F_n = 3F_ {n-1} + 10F_ {n-2} $ dan $ f (n) = 7,5 ^ n $

Persamaan karakteristik dari hubungan homogen yang terkait adalah -

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

Atau, $ (x - 5) (x + 2) = 0 $

Atau, $ x_1 = 5 $ dan $ x_2 = -2 $

Karenanya $ a_h = a.5 ^ n + b. (- 2) ^ n $, di mana a dan b adalah konstanta.

Karena $ f (n) = 7,5 ^ n $, yaitu dari bentuk $ cx ^ n $, solusi percobaan yang masuk akal dari at adalah $ Anx ^ n $

$ a_t = Anx ^ n = An5 ^ n $

Setelah meletakkan solusi dalam relasi perulangan, kita dapatkan -

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

Membagi kedua sisi dengan $ 5 ^ {n-2} $, kita dapatkan

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

Atau, $ 25An = 15An - 15A + 10An - 20A + 175 $

Atau, $ 35A = 175 $

Atau, $ A = 5 $

Jadi, $ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $

Solusi dari relasi perulangan dapat ditulis sebagai -

$ F_n = a_h + a_t $

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

Menempatkan nilai $ F_0 = 4 $ dan $ F_1 = 3 $, dalam persamaan di atas, kita mendapatkan $ a = -2 $ dan $ b = 6 $

Oleh karena itu, solusinya adalah -

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

Menghasilkan Fungsi

Generating Functions mewakili urutan di mana setiap suku urutan dinyatakan sebagai koefisien variabel x dalam deret pangkat formal.

Secara matematis, untuk urutan tak terbatas, katakan $ a_0, a_1, a_2, \ dots, a_k, \ dots, $ fungsi pembangkit akan -

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

Beberapa Area Aplikasi

Fungsi pembangkit dapat digunakan untuk tujuan berikut -

Untuk memecahkan berbagai masalah penghitungan. Misalnya, banyaknya cara untuk membuat perubahan untuk Rs. 100 uang kertas dengan uang pecahan Rs.1, Rs.2, Rs.5, Rs.10, Rs. 20 dan Rs.50
Untuk memecahkan hubungan kekambuhan
Untuk membuktikan beberapa identitas kombinatorial
Untuk menemukan rumus asimtotik untuk istilah urutan

Problem 1

Apa fungsi yang menghasilkan urutan $ \ lbrace {a_k} \ rbrace $ dengan $ a_k = 2 $ dan $ a_k = 3k $?

Solution

Ketika $ a_k = 2 $, menghasilkan fungsi, $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ dots $

Saat $ a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ dots \ dots $

Problem 2

Apa fungsi pembangkitan deret tak hingga; $ 1, 1, 1, 1, \ dots $?

Solution

Di sini, $ a_k = 1 $, untuk $ 0 \ le k \ le \ infty $

Karenanya, $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $

Beberapa Fungsi Pembangkit Berguna

Untuk $ 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 - ax) $
Untuk $ 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}} $
Untuk $ 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} $
Untuk $ 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} $