Matematica discreta - Relazione di ricorrenza
In questo capitolo discuteremo di come le tecniche ricorsive possono derivare sequenze ed essere usate per risolvere problemi di conteggio. Viene chiamata la procedura per trovare i termini di una sequenza in modo ricorsivorecurrence relation. Studiamo la teoria delle relazioni di ricorrenza lineare e le loro soluzioni. Infine, introduciamo le funzioni di generazione per risolvere le relazioni di ricorrenza.
Definizione
Una relazione di ricorrenza è un'equazione che definisce ricorsivamente una sequenza in cui il termine successivo è una funzione dei termini precedenti (Esprimendo $ F_n $ come una combinazione di $ F_i $ con $ i <n $).
Example - Serie di Fibonacci - $ F_n = F_ {n-1} + F_ {n-2} $, Torre di Hanoi - $ F_n = 2F_ {n-1} + 1 $
Relazioni di ricorrenza lineare
Un'equazione di ricorrenza lineare di grado ko ordine k è un'equazione di ricorrenza nel formato $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_k x_ {nk} $ ($ A_n $ è una costante e $ A_k \ neq 0 $) su una sequenza di numeri come polinomio di primo grado.
Questi sono alcuni esempi di equazioni di ricorrenza lineare:
| Relazioni ricorrenti | Valori iniziali | Soluzioni |
|---|---|---|
| F n = F n-1 + F n-2 | a 1 = a 2 = 1 | Numero di Fibonacci |
| F n = F n-1 + F n-2 | a 1 = 1, a 2 = 3 | Lucas Number |
| F n = F n-2 + F n-3 | a 1 = a 2 = a 3 = 1 | Sequenza padovana |
| F n = 2F n-1 + F n-2 | a 1 = 0, a 2 = 1 | Numero di Pell |
Come risolvere la relazione di ricorrenza lineare
Supponiamo che una relazione di ricorrenza lineare ordinata sia - $ F_n = AF_ {n-1} + BF_ {n-2} $ dove A e B sono numeri reali.
L'equazione caratteristica per la relazione di ricorrenza di cui sopra è:
$$ x ^ 2 - Ascia - B = 0 $$
Possono verificarsi tre casi mentre si trovano le radici:
Case 1- Se questa equazione fattorizza come $ (x- x_1) (x- x_1) = 0 $ e produce due radici reali distinte $ x_1 $ e $ x_2 $, allora $ F_n = ax_1 ^ n + bx_2 ^ n $ è la soluzione. [Qui, aeb sono costanti]
Case 2 - Se questa equazione fattorizza come $ (x- x_1) ^ 2 = 0 $ e produce una singola radice reale $ x_1 $, allora $ F_n = a x_1 ^ n + bn x_1 ^ n $ è la soluzione.
Case 3 - Se l'equazione produce due radici complesse distinte, $ x_1 $ e $ x_2 $ in forma polare $ x_1 = r \ angle \ theta $ e $ x_2 = r \ angle (- \ theta) $, allora $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ è la soluzione.
Problem 1
Risolvi la relazione di ricorrenza $ F_n = 5F_ {n-1} - 6F_ {n-2} $ dove $ F_0 = 1 $ e $ F_1 = 4 $
Solution
L'equazione caratteristica della relazione di ricorrenza è:
$$ x ^ 2 - 5x + 6 = 0, $$
Quindi, $ (x - 3) (x - 2) = 0 $
Quindi, le radici sono -
$ x_1 = 3 $ e $ x_2 = 2 $
Le radici sono reali e distinte. Quindi, questo è nella forma del caso 1
Quindi, la soluzione è:
$$ F_n = ax_1 ^ n + bx_2 ^ n $$
Qui, $ F_n = a3 ^ n + b2 ^ n \ (As \ x_1 = 3 \ e \ x_2 = 2) $
Perciò,
$ 1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b $
$ 4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b $
Risolvendo queste due equazioni, otteniamo $ a = 2 $ e $ b = -1 $
Quindi, la soluzione finale è:
$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n - 2 ^ n $$
Problem 2
Risolvi la relazione di ricorrenza - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ dove $ F_0 = 3 $ e $ F_1 = 17 $
Solution
L'equazione caratteristica della relazione di ricorrenza è:
$$ x ^ 2 - 10x -25 = 0 $$
Quindi $ (x - 5) ^ 2 = 0 $
Quindi, esiste una singola radice reale $ x_1 = 5 $
Poiché esiste un'unica radice con valore reale, questa è nella forma del caso 2
Quindi, la soluzione è:
$ 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 $
Risolvendo queste due equazioni, otteniamo $ a = 3 $ e $ b = 2/5 $
Quindi, la soluzione finale è - $ F_n = 3.5 ^ n + (2/5) .n.2 ^ n $
Problem 3
Risolvi la relazione di ricorrenza $ F_n = 2F_ {n-1} - 2F_ {n-2} $ dove $ F_0 = 1 $ e $ F_1 = 3 $
Solution
L'equazione caratteristica della relazione di ricorrenza è:
$$ x ^ 2 -2x -2 = 0 $$
Quindi, le radici sono -
$ x_1 = 1 + i $ e $ x_2 = 1 - i $
In forma polare,
$ x_1 = r \ angle \ theta $ e $ x_2 = r \ angle (- \ theta), $ dove $ r = \ sqrt 2 $ e $ \ theta = \ frac {\ pi} {4} $
Le radici sono immaginarie. Quindi, questo è nella forma del caso 3.
Quindi, la soluzione è:
$ 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 ) $
Risolvendo queste due equazioni otteniamo $ a = 1 $ e $ b = 2 $
Quindi, la soluzione finale è:
$ F_n = (\ sqrt 2) ^ n (cos (n. \ Pi / 4) + 2 sin (n. \ Pi / 4)) $
Relazione di ricorrenza non omogenea e soluzioni particolari
Una relazione di ricorrenza è chiamata non omogenea se è nella forma
$ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ dove $ f (n) \ ne 0 $
La relazione di ricorrenza omogenea associata è $ F_n = AF_ {n – 1} + BF_ {n-2} $
La soluzione $ (a_n) $ di una relazione di ricorrenza non omogenea ha due parti.
La prima parte è la soluzione $ (a_h) $ della relazione di ricorrenza omogenea associata e la seconda parte è la particolare soluzione $ (a_t) $.
$$ a_n = a_h + a_t $$
La soluzione alla prima parte viene eseguita utilizzando le procedure discusse nella sezione precedente.
Per trovare la soluzione particolare, troviamo una soluzione di prova appropriata.
Sia $ f (n) = cx ^ n $; siano $ x ^ 2 = Ax + B $ l'equazione caratteristica della relazione di ricorrenza omogenea associata e siano $ x_1 $ e $ x_2 $ le sue radici.
Se $ x \ ne x_1 $ e $ x \ ne x_2 $, allora $ a_t = Ax ^ n $
Se $ x = x_1 $, $ x \ ne x_2 $, allora $ a_t = Anx ^ n $
Se $ x = x_1 = x_2 $, allora $ a_t = An ^ 2x ^ n $
Esempio
Sia una relazione di ricorrenza non omogenea $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ con radici caratteristiche $ x_1 = 2 $ e $ x_2 = 5 $. Le soluzioni di prova per diversi valori possibili di $ f (n) $ sono le seguenti:
| f (n) | Soluzioni di prova |
|---|---|
| 4 | UN |
| 5.2 n | An2 n |
| 8.5 n | An5 n |
| 4 n | A4 n |
| 2n 2 + 3n + 1 | Un 2 + Bn + C |
Problem
Risolvi la relazione di ricorrenza $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7.5 ^ n $ dove $ F_0 = 4 $ e $ F_1 = 3 $
Solution
Questa è una relazione lineare non omogenea, dove l'equazione omogenea associata è $ F_n = 3F_ {n-1} + 10F_ {n-2} $ e $ f (n) = 7.5 ^ n $
L'equazione caratteristica della sua relazione omogenea associata è:
$$ x ^ 2 - 3x -10 = 0 $$
Oppure $ (x - 5) (x + 2) = 0 $
Oppure $ x_1 = 5 $ e $ x_2 = -2 $
Quindi $ a_h = a.5 ^ n + b. (- 2) ^ n $, dove aeb sono costanti.
Poiché $ f (n) = 7.5 ^ n $, cioè della forma $ cx ^ n $, una ragionevole soluzione di prova di at sarà $ Anx ^ n $
$ a_t = Anx ^ n = An5 ^ n $
Dopo aver inserito la soluzione nella relazione di ricorrenza, otteniamo:
$ An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7,5 ^ n $
Dividendo entrambi i lati per $ 5 ^ {n-2} $, otteniamo
$ An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7,5 ^ 2 $
Oppure, $ 25An = 15An - 15A + 10An - 20A + 175 $
Oppure $ 35A = 175 $
Oppure $ A = 5 $
Quindi, $ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $
La soluzione della relazione di ricorrenza può essere scritta come:
$ F_n = a_h + a_t $
$ = a.5 ^ n + b. (- 2) ^ n + n5 ^ {n + 1} $
Mettendo i valori di $ F_0 = 4 $ e $ F_1 = 3 $, nell'equazione sopra, otteniamo $ a = -2 $ e $ b = 6 $
Quindi, la soluzione è:
$ F_n = n5 ^ {n + 1} + 6. (- 2) ^ n -2,5 ^ n $
Generazione di funzioni
Generating Functions rappresenta sequenze in cui ogni termine di una sequenza è espresso come coefficiente di una variabile x in una serie di potenze formali.
Matematicamente, per una sequenza infinita, diciamo $ a_0, a_1, a_2, \ dots, a_k, \ dots, $ la funzione generatrice sarà -
$$ G_x = a_0 + a_1x + a_2x ^ 2 + \ dots + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k $$
Alcune aree di applicazione
Le funzioni di generazione possono essere utilizzate per i seguenti scopi:
Per risolvere una varietà di problemi di conteggio. Ad esempio, il numero di modi per apportare modifiche a Rs. Banconota da 100 con le denominazioni Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 e Rs.50
Per risolvere le relazioni di ricorrenza
Per provare alcune delle identità combinatorie
Per trovare formule asintotiche per termini di sequenze
Problem 1
Quali sono le funzioni di generazione delle sequenze $ \ lbrace {a_k} \ rbrace $ con $ a_k = 2 $ e $ a_k = 3k $?
Solution
Quando $ a_k = 2 $, funzione di generazione, $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ dots $
Quando $ a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ dots \ dots $
Problem 2
Qual è la funzione generatrice della serie infinita; $ 1, 1, 1, 1, \ punti $?
Solution
Qui $ a_k = 1 $, per $ 0 \ le k \ le \ infty $
Quindi, $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $
Alcune utili funzioni di generazione
Per $ a_k = a ^ {k}, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ punti \ punti \ punti = 1 / (1 - ascia) $
Per $ 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}} $
Per $ 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} $
Per $ 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} $