Lista 8 - Indução Matemática 2021-1

1 Caso base: Para n = 0, temos: Σ 0 3 i = 3 0+1 − 1 i=0 2 30 = 31 − 1 2 Passo indutivo: Suponha n arbitrário. Suponha n ∈ N e que Σ n i=0 3i = 3n+1−1 . Temos: 2 n+1 Σ Σ 3 = i i=0 n 3 i n+1 + 3 = i=0 3n+1 − 1 + 3n+1 = 3n+1 − 1 + 2 · 3n+1 = 2 2 3n+2 − 1 2 Para todo n ∈ N, 3 = Σ n i 3 n+1 − 1 . i=0 2 A indução matemática é descrita da seguinte forma: Para provar um conclusão da forma ∀n.n ∈ N → P (n). Prove que a seguinte fórmula é verdadeira: P (0) ∧ ∀n.n ∈ N ∧ P (n) → P (n + 1) Universidade Federal de Ouro Preto – UFOP Disciplina: Matemática Discreta Artur linhares de oliveira – 20.1.8022 Lista de Exercícios 08: Indução Matemática Revisão 1. Responda formalmente as seguintes questões: a) Defina indução matemática, caso base, passo indutivo e hipótese de indução. b) Por meio de metáfora, mostre que indução matemática funciona. Exercícios 2. (Ribeiro 9.2.1.1) Prove os seguintes teoremas. a) Resposta pessoal. 2 Caso base: Para n = 0, temos: Σ 0 i = 2 0(0 + 1)(2 · 0 + 1) i=0 6 0 = 0 Passo indutivo: Suponha n ∈ N arbitrário e que Σ n i2 = n(n+1)(2n+1) , temos: i=0 6 n+1 Σ i = 2 i=0 Σ n i + (n + 1) = 2 2 i=0 n(n + 1)(2n + 1) + (n + 1)2 = n(n + 1)(2n + 1) + 6(n + 1)2 = 6 (n + 1)(2n2 + 7n + 6) = 6 (n + 1)(n + 2)(2n + 3) = 6 6 Para todo n ∈ N, Σi 2 = n(n + 1)(2n + 1) n i=0 6 b) c) d) Para todo n ∈ N, 5 | (n5 − n) Caso base: Para n = 1, temos: Σ 1 2 i=1 (8i − 5) = 4 · 1 − 1 8 − 5 = 4 − 1 Passo indutivo: Suponha n ∈ N e que Σ n i=1 (8i − 5) = 4n2 − n, temos: n+1 Σ Σ i=1 (8i − 5) = n i=1 4n2 + 8n + 4 − n − 1 = 4(n2 + 2n + 1) − n − 1 = 4(n + 1)2 − (n + 1) (8i − 5) + 8(n + 1) − 5 = 4n2 − n + 8n + 3 = Para todo n ∈ N, (8i − 5) = 4 Σ n 2 i=1 n − n 3 Caso base: Para n = 0, temos: 6 | (70 − 1) = 6 | 0 Passo indutivo: Suponha n ∈ N arbitrário, temos: 7n+1 − 1 = 7n · 7 − 1 = 6(7n) + 6a = 6(7n + a) Portanto, 6 | 7n+1 − 1, o que completa o passo de indução. 6(7n) + (7n − 1) = e) Para todo n ∈ N, 6 | (7n − 1) f) Para todo n ∈ N, 6 | (n3 + 5n) Caso base: Para n = 0, temos: 6 | (03 + 5 · 0) = 6 | 6 Passo indutivo: Suponha n ∈ N arbitrário e que 6 | (n3 + 5n), temos: Caso base: Para n = 1, temos: 5|(15 − 1) = 5|0 Passo indutivo: Suponha n arbitrário. Suponha n ∈ N e que 5|(n5 − n). Temos: (n + 1)5 − (n + 1) = (n + 1)2(n + 1)2(n + 1) − n − 1 = (n2 + 2n + 1)(n2 + 2n + 1)(n + 1) − n − 1 = (n4 + 2n3 + n2 + 2n3 + 4n2 + 2n + n2 + 2n + 1)(n + 1) − n − 1 = (n4 + 4n3 + 6n2 + 4n + 1)(n + 1) − n − 1 = n5 + 4n4 + 6n3 + 4n2 + n + n4 + 4n3 + 6n2 + 4n + 1 − n − 1 = (5a) + 5n4 + 10n3 + 10n2 + 5n = 5(a + n4 + 2n3 + 2n2 + n) Portanto, 5|(n + 1)5 − (n + 1). O que completa o passo de indução. (n5 − n) + 5n4 + 10n3 + 10n2 + 5n = 4 Caso base: Para n = 0, temos: 2|02 + 0 = 2|0 Passo indutivo: Suponha n arbitrário. Suponha n ∈ N e que 2|(n2 + n). Temos: (n + 1)2 + (n + 1) = n2 + 2n + 1 + n + 1 = (n2 + n) + 2n + 2 = (2a) + 2n + 2 = 2(a + n + 1) Portanto, 2|(n + 1)2 + (n + 1). O que completa o passo de indução. g) Para todo n ∈ N, 2 | (n2 + n) (n + 1)3 + 5(n + 1) = n3 + 3n2 + 3n + 1 + 5n + 5 = n3 + 5n + 3n2 + 3n + 6 = 6a + 3n2 + 3n + 6 = 6(a + 1 + n2/2 + n/2) Caso1: n é par. Suponha k ∈ N arbitrário e que n = 2k. 6(a + 1 + 4k2/2 + 2k/2) = 6(a + 1 + 2k2 + k) Caso2: n é ímpar. Suponha k ∈ N arbitrário e que n = 2k + 1. 6 a + 1 + 4k + 4k + 1 2 2 + 2k + 1 2 = 6(a + 1 + 2k2 + 2k + 1/2 + k + 1/2) = 6(a + 1 + 2k2 + 3k + 1) Portanto, 6 | (n + 1)2 + (n + 1). O que completa o passo de indução.