Revisão Matematica Discreta Indução Matematica e Recorrência

Matemática Discreta Turma 02 Revisão do conteúdo para a avaliação da segunda unidade Exercício da lista de exercícios 8 1 Demonstre por indução matemática que Px d Para todo x 0 1 2 22 2x 2x1 1 3 Demonstração PB Temos que demonstrar que 20 201 1 3 Temos que 201 1 3 2 1 3 3 3 1 20 Portanto 20 201 1 3 PI Temos que demonstrar que para todo y 0 se 1 2 22 2y 2y1 1 3 Então 1 2 22 2k 2k1 1 3 Seja k N0 um elemento particular e arbitrário tal que 1 2 22 2k 2k1 1 3 onde k 0 HI Temos que 1 2 22 2k1 1 2 22 2k 2k1 Pela ordem dos naturais 2k1 1 3 2k1 pela HI e por substituição 2k1 1 3 32k1 22k1 1 3 2k11 1 3 objetivo 1 2 22 2k1 2k11 1 3 Portanto para todo y 0 se 1 2 22 2y 2y1 1 3 Então 1 2 22 2y1 2y11 1 3 Portanto para todo x 0 1 2 22 2x 2x1 1 3 QED Exercício da lista de exercícios 9 1 Demonstre por indução matemática que Px h Para todo x 1 i1x i2 x 2x Demonstração PB Temos que demonstrar que i11 i2 1 21 Temos que i11 i2 1 2 Pela def recursiva do produtório 1 21 Portanto i11 i2 1 21 PI Temos que demonstrar que para todo y 1 se i1y i2 y 2y Então i1y1 i2 y1 2y1 Seja k N0 um elemento particular e arbitrário tal que i1k i2 k 2k onde k 1 HI Temos que i1k1 i2 i1k i2 k12 Pela def recursiva do produtório k 2k k12 Pela HI e por substituição k k1 2k 2 k1 2k1 5 6 6 80 81 82 82 Objetivo i1k1 i2 k1 2k1 Portanto para todo y 1 se i1y i2 y 2y Então i1y1 i2 y1 2y1 Portanto para todo x 1 i1x i2 x 2x QED Exercício da lista de exercícios 10 1 Use o método da iteração para achar uma fórmula explícita para cada uma das sequências a seguir e demonstre por indução matemática que a fórmula explícita encontrada está correta d Seja t0 t1 t2 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo k 1 tk tk1 3k2 Condição inicial t0 0 Resolução t0 0 3 03 t2 0 3 12 3 22 312 22 t1 0 3 12 3 12 t3 0 3 12 3 22 3 32 312 22 32 Rascunho antes de propor a possível fórmula explícita tx 312 22 x2 3xx12x1 6 xx12x1 2 Para todo x 1 12 22 x2 xx12x1 6 Esta fórmula está no final da lista de ex 10 Possível fórmula explícita para todo x 0 tx xx12x1 2 Temos que demonstrar que a fórmula explícita está correta Demonstração PB Temos que demonstrar t0 0012012 Temos que 0012012 0 t0 Pela condição inicial Portanto t0 0012012 PI Temos que demonstrar que para todo y 0 se ty yy12y12 Então ty1 y1y112y112 Seja l N0 um elemento particular e arbitrário tal que tl ll12l12 onde l 0 HI Temos que tl1 tl 3l12 Pela relação de recorrência Objetivo tl1 l1l112l112 ll12l12 3l12 Pela HI e por substituição ll12l12 6l12 l1l2l1 6l12 l12l2 l 6l 62 l12l2 3l 4l 62 l1l22l32 l1l112l212 l1l112l112 Portanto para todo y 0 se ty yy12y12 então ty1 y1y112y112 Portanto a fórmula explícita está correta QED