Demonstração por indução - Teoria e exercícios

DEMONSTRAÇÃO POR INDUÇÃO Más quando temos uma proposição matemática verdadeira para vários casos particulares e não é possível analisar todos os casos, como podemos confirmar que a proposição vale para todos os casos? Por exemplo: Considere a função f : IN → IR definida por f(x) = x² + x + 41. A partir dessa função determinar: f(0) = 41, Todos são primos! Mas tal conjectura, é falsa! Veja o contraexemplo: f(40) = 40² + 40 + 41 = 1600 + 40 + 41 Não é primo! Então o que fazer quando não é possível analisar todos os casos? Utilizamos: Princípio da Indução Finita. Seja P(n) uma propriedade sobre um número natural n maior ou igual a um número natural k fixado. Se P(1) é valido e P(k) ⇒ P(k + 1). Então, P(n) é verdadeira ∀n ≥ k. Duas etapas: Base da indução: envolve a demonstração de que a proposição é verdadeira para o menor valor possível, geralmente o número 1. Passo de indução: assume que a proposição é verdadeira para algum valor genérico k e utiliza essa hipótese para provar que a proposição também é verdadeira para k + 1. Exemplo: Prove por indução que a soma dos primeiros n números ímpares é um quadrado perfeito. 1 + 3 + 5 +…+ (2n−1) = n² Demonstração por indução: 1 + 3 + 5 +…+ (2n−1) = n² Caso base P(1): para n = 1, temos: 1 e 1² = 1 Passo de indução: suponhamos que vale para algum n = k, k ≥ 1, ou seja P(k): 1 + 3 + 5 + … + (2k−1) = k² Então para n = k + 1, temos: P(k+1): 1 + 3 + … + (2k−1) + 2k + 1 Como por hipótese de indução: P(k): 1 + 3 + 5 +…+ (2k−1) = k², temos k² + 2k + 1 = (k + 1)² Logo P(k) ⇒ P(k + 1). Portanto pelo PIF vale ∀n ∈ IN. Giuseppe Peano (27 de agosto de 1858 – 20 de abril de 1932) Axiomas de Peano i) Todo número natural tem um único sucessor; ii) Números naturais diferentes têm sucessores diferentes; iii) Existe um único número natural, chamado um e representado pelo símbolo 1, que não é sucessor de nenhum outro; iv) Seja X um conjunto de números naturais (isto é, X ⊂ IN). Se 1 ∈ X e se, além disso, o sucessor de todo elemento de X ainda pertence a X, então X = IN. Do último axioma, vem o Princípio da Indução: A proposição P(n) é válida para todos os números naturais n, se: i) P(1) é válida ii) Se P(n) é válida então P(n+1) é válida. Exercícios 1º] Demonstre que a soma dos primeiros n números pares é igual a n(n + 1). 2 + 4 + 6 + ... + 2n = n(n + 1). Caso base P(1): para n = 1, temos: 2 e 1(1 + 1) = 2, Passo de indução: suponhamos que vale para algum n = k, k ≥ 1, ou seja P(k): 2 + 4 + ... + 2k = k(k + 1) Então para n = k + 1, temos: P(k + 1): 2 + 4 + ... + 2k + 2k + 2 Como por hipótese de indução: 2 + 4 + 6 + ... + 2k = k(k + 1), temos P(k + 1): k(k + 1) + 2k + 2 = k² + k + 2k + 2 = k² + 2k + k + 2 = k(k + 2) + 1(k + 2) = (k + 1) (k + 2) Logo P(k) ⇒ P(k + 1). Portanto pelo PIF vale ∀n ∈ IN. 2º] Demonstrar por indução que 𝟐^𝒏 maior que n para todos os inteiros positivos n. Caso base P(1): para n = 1, temos: 〖 2〗^1 = 2 e 1, Passo de indução: suponhamos que vale para algum n = k, k maior ou igual que 1, ou seja P(k): 〖 2〗^𝑘 maior que k Então para n = k + 1, temos: P(k + 1): 〖 2〗^(𝑘+1) Como por hipótese de indução: 〖 2〗^𝑘 maior que k, temos P(k + 1): 〖2•2〗^𝑘 maior que 2•k por transitividade 〖 2〗^(𝑘+1) maior que k + 1 Logo P(k) ⇒ P(k + 1). Portanto pelo PIF vale ∀n ∈ IN.