Aula 14 - Recorrências Matemática Discreta 2021 2

Aula 14 Recorrˆencias MAT13700 Matematica Discreta Ricardo Recorrˆencias lineares de 1a ordem Exemplo xn 3xn1 3n1 x0 13 Recorrências lineares de 1a ordem am a0 m3 Recorrˆencias lineares de 1a ordem Vamos ver que e possıvel transformar quase toda recorrˆencia linear de 1a ordem naohomogˆenea xn gnxn1 hn em uma recorrˆencia da forma xn xn1 f n Seja an uma solucao naonula da recorrˆencia xn gnxn1 ym y0 ym1 gm am1 hm Recorrˆencias lineares de 2a ordem Vamos comecar com recorrˆencias lineares de 2a ordem homogˆeneas e com coeficientes constantes xn a xn1 b xn2 x0 c0 x1 c1 a b R com b 0 para garantir que a recorrˆencia seja de 2a ordem Ym alpha nm X0 c0 X1 c1 quad c0 alpha n0 Leftrightarrow alpha c0 C1 alpha n quad Rightarrow quad n fracc12 c1 alpha n Recorrˆencias lineares de 2a ordem A equacao caracterıstica da recorrˆencia acima e r2 ar b b 0 0 nao e raiz Teorema Sejam r1 e r2 as raızes da equacao caracterıstica r2 pr q Entao an α rn 1 βrn 2 e solucao da recorrˆencia xn pxn1 qxn2 para quaisquer valores de α e β Recorrˆencias lineares de 2a ordem Exemplo xn xn1 xn2 Fibonacci A equacao caracterıstica e r2 r 1 0 Que tem raızes r1 1 5 2 r2 1 5 2 Y0 0 Leftrightarrow alpha beta X1 1 Leftrightarrow alpha n1 alpha n2 1 alphan1 n2 1 alpha left fracx sqrt52 fracx sqrt52 right 1 alpha sqrt5 1 Leftrightarrow alpha frac1sqrt5 beta frac1sqrt5 am frac1sqrt5 left frac1 sqrt52 rightm frac1sqrt5 left frac1 sqrt52 rightm Recorrˆencias lineares de 2a ordem Se r1 r2 0 entao a equacao caracterıstica e r2 0 e a recorrˆencia nao e de 2a orderm Teorema Sejam r1 e r2 as raızes da equacao caracterıstica r2 pr q Se r1 r2 entao todas as solucoes da recorrˆencia xn pxn1 qxn2 sao da forma an α rn 1 βrn 2 para α e β constantes Demonstracao Seja yn uma solucao qualquer de xn pxn1 qxn2 det M n₂ n₁ 0 M invertível O sistema tem soluções únicas zm rho zm1 gamma zm2 zm ym alpha n1m beta n2m 0 extsatisfazendo Recorrˆencias lineares de 2a ordem Temos 3 casos r1 r2 sao reais r1 r2 sao complexos r1 r2 Recorrˆencias lineares de 2a ordem r1 r2 sao reais Exemplo Fibonacci Recorrências lineares de 2a ordem Recorrˆencias lineares de 2a ordem r1 r2 sao complexos r2 r1 Vamos escrever r1 e r2 r1 na forma polar r1 ρ cos θ i sen θn r2 ρ cos θ i sen θn Entao rn 1 ρ cosnθ i sen nθn rn 2 ρ cosnθ i sen nθn Recorrˆencias lineares de 2a ordem Escolhendo β α obtemos Recorrˆencias lineares de 2a ordem Entao se r1 e r2 sao complexos a solucao pode ser escrita na forma ρnα cosnθ β sen nθ Exemplo Referˆencias 1 Matematica Discreta Lovasz Pelikan Vesztergombi 2 Analise Combinatoria e Probabilidade Morgado Pitombeira Carvalho e Fernandez 3 Matematica Comcreta Graham Knuth Patashnik 4 Princıpios de Combinatoria e Probabilidade Tertuliano Franco SBM 2020 5 Matematica Discreta Morgado e Carvalho PROFMAT