Mathématiques discrètes - Relation de récurrence
Dans ce chapitre, nous discuterons de la manière dont les techniques récursives peuvent dériver des séquences et être utilisées pour résoudre des problèmes de comptage. La procédure pour trouver les termes d'une séquence de manière récursive est appeléerecurrence relation. Nous étudions la théorie des relations de récurrence linéaire et leurs solutions. Enfin, nous introduisons des fonctions de génération pour résoudre les relations de récurrence.
Définition
Une relation de récurrence est une équation qui définit de façon récursive une séquence où le terme suivant est une fonction des termes précédents (exprimant $ F_n $ comme une combinaison de $ F_i $ avec $ i <n $).
Example - Série Fibonacci - $ F_n = F_ {n-1} + F_ {n-2} $, Tour de Hanoï - $ F_n = 2F_ {n-1} + 1 $
Relations de récurrence linéaire
Une équation de récurrence linéaire de degré k ou d'ordre k est une équation de récurrence au format $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ points A_k x_ {nk} $ ($ A_n $ est une constante et $ A_k \ neq 0 $) sur une suite de nombres comme polynôme du premier degré.
Voici quelques exemples d'équations de récurrence linéaire -
| Relations de récurrence | Valeurs initiales | Solutions |
|---|---|---|
| F n = F n-1 + F n-2 | a 1 = a 2 = 1 | Numéro de Fibonacci |
| F n = F n-1 + F n-2 | a 1 = 1, a 2 = 3 | Numéro Lucas |
| F n = F n-2 + F n-3 | a 1 = a 2 = a 3 = 1 | Séquence de Padovan |
| F n = 2F n-1 + F n-2 | a 1 = 0, a 2 = 1 | Numéro Pell |
Comment résoudre la relation de récurrence linéaire
Supposons qu'une relation de récurrence linéaire à deux ordres soit - $ F_n = AF_ {n-1} + BF_ {n-2} $ où A et B sont des nombres réels.
L'équation caractéristique de la relation de récurrence ci-dessus est -
$$ x ^ 2 - Axe - B = 0 $$
Trois cas peuvent survenir lors de la recherche des racines -
Case 1- Si cette équation prend la forme $ (x- x_1) (x- x_1) = 0 $ et qu'elle produit deux racines réelles distinctes $ x_1 $ et $ x_2 $, alors $ F_n = ax_1 ^ n + bx_2 ^ n $ est la solution. [Ici, a et b sont des constantes]
Case 2 - Si cette équation prend la forme $ (x- x_1) ^ 2 = 0 $ et qu'elle produit une racine réelle unique $ x_1 $, alors $ F_n = a x_1 ^ n + bn x_1 ^ n $ est la solution.
Case 3 - Si l'équation produit deux racines complexes distinctes, $ x_1 $ et $ x_2 $ sous forme polaire $ x_1 = r \ angle \ theta $ et $ x_2 = r \ angle (- \ theta) $, alors $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ est la solution.
Problem 1
Résolvez la relation de récurrence $ F_n = 5F_ {n-1} - 6F_ {n-2} $ où $ F_0 = 1 $ et $ F_1 = 4 $
Solution
L'équation caractéristique de la relation de récurrence est -
$$ x ^ 2 - 5x + 6 = 0, $$
Donc, $ (x - 3) (x - 2) = 0 $
Par conséquent, les racines sont -
$ x_1 = 3 $ et $ x_2 = 2 $
Les racines sont réelles et distinctes. Donc, c'est sous la forme du cas 1
Par conséquent, la solution est -
$$ F_n = ax_1 ^ n + bx_2 ^ n $$
Ici, $ F_n = a3 ^ n + b2 ^ n \ (Comme \ x_1 = 3 \ et \ x_2 = 2) $
Par conséquent,
$ 1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b $
4 $ = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b $
En résolvant ces deux équations, nous obtenons $ a = 2 $ et $ b = -1 $
Par conséquent, la solution finale est -
$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n - 2 ^ n $$
Problem 2
Résoudre la relation de récurrence - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ où $ F_0 = 3 $ et $ F_1 = 17 $
Solution
L'équation caractéristique de la relation de récurrence est -
$$ x ^ 2 - 10x -25 = 0 $$
Donc $ (x - 5) ^ 2 = 0 $
Par conséquent, il existe une seule racine réelle $ x_1 = 5 $
Comme il y a une seule racine réelle valorisée, cela se présente sous la forme du cas 2
Par conséquent, la solution est -
$ 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 $
En résolvant ces deux équations, nous obtenons $ a = 3 $ et $ b = 2/5 $
Par conséquent, la solution finale est - $ F_n = 3,5 ^ n + (2/5) .n.2 ^ n $
Problem 3
Résolvez la relation de récurrence $ F_n = 2F_ {n-1} - 2F_ {n-2} $ où $ F_0 = 1 $ et $ F_1 = 3 $
Solution
L'équation caractéristique de la relation de récurrence est -
$$ x ^ 2 -2x -2 = 0 $$
Par conséquent, les racines sont -
$ x_1 = 1 + i $ et $ x_2 = 1 - i $
Sous forme polaire,
$ x_1 = r \ angle \ theta $ et $ x_2 = r \ angle (- \ theta), $ où $ r = \ sqrt 2 $ et $ \ theta = \ frac {\ pi} {4} $
Les racines sont imaginaires. Donc, c'est sous la forme du cas 3.
Par conséquent, la solution est -
$ F_n = (\ sqrt 2) ^ n (un 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 ) $
En résolvant ces deux équations, nous obtenons $ a = 1 $ et $ b = 2 $
Par conséquent, la solution finale est -
$ F_n = (\ sqrt 2) ^ n (cos (n. \ Pi / 4) + 2 sin (n. \ Pi / 4)) $
Relation de récurrence non homogène et solutions particulières
Une relation de récurrence est dite non homogène si elle est de la forme
$ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ où $ f (n) \ ne 0 $
Sa relation de récurrence homogène associée est $ F_n = AF_ {n – 1} + BF_ {n-2} $
La solution $ (a_n) $ d'une relation de récurrence non homogène comporte deux parties.
La première partie est la solution $ (a_h) $ de la relation de récurrence homogène associée et la seconde partie est la solution particulière $ (a_t) $.
$$ a_n = a_h + a_t $$
La solution de la première partie se fait en utilisant les procédures décrites dans la section précédente.
Pour trouver la solution particulière, nous trouvons une solution d'essai appropriée.
Soit $ f (n) = cx ^ n $; soit $ x ^ 2 = Ax + B $ l'équation caractéristique de la relation de récurrence homogène associée et soit $ x_1 $ et $ x_2 $ ses racines.
Si $ x \ ne x_1 $ et $ x \ ne x_2 $, alors $ a_t = Ax ^ n $
Si $ x = x_1 $, $ x \ ne x_2 $, alors $ a_t = Anx ^ n $
Si $ x = x_1 = x_2 $, alors $ a_t = An ^ 2x ^ n $
Exemple
Soit une relation de récurrence non homogène $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ avec des racines caractéristiques $ x_1 = 2 $ et $ x_2 = 5 $. Les solutions d'essai pour différentes valeurs possibles de $ f (n) $ sont les suivantes -
| f (n) | Solutions d'essai |
|---|---|
| 4 | UNE |
| 5,2 n | An2 n |
| 8,5 n | An5 n |
| 4 n | A4 n |
| 2n 2 + 3n + 1 | Un 2 + Bn + C |
Problem
Résolvez la relation de récurrence $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7,5 ^ n $ où $ F_0 = 4 $ et $ F_1 = 3 $
Solution
Il s'agit d'une relation linéaire non homogène, où l'équation homogène associée est $ F_n = 3F_ {n-1} + 10F_ {n-2} $ et $ f (n) = 7,5 ^ n $
L'équation caractéristique de sa relation homogène associée est -
$$ x ^ 2 - 3x -10 = 0 $$
Ou, $ (x - 5) (x + 2) = 0 $
Ou, $ x_1 = 5 $ et $ x_2 = -2 $
D'où $ a_h = a.5 ^ n + b. (- 2) ^ n $, où a et b sont des constantes.
Puisque $ f (n) = 7,5 ^ n $, c'est-à-dire de la forme $ cx ^ n $, une solution d'essai raisonnable de at sera $ Anx ^ n $
$ a_t = Anx ^ n = An5 ^ n $
Après avoir mis la solution dans la relation de récurrence, on obtient -
$ An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7,5 ^ n $
En divisant les deux côtés par 5 $ ^ {n-2} $, on obtient
$ An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7,5 ^ 2 $
Ou, 25 $ An = 15 An - 15 A + 10 An - 20 A + 175 $
Ou, 35 $ A = 175 $
Ou, $ A = 5 $
Donc, $ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $
La solution de la relation de récurrence peut s'écrire -
$ F_n = a_h + a_t $
$ = a.5 ^ n + b. (- 2) ^ n + n5 ^ {n + 1} $
En mettant des valeurs de $ F_0 = 4 $ et $ F_1 = 3 $, dans l'équation ci-dessus, nous obtenons $ a = -2 $ et $ b = 6 $
Par conséquent, la solution est -
$ F_n = n5 ^ {n + 1} + 6. (- 2) ^ n -2,5 ^ n $
Générer des fonctions
Generating Functions représente des séquences où chaque terme d'une séquence est exprimé comme un coefficient d'une variable x dans une série de puissance formelle.
Mathématiquement, pour une séquence infinie, disons $ a_0, a_1, a_2, \ dots, a_k, \ dots, $ la fonction génératrice sera -
$$ G_x = a_0 + a_1x + a_2x ^ 2 + \ dots + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k $$
Quelques domaines d'application
Les fonctions de génération peuvent être utilisées aux fins suivantes -
Pour résoudre une variété de problèmes de comptage. Par exemple, le nombre de façons de changer pour un Rs. Billet de 100 avec les notes des dénominations Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 et Rs.50
Pour résoudre les relations de récurrence
Pour prouver certaines des identités combinatoires
Pour trouver des formules asymptotiques pour les termes de séquences
Problem 1
Quelles sont les fonctions génératrices pour les séquences $ \ lbrace {a_k} \ rbrace $ avec $ a_k = 2 $ et $ a_k = 3k $?
Solution
Lorsque $ a_k = 2 $, fonction de génération, $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ points $
Lorsque $ a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ points \ points $
Problem 2
Quelle est la fonction génératrice de la série infinie; $ 1, 1, 1, 1, \ points $?
Solution
Ici, $ a_k = 1 $, pour $ 0 \ le k \ le \ infty $
Par conséquent, $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $
Quelques fonctions de génération utiles
Pour $ 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) $
Pour $ 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}} $
Pour $ 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} $
Pour $ 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} $