Matematyka dyskretna - relacja nawrotów

W tym rozdziale omówimy, w jaki sposób techniki rekurencyjne mogą wyprowadzać sekwencje i być używane do rozwiązywania problemów z liczeniem. Wywoływana jest procedura wyszukiwania terminów sekwencji w sposób rekurencyjnyrecurrence relation. Badamy teorię liniowych relacji rekurencyjnych i ich rozwiązania. Na koniec wprowadzamy funkcje generujące do rozwiązywania relacji rekurencyjnych.

Definicja

Relacja rekurencji to równanie, które rekurencyjnie definiuje sekwencję, w której następny człon jest funkcją poprzednich wyrazów (Wyrażając $ F_n $ jako pewną kombinację $ F_i $ z $ i <n $).

Example - Szereg Fibonacciego - $ F_n = F_ {n-1} + F_ {n-2} $, Wieża Hanoi - $ F_n = 2F_ {n-1} + 1 $

Relacje liniowej powtarzalności

Liniowe równanie rekurencji stopnia k lub rzędu k to równanie rekurencji w formacie $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_k x_ {nk} $ ($ A_n $ jest stałą, a $ A_k \ neq 0 $) na sekwencji liczb jako wielomian pierwszego stopnia.

Oto kilka przykładów równań rekurencji liniowej -

Relacje cykliczne	Wartości początkowe	Rozwiązania
F _n = F _n-1 + F _n-2	a ₁ = a ₂ = 1	Liczba Fibonacciego
F _n = F _n-1 + F _n-2	a ₁ = 1, a ₂ = 3	Lucas Number
F _n = F _n-2 + F _n-3	a ₁ = a ₂ = a ₃ = 1	Sekwencja Padovana
F _n = 2F _n-1 + F _n-2	a ₁ = 0, a ₂ = 1	Numer pelletu

Jak rozwiązać relację liniowej powtarzalności

Załóżmy, że relacja dwóch uporządkowanych liniowych powtórzeń to - $ F_n = AF_ {n-1} + BF_ {n-2} $, gdzie A i B to liczby rzeczywiste.

Charakterystyczne równanie dla powyższej relacji nawrotu to -

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

Podczas wyszukiwania korzeni mogą wystąpić trzy przypadki -

Case 1- Jeśli to równanie bierze pod uwagę $ (x- x_1) (x- x_1) = 0 $ i daje dwa różne pierwiastki rzeczywiste $ x_1 $ i $ x_2 $, to rozwiązaniem jest $ F_n = ax_1 ^ n + bx_2 ^ n $. [Tutaj a i b są stałymi]

Case 2 - Jeśli to równanie uwzględnia jako $ (x- x_1) ^ 2 = 0 $ i daje pojedynczy pierwiastek rzeczywisty $ x_1 $, to rozwiązaniem jest $ F_n = a x_1 ^ n + bn x_1 ^ n $.

Case 3 - Jeśli równanie daje dwa różne pierwiastki zespolone, $ x_1 $ i $ x_2 $ w postaci biegunowej $ x_1 = r \ angle \ theta $ i $ x_2 = r \ angle (- \ theta) $, to $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ jest rozwiązaniem.

Problem 1

Rozwiąż relację powtarzania $ F_n = 5F_ {n-1} - 6F_ {n-2} $ gdzie $ F_0 = 1 $ i $ F_1 = 4 $

Solution

Charakterystyczne równanie relacji rekurencji to -

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

Tak więc $ (x - 3) (x - 2) = 0 $

Dlatego korzenie są -

x_1 $ = 3 $ i $ x_2 = 2 $

Korzenie są prawdziwe i wyraźne. Jest to więc przypadek 1

Stąd rozwiązaniem jest -

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

Tutaj $ F_n = a3 ^ n + b2 ^ n \ (As \ x_1 = 3 \ and \ x_2 = 2) $

W związku z tym,

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

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

Rozwiązując te dwa równania, otrzymujemy $ a = 2 $ i $ b = -1 $

Stąd ostatecznym rozwiązaniem jest -

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

Problem 2

Rozwiąż relację powtarzania - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ gdzie $ F_0 = 3 $ i $ F_1 = 17 $

Solution

Charakterystyczne równanie relacji rekurencji to -

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

Więc $ (x - 5) ^ 2 = 0 $

W związku z tym istnieje pojedynczy prawdziwy root $ x_1 = 5 $

Ponieważ istnieje pojedynczy pierwiastek o wartości rzeczywistej, ma to postać przypadku 2

Stąd rozwiązaniem jest -

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

Rozwiązując te dwa równania, otrzymujemy $ a = 3 $ i $ b = 2/5 $

Stąd ostateczne rozwiązanie to - $ F_n = 3,5 ^ n + (2/5). N.2 ^ n $

Problem 3

Rozwiąż relację powtarzania $ F_n = 2F_ {n-1} - 2F_ {n-2} $ gdzie $ F_0 = 1 $ i $ F_1 = 3 $

Solution

Charakterystyczne równanie relacji rekurencji to -

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

Dlatego korzenie są -

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

W postaci polarnej,

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

Korzenie są wyimaginowane. Jest to więc przypadek 3.

Stąd rozwiązaniem jest -

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

Rozwiązując te dwa równania otrzymujemy $ a = 1 $ i $ b = 2 $

Stąd ostatecznym rozwiązaniem jest -

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

Relacja niejednorodnych nawrotów i poszczególne rozwiązania

Relacja rekurencji nazywana jest niejednorodną, jeśli ma postać

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

Skojarzona z nim jednorodna relacja powtarzalności to $ F_n = AF_ {n – 1} + BF_ {n-2} $

Rozwiązanie $ (a_n) $ niejednorodnej relacji powtarzania ma dwie części.

Pierwsza część to rozwiązanie $ (a_h) $ powiązanej jednorodnej relacji powtarzania, a druga część to rozwiązanie szczegółowe $ (a_t) $.

$$ a_n = a_h + a_t $$

Rozwiązanie pierwszej części odbywa się za pomocą procedur omówionych w poprzedniej sekcji.

Aby znaleźć konkretne rozwiązanie, znajdujemy odpowiednie rozwiązanie próbne.

Niech $ f (n) = cx ^ n $; niech $ x ^ 2 = Ax + B $ będzie charakterystycznym równaniem powiązanej jednorodnej relacji powtarzania i niech $ x_1 $ i $ x_2 $ będą jego pierwiastkami.

Jeśli $ x \ ne x_1 $ i $ x \ ne x_2 $, to $ a_t = Ax ^ n $
Jeśli $ x = x_1 $, $ x \ ne x_2 $, to $ a_t = Anx ^ n $
Jeśli $ x = x_1 = x_2 $, to $ a_t = An ^ 2x ^ n $

Przykład

Niech niejednorodna relacja powtarzania będzie wynosić $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ z charakterystycznymi pierwiastkami $ x_1 = 2 $ i $ x_2 = 5 $. Rozwiązania próbne dla różnych możliwych wartości $ f (n) $ są następujące -

f (n)	Rozwiązania próbne
4	ZA
5,2 ⁿ	AN2 ⁿ
8,5 ⁿ	AN5 ⁿ
4 ⁿ	A4 ⁿ
2n ² + 3n + 1	An ² + Bn + C

Problem

Rozwiąż relację powtarzania $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7,5 ^ n $ gdzie $ F_0 = 4 $ i $ F_1 = 3 $

Solution

Jest to liniowa niejednorodna relacja, w której powiązane równanie jednorodne to $ F_n = 3F_ {n-1} + 10F_ {n-2} $ i $ f (n) = 7,5 ^ n $

Charakterystyczne równanie powiązanej z nim jednorodnej relacji to -

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

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

Lub $ x_1 = 5 $ i $ x_2 = -2 $

Stąd $ a_h = a.5 ^ n + b. (- 2) ^ n $, gdzie a i b są stałymi.

Ponieważ $ f (n) = 7,5 ^ n $, tj. Postaci $ cx ^ n $, rozsądnym rozwiązaniem próbnym o wartości at będzie $ Anx ^ n $

$ a_t = Anx ^ n = An5 ^ n $

Po umieszczeniu rozwiązania w relacji rekurencji otrzymujemy -

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

Dzieląc obie strony przez 5 ^ {n-2} $, otrzymamy

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

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

Lub 35 $ = 175 $

Lub $ A = 5 $

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

Rozwiązanie relacji powtarzania można zapisać jako -

$ F_n = a_h + a_t $

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

Podając wartości $ F_0 = 4 $ i $ F_1 = 3 $, w powyższym równaniu otrzymujemy $ a = -2 $ i $ b = 6 $

Stąd rozwiązaniem jest -

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

Funkcje generujące

Generating Functions reprezentuje sekwencje, w których każdy wyraz sekwencji jest wyrażony jako współczynnik zmiennej x w formalnym szeregu potęg.

Matematycznie, dla nieskończonej sekwencji, powiedzmy $ a_0, a_1, a_2, \ dots, a_k, \ dots, $ funkcja generująca będzie -

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

Niektóre obszary zastosowań

Funkcje generujące można wykorzystać do następujących celów -

Do rozwiązywania różnych problemów z liczeniem. Na przykład liczba sposobów wprowadzenia zmiany dla Rs. Uwaga 100 z nutami o nominałach Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 i Rs.50
Do rozwiązywania relacji rekurencyjnych
Do udowodnienia niektórych kombinatorycznych tożsamości
Do znajdowania asymptotycznych formuł terminów sekwencji

Problem 1

Jakie są funkcje generujące dla sekwencji $ \ lbrace {a_k} \ rbrace $ z $ a_k = 2 $ i $ a_k = 3k $?

Solution

Gdy $ a_k = 2 $, funkcja generująca, $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ dots $

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

Problem 2

Jaka jest funkcja tworząca nieskończonego szeregu; $ 1, 1, 1, 1, \ kropki $?

Solution

Tutaj $ a_k = 1 $, dla $ 0 \ le k \ le \ infty $

Stąd $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $

Niektóre przydatne funkcje generujące

Dla $ 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 - topór) $
Dla $ 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}} $
Dla $ 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} $
Dla $ 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} $