Matemática Discreta - Relação de Recorrência
Neste capítulo, discutiremos como as técnicas recursivas podem derivar sequências e ser usadas para resolver problemas de contagem. O procedimento para encontrar os termos de uma sequência de maneira recursiva é chamadorecurrence relation. Estudamos a teoria das relações de recorrência linear e suas soluções. Finalmente, introduzimos funções geradoras para resolver relações de recorrência.
Definição
Uma relação de recorrência é uma equação que define recursivamente uma sequência onde o próximo termo é uma função dos termos anteriores (Expressando $ F_n $ como alguma combinação de $ F_i $ com $ i <n $).
Example - Série Fibonacci - $ F_n = F_ {n-1} + F_ {n-2} $, Torre de Hanói - $ F_n = 2F_ {n-1} + 1 $
Relações de recorrência linear
Uma equação de recorrência linear de grau k ou ordem k é uma equação de recorrência que está no formato $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ pontos A_k x_ {nk} $ ($ A_n $ é uma constante e $ A_k \ neq 0 $) em uma sequência de números como um polinômio de primeiro grau.
Estes são alguns exemplos de equações de recorrência linear -
| Relações de recorrência | Valores iniciais | Soluções |
|---|---|---|
| F n = F n-1 + F n-2 | a 1 = a 2 = 1 | Número de Fibonacci |
| F n = F n-1 + F n-2 | a 1 = 1, a 2 = 3 | Número lucas |
| F n = F n-2 + F n-3 | a 1 = a 2 = a 3 = 1 | Sequência Padovan |
| F n = 2F n-1 + F n-2 | a 1 = 0, a 2 = 1 | Número Pell |
Como resolver a relação de recorrência linear
Suponha que uma relação de recorrência linear de duas ordens seja - $ F_n = AF_ {n-1} + BF_ {n-2} $ onde A e B são números reais.
A equação característica para a relação de recorrência acima é -
$$ x ^ 2 - Ax - B = 0 $$
Três casos podem ocorrer ao encontrar as raízes -
Case 1- Se esta equação fatora como $ (x- x_1) (x- x_1) = 0 $ e produz duas raízes reais distintas $ x_1 $ e $ x_2 $, então $ F_n = ax_1 ^ n + bx_2 ^ n $ é a solução. [Aqui, a e b são constantes]
Case 2 - Se esta equação fatora como $ (x- x_1) ^ 2 = 0 $ e produz uma raiz real única $ x_1 $, então $ F_n = a x_1 ^ n + bn x_1 ^ n $ é a solução.
Case 3 - Se a equação produz duas raízes complexas distintas, $ x_1 $ e $ x_2 $ na forma polar $ x_1 = r \ ângulo \ theta $ e $ x_2 = r \ ângulo (- \ theta) $, então $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ é a solução.
Problem 1
Resolva a relação de recorrência $ F_n = 5F_ {n-1} - 6F_ {n-2} $ onde $ F_0 = 1 $ e $ F_1 = 4 $
Solution
A equação característica da relação de recorrência é -
$$ x ^ 2 - 5x + 6 = 0, $$
Portanto, $ (x - 3) (x - 2) = 0 $
Portanto, as raízes são -
$ x_1 = 3 $ e $ x_2 = 2 $
As raízes são reais e distintas. Então, isso está na forma do caso 1
Portanto, a solução é -
$$ F_n = ax_1 ^ n + bx_2 ^ n $$
Aqui, $ F_n = a3 ^ n + b2 ^ n \ (As \ x_1 = 3 \ e \ x_2 = 2) $
Portanto,
$ 1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b $
$ 4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b $
Resolvendo essas duas equações, obtemos $ a = 2 $ e $ b = -1 $
Portanto, a solução final é -
$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n - 2 ^ n $$
Problem 2
Resolva a relação de recorrência - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ onde $ F_0 = 3 $ e $ F_1 = 17 $
Solution
A equação característica da relação de recorrência é -
$$ x ^ 2 - 10x -25 = 0 $$
Então $ (x - 5) ^ 2 = 0 $
Portanto, há uma única raiz real $ x_1 = 5 $
Como há uma única raiz de valor real, isso está na forma do caso 2
Portanto, a solução é -
$ 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 $
Resolvendo essas duas equações, obtemos $ a = 3 $ e $ b = 2/5 $
Portanto, a solução final é - $ F_n = 3,5 ^ n + (2/5) .n.2 ^ n $
Problem 3
Resolva a relação de recorrência $ F_n = 2F_ {n-1} - 2F_ {n-2} $ onde $ F_0 = 1 $ e $ F_1 = 3 $
Solution
A equação característica da relação de recorrência é -
$$ x ^ 2 -2x -2 = 0 $$
Portanto, as raízes são -
$ x_1 = 1 + i $ e $ x_2 = 1 - i $
Na forma polar,
$ x_1 = r \ angle \ theta $ e $ x_2 = r \ angle (- \ theta), $ onde $ r = \ sqrt 2 $ e $ \ theta = \ frac {\ pi} {4} $
As raízes são imaginárias. Então, isso está na forma do caso 3.
Portanto, a solução é -
$ 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 ) $
Resolvendo essas duas equações, obtemos $ a = 1 $ e $ b = 2 $
Portanto, a solução final é -
$ F_n = (\ sqrt 2) ^ n (cos (n. \ Pi / 4) + 2 sin (n. \ Pi / 4)) $
Relação de recorrência não homogênea e soluções particulares
Uma relação de recorrência é chamada de não homogênea se estiver na forma
$ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ onde $ f (n) \ ne 0 $
Sua relação de recorrência homogênea associada é $ F_n = AF_ {n – 1} + BF_ {n-2} $
A solução $ (a_n) $ de uma relação de recorrência não homogênea tem duas partes.
A primeira parte é a solução $ (a_h) $ da relação de recorrência homogênea associada e a segunda parte é a solução particular $ (a_t) $.
$$ a_n = a_h + a_t $$
A solução da primeira parte é feita usando os procedimentos discutidos na seção anterior.
Para encontrar a solução específica, encontramos uma solução de teste apropriada.
Seja $ f (n) = cx ^ n $; seja $ x ^ 2 = Ax + B $ a equação característica da relação de recorrência homogênea associada e seja $ x_1 $ e $ x_2 $ suas raízes.
Se $ x \ ne x_1 $ e $ x \ ne x_2 $, então $ a_t = Ax ^ n $
Se $ x = x_1 $, $ x \ ne x_2 $, então $ a_t = Anx ^ n $
Se $ x = x_1 = x_2 $, então $ a_t = An ^ 2x ^ n $
Exemplo
Seja uma relação de recorrência não homogênea $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ com raízes características $ x_1 = 2 $ e $ x_2 = 5 $. As soluções de teste para diferentes valores possíveis de $ f (n) $ são as seguintes -
| f (n) | Soluções de teste |
|---|---|
| 4 | UMA |
| 5,2 n | An2 n |
| 8,5 n | An5 n |
| 4 n | A4 n |
| 2n 2 + 3n + 1 | Um 2 + Bn + C |
Problem
Resolva a relação de recorrência $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7,5 ^ n $ onde $ F_0 = 4 $ e $ F_1 = 3 $
Solution
Esta é uma relação linear não homogênea, onde a equação homogênea associada é $ F_n = 3F_ {n-1} + 10F_ {n-2} $ e $ f (n) = 7,5 ^ n $
A equação característica de sua relação homogênea associada é -
$$ x ^ 2 - 3x -10 = 0 $$
Ou $ (x - 5) (x + 2) = 0 $
Ou $ x_1 = 5 $ e $ x_2 = -2 $
Portanto, $ a_h = a.5 ^ n + b. (- 2) ^ n $, onde aeb são constantes.
Dado que $ f (n) = 7,5 ^ n $, ou seja, da forma $ cx ^ n $, uma solução experimental razoável de at será $ Anx ^ n $
$ a_t = Anx ^ n = An5 ^ n $
Depois de colocar a solução na relação de recorrência, obtemos -
$ An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7,5 ^ n $
Dividindo ambos os lados por $ 5 ^ {n-2} $, obtemos
$ An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7,5 ^ 2 $
Ou $ 25An = 15A - 15A + 10An - 20A + 175 $
Ou $ 35A = 175 $
Ou $ A = 5 $
Portanto, $ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $
A solução da relação de recorrência pode ser escrita como -
$ F_n = a_h + a_t $
$ = a.5 ^ n + b. (- 2) ^ n + n5 ^ {n + 1} $
Colocando os valores de $ F_0 = 4 $ e $ F_1 = 3 $, na equação acima, obtemos $ a = -2 $ e $ b = 6 $
Portanto, a solução é -
$ F_n = n5 ^ {n + 1} + 6. (- 2) ^ n -2,5 ^ n $
Funções Geradoras
Generating Functions representa sequências onde cada termo de uma sequência é expresso como um coeficiente de uma variável x em uma série de potências formal.
Matematicamente, para uma sequência infinita, digamos $ a_0, a_1, a_2, \ dots, a_k, \ dots, $ a função geradora será -
$$ G_x = a_0 + a_1x + a_2x ^ 2 + \ dots + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k $$
Algumas áreas de aplicação
Funções geradoras podem ser usadas para os seguintes fins -
Para resolver uma variedade de problemas de contagem. Por exemplo, o número de maneiras de fazer alterações por Rs. 100 nota com as notas de denominações Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 e Rs.50
Para resolver relações de recorrência
Para provar algumas das identidades combinatórias
Para encontrar fórmulas assintóticas para termos de sequências
Problem 1
Quais são as funções geradoras para as sequências $ \ lbrace {a_k} \ rbrace $ com $ a_k = 2 $ e $ a_k = 3k $?
Solution
Quando $ a_k = 2 $, função geradora, $ 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} + \ pontos \ dots $
Problem 2
Qual é a função geradora da série infinita; $ 1, 1, 1, 1, \ dots $?
Solution
Aqui, $ a_k = 1 $, por $ 0 \ le k \ le \ infty $
Portanto, $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $
Algumas funções úteis de geração
Para $ 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) $
Para $ 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}} $
Para $ 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} $
Para $ 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} $