Revisão Matemática Discreta: Demonstrações por Indução e Fórmula Explícita de Sequências

Matematica Discreta Turma 01 Revisao do conteudo para a avaliacao da segunda unidade Exercicio da Lista de exercicios 8 ① Demonstre por indução matemática que j Para todo x 1 3 24 3x³ 3ˣx³ Demonstração PB Temos que demonstrar que 3 1³ 3¹1³ Temos que 3¹1³ 31³ 3 1³ Portanto 3 1³ 3¹1³ PI Temos que demonstrar que para todo y 1 se 3 24 3y³ 3ʸy³ então 3 24 3y1³ 3ʸ¹y1³ Seja k ℕ₀ um elemento particular e arbitrário tal que 3 24 3k³ 3ᵏk³ onde k 1 Temos que 3 24 3k1³ 3 24 3k³ 3k1³ Pela ordem dos naturais 3ᵏk³ 3k1³ Pela HI e por substituição 3ᵏ 3³ k³ k1³ 3ᵏ¹ k³ k1³ 3ᵏ¹ k k1³ 3ᵏ¹k1³ 20 21 21 104 105 106 106 Objetivo 3 24 3k1³ 3ᵏ¹k1³ Portanto para todo y 1 se 3 24 3y³ 3ʸy³ então 3 24 3y1³ 3ʸ¹y1³ Portanto para todo x 1 3 24 3x³ 3ˣx³ QED Exercicio da lista de exercicios 9 ① Demonstre por indução matemática que e Para todo x 1 5i1 x35x 2 i1 Demonstração PB Temos que demonstrar que 5i1 1351 i1 2 Temos que 5i1 511 Pela def recursiva de somatório i1 4 Temos que 1351 3 52 8 2 4 Portanto 5i1 1351 i1 2 PI Temos que demonstrar que para todo y 1 se 5i1 y35y i1 2 então 5i1 y13 5y1 i1 2 Seja k ℕ₀ um elemento particular e arbitrário tal que 5i1 k35k onde k1 i1 2 Temos que 5i1 5i1 5k11 Pela def recursiva de somatório i1 j1 k1 k35k 5k11 Pela HI e por substituição 2 2 k35k 25k11 2 k35k 10k1 2 2 3k 5k² 10k 10 2 2 5k² 8k 5k 8 2 k15k 8 2 k13 5k 5 2 k13 5k1 2 Objetivo 5i1 k13 5k1 i1 k1 Portanto para todo y 1 se 5i1 y35y i1 2 então 5i1 y13 5y1 i1 2 Portanto para todo x 1 5i1 x35x i1 2 QED Exercício da Lista de exercícios 10 ① 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 h Seja t₁ t₂ t₃ uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo k 2 tₖ tₖ₁ k 1k Condição inicial t₁ 1 Resolução t₁ 1 22 112 t₂ 1 21 2 32 212 t₃ 1 21 231 3 32 43 42 312 t₄ 1 21 231 341 4 32 43 54 52 412 Possível fórmula explícita para todo x 1 tₓ x12 Temos que demonstrar que a fórmula explícita está correta Demonstração PB Temos que demonstrar que t₁ 112 Temos que 112 1 t₁ Pela condição inicial Portanto t₁ 112 PI Temos que demonstrar que para todo y 1 se tᵧ y12 então tᵧ₁ y112 Seja k ℕ₀ um elemento particular e arbitrário tal que tₖ k12 onde k 1 Temos que tₖ₁ tₖ k11k1 Pela relação de recorrência k12 k11k1 Pela HI e por substituição k1k112 k1 k112 Objetivo tₖ₁ k112 Portanto para todo y 1 se tᵧ y12 então tᵧ₁ y112 Portanto a fórmula explícita está correta QED