Ayrık Matematik - Tekrarlama İlişkisi

Bu bölümde, yinelemeli tekniklerin dizileri nasıl türetebileceğini ve sayma problemlerini çözmek için nasıl kullanılabileceğini tartışacağız. Bir dizinin terimlerini yinelemeli bir şekilde bulma prosedürü denirrecurrence relation. Doğrusal tekrarlama ilişkileri teorisini ve çözümlerini inceliyoruz. Son olarak, yineleme ilişkilerini çözmek için işlevler üretiyoruz.

Tanım

Bir yineleme ilişkisi, sonraki terimin önceki terimlerin bir işlevi olduğu bir diziyi yinelemeli olarak tanımlayan bir denklemdir ($ F_n $ 'ı $ F_i $ ile $ i <n $' ın bir kombinasyonu olarak ifade ederek).

Example - Fibonacci serisi - $ F_n = F_ {n-1} + F_ {n-2} $, Hanoi Kulesi - $ F_n = 2F_ {n-1} + 1 $

Doğrusal Tekrarlama İlişkileri

K derece veya k dereceli bir doğrusal tekrarlama denklemi, $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_k x_ biçiminde bir tekrarlama denklemidir {nk} $ ($ A_n $ bir sabittir ve $ A_k \ neq 0 $) birinci derece polinom olarak bir sayı dizisi üzerinde.

Doğrusal tekrarlama denklemlerinin bazı örnekleridir -

Tekrarlama ilişkileri	Başlangıç değerleri	Çözümler
F _n = F _n-1 + F _n-2	bir ₁ = bir ₂ = 1	Fibonacci numarası
F _n = F _n-1 + F _n-2	bir ₁ = 1, bir ₂ = 3	Lucas Numarası
F _n = F _n-2 + F _n-3	bir ₁ = bir ₂ = bir ₃ = 1	Padovan dizisi
F _n = 2F _n-1 + F _n-2	bir ₁ = 0, bir ₂ = 1	Pell numarası

Doğrusal tekrarlama ilişkisi nasıl çözülür?

Diyelim ki, iki sıralı doğrusal tekrarlama ilişkisi - $ F_n = AF_ {n-1} + BF_ {n-2} $, burada A ve B gerçek sayılardır.

Yukarıdaki tekrarlama ilişkisinin karakteristik denklemi -

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

Kökleri bulurken üç durum ortaya çıkabilir -

Case 1- Bu denklem $ (x- x_1) (x- x_1) = 0 $ olarak çarpılırsa ve $ x_1 $ ve $ x_2 $ olmak üzere iki farklı gerçek kök üretirse, çözüm $ F_n = ax_1 ^ n + bx_2 ^ n $ olur. [Burada a ve b sabitlerdir]

Case 2 - Bu denklem $ (x- x_1) ^ 2 = 0 $ olarak çarpılırsa ve tek gerçek kök $ x_1 $ üretirse, çözüm $ F_n = a x_1 ^ n + bn x_1 ^ n $ olur.

Case 3 - Denklem iki farklı karmaşık kök üretirse, $ x_1 $ ve $ x_2 $ kutupsal biçimde $ x_1 = r \ angle \ theta $ ve $ x_2 = r \ angle (- \ theta) $, sonra $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ çözümdür.

Problem 1

$ F_n = 5F_ {n-1} - 6F_ {n-2} $ burada $ F_0 = 1 $ ve $ F_1 = 4 $ olmak üzere yinelenme ilişkisini çözün

Solution

Yineleme ilişkisinin karakteristik denklemi -

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

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

Dolayısıyla kökler -

$ x_1 = 3 $ ve x_2 $ = 2 $

Kökler gerçek ve farklı. Yani, bu durum 1 şeklinde

Dolayısıyla çözüm -

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

Burada, $ F_n = a3 ^ n + b2 ^ n \ (As \ x_1 = 3 \ ve \ x_2 = 2) $

Bu nedenle,

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

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

Bu iki denklemi çözerek $ a = 2 $ ve $ b = -1 $ elde ederiz

Dolayısıyla, nihai çözüm -

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

Problem 2

Yineleme ilişkisini çözün - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ burada $ F_0 = 3 $ ve $ F_1 = 17 $

Solution

Yineleme ilişkisinin karakteristik denklemi -

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

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

Dolayısıyla, tek bir gerçek kök vardır $ x_1 = 5 $

Tek gerçek değerli kök olduğu için, bu durum 2 şeklindedir.

Dolayısıyla çözüm -

$ F_n = ax_1 ^ n + bnx_1 ^ n $

$ 3 = F_0 = a.5 ^ 0 + (b) (0.5) ^ 0 = a $

17 ABD Doları = F_1 = a.5 ^ 1 + b.1.5 ^ 1 = 5a + 5b $

Bu iki denklemi çözerek, $ a = 3 $ ve $ b = 2/5 $ elde ederiz.

Dolayısıyla, nihai çözüm - $ F_n = 3.5 ^ n + (2/5) .n.2 ^ n $

Problem 3

$ F_n = 2F_ {n-1} - 2F_ {n-2} $ burada $ F_0 = 1 $ ve $ F_1 = 3 $ olmak üzere yinelenme ilişkisini çözün

Solution

Yineleme ilişkisinin karakteristik denklemi -

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

Dolayısıyla kökler -

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

Kutupsal formda,

$ x_1 = r \ angle \ theta $ ve $ x_2 = r \ angle (- \ theta), $ burada $ r = \ sqrt 2 $ ve $ \ theta = \ frac {\ pi} {4} $

Kökler hayalidir. Yani, bu durum 3 şeklinde.

Dolayısıyla çözüm -

$ F_n = (\ sqrt 2) ^ n (a cos (n. \ Sqcap / 4) + b sin (n. \ Sqrt / 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 ) $

Bu iki denklemi çözdüğümüzde $ a = 1 $ ve $ b = 2 $ elde ederiz

Dolayısıyla, nihai çözüm -

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

Homojen Olmayan Tekrarlama İlişkisi ve Özel Çözümler

Bir yineleme ilişkisine homojen olmayan denir, eğer formda ise

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

İlişkili homojen yineleme ilişkisi $ F_n = AF_ {n – 1} + BF_ {n-2} $

Homojen olmayan bir tekrarlama ilişkisinin $ (a_n) $ çözümü iki bölümden oluşur.

Birinci kısım, ilişkili homojen tekrarlama ilişkisinin $ (a_h) $ çözümü, ikinci kısım ise $ (a_t) $ özel çözümüdür.

$$ a_n = a_h + a_t $$

İlk bölümün çözümü, önceki bölümde tartışılan prosedürler kullanılarak yapılır.

Belirli çözümü bulmak için uygun bir deneme çözümü buluyoruz.

$ F (n) = cx ^ n $; $ x ^ 2 = Ax + B $ ilişkili homojen yineleme ilişkisinin karakteristik denklemi olsun ve $ x_1 $ ve $ x_2 $ bunun kökleri olsun.

$ X \ ne x_1 $ ve $ x \ ne x_2 $ ise, $ a_t = Ax ^ n $
$ X = x_1 $, $ x \ ne x_2 $ ise, $ a_t = Anx ^ n $
$ X = x_1 = x_2 $ ise, $ a_t = An ^ 2x ^ n $

Misal

Homojen olmayan bir tekrarlama ilişkisinin, karakteristik kökleri $ x_1 = 2 $ ve $ x_2 = 5 $ olan $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ olsun. Farklı olası $ f (n) $ değerleri için deneme çözümleri aşağıdaki gibidir -

f (n)	Deneme çözümleri
4	Bir
5,2 ⁿ	An2 ⁿ
8.5 ⁿ	An5 ⁿ
4 ⁿ	A4 ⁿ
2n ² + 3n + 1	Bir ² + Bn + C

Problem

$ F_n = 3F_ {n-1} + 10F_ {n-2} + 7.5 ^ n $ burada $ F_0 = 4 $ ve $ F_1 = 3 $ olmak üzere yinelenme ilişkisini çözün

Solution

Bu, ilişkili homojen denklemin $ F_n = 3F_ {n-1} + 10F_ {n-2} $ ve $ f (n) = 7.5 ^ n $ olduğu doğrusal homojen olmayan bir ilişkidir.

İlişkili homojen ilişkisinin karakteristik denklemi -

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

Veya $ (x - 5) (x + 2) = 0 $

Veya x_1 = 5 $ ve x_2 = -2 $

Dolayısıyla, $ a_h = a.5 ^ n + b. (- 2) ^ n $, burada a ve b sabittir.

$ F (n) = 7.5 ^ n $ olduğundan, yani $ cx ^ n $ biçiminde, makul bir deneme çözümü $ Anx ^ n $ olacaktır

$ a_t = Ek ^ n = An5 ^ n $

Çözümü tekrarlama ilişkisine koyduktan sonra, şunu elde ederiz -

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

Her iki tarafı da $ 5 ^ {n-2} $ 'a bölersek

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

Veya 25 An = 15 An - 15A + 10 An - 20A + 175 $

Veya 35A $ = 175 $

Veya A $ = 5 $

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

Yineleme ilişkisinin çözümü şu şekilde yazılabilir:

$ F_n = a_h + a_t $

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

$ F_0 = 4 $ ve $ F_1 = 3 $ değerlerini koyarsak, yukarıdaki denklemde $ a = -2 $ ve $ b = 6 $ elde ederiz

Dolayısıyla çözüm -

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

İşlevler Oluşturma

Generating Functions Bir dizideki her terimin, biçimsel bir güç serisindeki bir değişken x'in katsayısı olarak ifade edildiği dizileri temsil eder.

Matematiksel olarak, sonsuz bir dizi için, $ a_0, a_1, a_2, \ dots, a_k, \ dots, $ diyelim, oluşturma işlevi -

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

Bazı Uygulama Alanları

Oluşturma işlevleri aşağıdaki amaçlar için kullanılabilir -

Çeşitli sayma problemlerini çözmek için. Örneğin, bir Rs için değişiklik yapmanın yollarının sayısı. Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 ve Rs.50 mezhep notları ile 100 not
Tekrarlama ilişkilerini çözmek için
Bazı kombinatoryal kimlikleri kanıtlamak için
Diziler için asimptotik formüller bulmak için

Problem 1

$ A_k = 2 $ ve $ a_k = 3k $ ile $ \ lbrace {a_k} \ rbrace $ dizileri için üretme fonksiyonları nelerdir?

Solution

$ A_k = 2 $ olduğunda, oluşturma işlevi, $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ dots $

$ A_ {k} = 3k olduğunda, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ dots \ dots $

Problem 2

Sonsuz serinin üretme işlevi nedir; $ 1, 1, 1, 1, \ dots $?

Solution

Burada, $ a_k = 1 $, $ 0 \ le k \ le \ infty $ için

Dolayısıyla, $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $

Bazı Yararlı Oluşturma İşlevleri

$ A_k = a ^ {k} için, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ dots \ dots \ dots = 1 / (1 - ax) $
$ A_ {k} = (k + 1), G (x) = \ sum_ {k = 0} ^ {\ infty} (k + 1) x ^ {k} = 1 + 2x + 3x ^ {2} için \ noktalar \ noktalar \ noktalar = \ frac {1} {(1 - x) ^ {2}} $
$ A_ {k} = c_ {k} ^ {n}, G (x) = \ sum_ {k = 0} ^ {\ infty} c_ {k} ^ {n} x ^ {k} = 1 + c_ için {1} ^ {n} x + c_ {2} ^ {n} x ^ {2} + \ dots \ dots \ dots + x ^ {2} = (1 + x) ^ {n} $
$ A_ {k} = \ frac {1} {k!} İçin, 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} $