Como provar pelo principio da indução matemática que
n A = para n 1.
Lista de comentários
joaorockIndução matemática é um método de prova de matematica usado para demonstrar a verdade de um número infinito de proposições. A forma mais simples e mais comum de indução matemática prova que um enunciado vale para todos os números naturais n e consiste de dois passos:A base: mostrar que o enunciado vale para n = 1.O passo indutivo: mostrar que, se o enunciado vale para n=k, então o mesmo enunciado vale para n=k+1.Esse método funciona provando que o enunciado é verdadeiro para um valor inicial, e então provando que o processo usado para ir de um valor para o próximo é valido. Se ambas as coisas são provadas, então qualquer valor pode ser obtido através da repetição desse processo. Para entender por que os dois passos são suficientes, é útil pensar no efeito domino: se você tem uma longa fila de dominós em pé e você puder assegurar que:O primeiro dominó cairá.Sempre que um dominó cair, seu próximo vizinho também cairá.então você pode concluir que todos os dominós cairão. Nas ciências naturais, utiliza-se a indução emprírica. Ou seja, a partir de um grande número de observações particulares selecionadas adequadamente, formula-se leis que devem reger determinados fenômenos. A validade de um teorema matemático, no entanto, se estabelece de forma completamente diferente. Verificar que certa afirmação vale para um grande número de casos particulares (como se faz nas ciências naturais) não permitirá concluir que esta afirmação é válida. O princípio da indução completa (ou método da recorrência), é utilizado para provar que a proposição vale para todos os casos (ou seja, na verdade há uma proposição para cada caso, freqüentemente um número infinito de casos).ex:Suponha que desejemos provar o seguinte enunciado:para todos os números naturais n. Esta é uma fórmula simples para a soma dos números naturais de 1 a n. A prova de que o enunciado é verdadeiro para todos os números naturais n é dada a seguir.Verificação o primeiro passo consiste em determinar a base da prova por indução. Neste caso, tomaremos como base n = 1. Claramente, do lado esquerdo da equação fica 1 e do lado direito 1(1 + 1) / 2, resolvendo dá 1=1. Então o enunciado é verdadeiro para n = 1.Agora precisamos provar que o enunciado vale para n = k.Por hipótese de indução, a equação vale para n = k-1, ou seja:Adicionando k a ambos os lados, a igualdade se mantém, então:Por manipulação algébrica, temos:Logo:Este último é o enunciado para n = k. Note que, assumindo que P(K - 1) é verdadeiro, podemos concluir que P(K) é verdadeiro. Simbolicamente, mostramos que:Por indução, no entanto, podemos concluir que o enunciado P(n) vale para todos os números naturais n:Primeiro provamos que a base de indução (n=1, neste caso) é verdadeira;Depois, por hipótese de indução temos que P(k-1) é verdadeiro, então precisamos provar que P(k) também é verdadeiro.Provando que o passo da indução está correto, concluimos que P(n) é verdadeiro para qualquer número n natural.Comece em b este tipo de prova pode ser generalizada de várias maneiras. Por exemplo, se quisermos provar um enunciado, não para todos os números naturais, mas apenas para todos os números maiores que ou iguais a um determinado número b, então os seguintes passos são suficientes:Mostrar que o enunciado vale quando n = b.Mostrar que se o enunciado vale para n = k ≥ b, então o mesmo enunciado também vale para n = k + 1.Isto pode ser usado, por exemplo, para mostrar que n² > 2n para n ≥ 3. Esta forma de indução matemática é na verdade um caso especial da forma anterior, porque se o enunciado que pretendemos provar é P(n), então prová-lo com estas duas regras é equivalente a provar P(n + b) para todos os números naturais n com os dois primeiros passos.Assumir verdadeiro para todos os valores menores outra generalização, chamada, permite que no segundo passo nós não apenas assumamos que o enunciado vale para n = k, mas também para todo n menor que ou igual a k.Nesta forma de indução, talvez supreendentemente, não é necessário provar que a proposição é verdadeira no primeiro caso. Isto se dá porque a proposição vale para todos os casos antes do primeiro caso, simplesmente porque não há casos antes do primeiro.Isto pode ser usado, por exemplo, para mostrar que
Lista de comentários
Nas ciências naturais, utiliza-se a indução emprírica. Ou seja, a partir de um grande número de observações particulares selecionadas adequadamente, formula-se leis que devem reger determinados fenômenos. A validade de um teorema matemático, no entanto, se estabelece de forma completamente diferente. Verificar que certa afirmação vale para um grande número de casos particulares (como se faz nas ciências naturais) não permitirá concluir que esta afirmação é válida. O princípio da indução completa (ou método da recorrência), é utilizado para provar que a proposição vale para todos os casos (ou seja, na verdade há uma proposição para cada caso, freqüentemente um número infinito de casos).ex:Suponha que desejemos provar o seguinte enunciado:para todos os números naturais n. Esta é uma fórmula simples para a soma dos números naturais de 1 a n. A prova de que o enunciado é verdadeiro para todos os números naturais n é dada a seguir.Verificação o primeiro passo consiste em determinar a base da prova por indução. Neste caso, tomaremos como base n = 1. Claramente, do lado esquerdo da equação fica 1 e do lado direito 1(1 + 1) / 2, resolvendo dá 1=1. Então o enunciado é verdadeiro para n = 1.Agora precisamos provar que o enunciado vale para n = k.Por hipótese de indução, a equação vale para n = k-1, ou seja:Adicionando k a ambos os lados, a igualdade se mantém, então:Por manipulação algébrica, temos:Logo:Este último é o enunciado para n = k. Note que, assumindo que P(K - 1) é verdadeiro, podemos concluir que P(K) é verdadeiro. Simbolicamente, mostramos que:Por indução, no entanto, podemos concluir que o enunciado P(n) vale para todos os números naturais n:Primeiro provamos que a base de indução (n=1, neste caso) é verdadeira;Depois, por hipótese de indução temos que P(k-1) é verdadeiro, então precisamos provar que P(k) também é verdadeiro.Provando que o passo da indução está correto, concluimos que P(n) é verdadeiro para qualquer número n natural.Comece em b este tipo de prova pode ser generalizada de várias maneiras. Por exemplo, se quisermos provar um enunciado, não para todos os números naturais, mas apenas para todos os números maiores que ou iguais a um determinado número b, então os seguintes passos são suficientes:Mostrar que o enunciado vale quando n = b.Mostrar que se o enunciado vale para n = k ≥ b, então o mesmo enunciado também vale para n = k + 1.Isto pode ser usado, por exemplo, para mostrar que n² > 2n para n ≥ 3. Esta forma de indução matemática é na verdade um caso especial da forma anterior, porque se o enunciado que pretendemos provar é P(n), então prová-lo com estas duas regras é equivalente a provar P(n + b) para todos os números naturais n com os dois primeiros passos.Assumir verdadeiro para todos os valores menores outra generalização, chamada, permite que no segundo passo nós não apenas assumamos que o enunciado vale para n = k, mas também para todo n menor que ou igual a k.Nesta forma de indução, talvez supreendentemente, não é necessário provar que a proposição é verdadeira no primeiro caso. Isto se dá porque a proposição vale para todos os casos antes do primeiro caso, simplesmente porque não há casos antes do primeiro.Isto pode ser usado, por exemplo, para mostrar que