Matematica Discreta - Revisao para Avaliacao - Lista de Exercicios Resolvidos

Matematica Discreta Revisão do conteúdo para a avaliação da segunda unidade 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 i Seja t1 t2 t3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo k 2 tk tk1 13k 23k1 Condição inicial t1 14 Resolução t1 14 1311 t2 t1 1322321 14 117 77 17 87 27 2321 t3 t1 1 322321 1332331 77 17 710 27 1710 20 1 710 21710 310 3331 ty 1y 1322321 1332331 1342341 310 11013 4016013 413 4341 t5 413 1352351 1113 11316 651316 516 5351 Possível fórmula explícita para todo x 1 tx x3x1 Temos que demonstrar que a fórmula explícita está correta Demonstração PI Temos que demonstrar que t1 1311 Temos que 311 4 t1 Pela condição inicial Portanto t1 1311 PI Temos que demonstrar que para todo y 1 se ty y3y1 então ty1 y13y11 seja l N0 um elemento particular e arbitrário tal que tl l3l1 onde l 1 Temos que tl1 tl 13l1 23l11 Pela relação de recorrência l3l1 13l1 23l1 1 Pela HI e por substituição l3l1 13l3 23l1 1 l3l1 13l13l1 1 l3l1 1 13l13l1 1 l3l3 1 13l13l11 l3l4 13l13l11 3l2 4l 13l13l11 3l2 l 3l 13l13l11 l13l13l13l11 l13l11 Portanto para todo y 1 se ty y3y1 então ty1 y13y1 1 Portanto a fórmula explícita está correta QED Lista de exercícios 9 g Para todo x 1 Πi1x 32i 32x2 x2 Demonstração PB Temos que demonstrar que Πi1k1 32i 32k12 k12 Temos que Πi1k1 32i Πi1k 32i 32k1 Pela def recursiva de produtório 32k2 k2 32k1 Pela HI e por substituição 32k2 k2 k 1 32k2 k 2k 22 32k2 2k 1 k 12 32k 12 k 12 Portanto para todo y 1 se Πi1y 32i 32y2 y 2 então Πi1y1 32i 32y12 y12 Portanto Para todo x 1 Πi1x 32i 32x2 x2 QED Lista de exercícios 3 k Para todo x 1 32 94 278 32x 32x2 x2 Demonstração PB Temos que demonstrar que 321 322 12 Temos que 321 12 321 Temos que 321 12 321 Portanto 1Πi1x 32i 32x2 12 PI Temos que demonstrar que para todo y 1 se Πi1y 32i 32y2 y2 então Πi1y1 32i 32y 12 y 12 seja k N0 um elemento particular e arbitrário tal que Πi1k 32i 32k2 k2 onde k 1 Temos que Πi1 k 1 32i Πi1k 32i 32k1 Pela def recursiva de produtório 32k2 k2 32k1 Pela HI e por substituição 32k2 k2 k 1 32k2 k 2k 22 32k2 2k 1 k 12 32k 12 k 12 Portanto para todo y 1 se Πi1y 32i 32y2 y2 então Πi1y1 32i 32y12 y12 Portanto Para todo x 1 Πi1x 32i 32x2 x2 QED Lista de exercícios 3 k Para todo x 1 32 94 278 32x 32x2 x2 Demonstração PB Temos que demonstrar que 321 322 12 Temos que 321 12 321 Portanto 321 32212 PI Temos que demonstrar que para todo y 1 se 32 94 278 32y 32y²y2 então 32 94 278 32y1 32y1²y12 Seja k N₀ um elemento particular e arbitrário tal que 32 94 278 32k 32k²k2 onde k 1 Temos que 32 94 278 32k1 32 94 278 32ᵏ 32 32k²k2 32k1 pela ordem dos naturais 32k²k2 32k1 pela HI e por substituição 32k²k2 k 1 32k² k 2k 22 32k² 3k 22 32k1² k12 Portanto para todo y 1 se 32 94 278 32y 32y²y2 então 32 94 278 32y1 32y1²y12 Portanto Para todo x 1 32 94 278 32x 32x² x2 QED