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

Aula 15 Recorrˆencias MAT13700 Matematica Discreta Ricardo Recorrˆencias lineares de 2a ordem xn p xn1 q xn2 x0 c0 x1 c1 p q R q 0 A equacao caracterıstica da recorrˆencia acima e r2 pr q Teorema Sejam r1 e r2 as raızes da equacao caracterıstica r2 pr q Entao yn α rn 1 βrn 2 e solucao da recorrˆencia xn pxn1 qxn2 para quaisquer valores de α e β Recorrˆencias lineares de 2a ordem Teorema Sejam r1 e r2 as raızes da equacao caracterıstica r2 pr q com r1 r2 Entao todas as solucoes da recorrˆencia xn pxn1 qxn2 sao da forma yn α rn 1 βrn 2 para alguma escolha de α e β Temos 3 casos r1 r2 sao reais r1 r2 sao complexos r1 r2 o segundo teorema nao diz nada sobre este caso Recorrˆencias lineares de 2a ordem Exemplo xn 3xn1 2xn2 x0 x1 1 Recorrências lineares de 2a ordem Recorrˆencias lineares de 2a ordem Exemplo xn xn1 6xn2 x0 1 x1 4 Recorrências lineares de 2a ordem Recorrˆencias lineares de 2a ordem Exemplo xn xn1 xn2 x0 1 x1 12 α²ρ αρ12 hαβ1 xₘ121ι32ⁿ1ι32º 1ι32cos π3 i sin π3 1ι33ⁿ cosmπ3 i sinmπ3 1ι32ⁿ cosmπ3 i sinmπ3 βα xm frac12 left omega0 left fracm pi3 right i nr left fracm pi3 right omega0 left fracm pi3 right i nr left frac2 m pi3 right right Recorrˆencias lineares de 2a ordem Teorema Seja r1 r2 r a unica solucao da equacao caracterıstica da recorrˆencia xn p xn1 q xn2 Entao para quaisquer α e β yn α β n p2n e solucao da recorrˆencia ym left alpha m rho right left fracm2 right 2 n m beta m n m 0 Recorrˆencias lineares de 2a ordem Teorema Seja r1 r2 r a unica solucao da equacao caracterıstica da recorrˆencia xn p xn1 q xn2 Entao todas as solucoes da recorrˆencia sao da forma yn α β n p2n para α e β constantes Recorrências lineares de 2a ordem Recorrências lineares de 2a ordem Recorrˆencias lineares de 2a ordem Exemplo xn 4xn1 4xn2 x0 1 x1 0 Recorrˆencias lineares de 2a ordem Teorema Sejam an uma solucao particular da recorrˆencia xn p xn1 q xn2 f n e yn a solucao geral da recorrˆencia homogˆenea associada xn p xn1 q xn2 Entao todas as solucoes da recorrˆencia nao homogˆenea sao da forma yn an Recorrências lineares de 2a ordem Recorrências lineares de 2a ordem Recorrˆencias lineares de 2a ordem Exemplo xn 6xn1 8xn2 n 3n 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