Matemática para Ensino Superior indução

Prévia do material em texto

Indução Matemática 
 
O último axioma de Peano diz o seguinte: seja um subconjunto de . Se e se, além disso, 
contém todos os sucessores dos seus elementos, então . 
Este axioma é conhecido como axioma da indução e serve como base do método de demonstração por indução, o 
qual é de grande utilidade para estabelecer provas rigorosas em Matemática. 
O princípio da boa ordenação dos naturais e o axioma de indução não são independentes e sem nenhuma conexão. 
De fato, eles são equivalentes, ou seja, se considerarmos o princípio da boa ordenação como sendo um postulado podemos 
deduzir o axioma de indução e, reciprocamente, se considerarmos o princípio de indução como sendo um postulado podemos 
deduzir o princípio da boa ordenação. 
Assumiremos que representa uma afirmação em relação ao natural , podendo esta ser verdadeira ou falsa. 
 
Teorema 6.1 (Princípio da Indução Finita) Considere um inteiro não negativo. Suponhamos que, para cada inteiro , 
seja dada uma proposição . Suponha que se pode verificar as seguintes propriedades. 
a) é verdadeira; 
b) se é verdadeira então também é verdadeira, para todo . 
Então, é verdadeira para qualquer . 
 
A afirmação (a) é chamada de base da indução e a (b) de passo indutivo. O fato de que é verdadeira no item (b) 
é chamado de hipótese da indução. 
 
Demonstração 
Definamos o conjunto 
 
 
Notemos que é não vazio, pois a condição (a) nos assegura que . A prova do teorema é equivalente a mostrarmos 
que 
 
 
ou equivalente, a provarmos que o conjunto 
 
 
é vazio. Suponhamos que é não vazio. Pelo princípio da boa ordenação existe um menor elemento , onde é 
falso. Observemos que, 
 . De fato, , porém a possibilidade contradiz a condição (a); 
 . Com efeito, é verdadeira pois, caso contrário, e, além disso, , 
contradizendo isso a minimilidade de . 
 
Finalmente, como é verdadeira, segue da condição (b) que também é verdadeira, o que é impossível pela 
definição de . Portanto, o conjunto é vazio, concluindo-se assim a prova. 
 
Aplicações do P.I.F. na Demonstração de Identidades 
 
(P1) Determinar uma fórmula para a soma dos primeiros números pares, isto é, 
 
(P2) Determinar uma fórmula para a soma dos primeiros números ímpares, isto é, 
 
Para induzir ambas as fórmulas, primeiro fazendo os cálculos para vários valores de , os quais apresentaremos na seguinte 
tabela: 
 1 2 3 4 5 
 2 = 1.2 6 = 2.3 12 = 3.4 20 = 4.5 30 = 5.6 
 1 = 12 4 = 22 9 = 32 16 = 42 25 = 52 
 
Os resultados da tabela sugerem que e que . Provaremos estas fórmulas por indução. 
 
Exemplo 6.3: Demonstre que para qualquer é válida a igualdade 
 
 
Definamos a proposição 
 
 
e observemos que a mesma vale para (base da indução); de fato 
 
 
Agora partirmos para a prova do passo indutivo: 
 Hipótese: suponhamos que é verdadeira para um certo ; 
 Tese: devemos mostrar que também é verdadeira. 
Com efeito, como 
 
 
somando a ambos os lados desta igualdade, temos que 
 
 
 
Esta última igualdade afirma que também é verdadeira. O Princípio da Indução nos garante que é verdadeira 
para qualquer . 
 
Exemplo 6.4 Demonstre que para qualquer é válida a igualdade 
 
 
Aqui definimos a proposição 
 
 
e notamos que a mesma é válida se tomarmos, por exemplo, . De fato, 
 
 
Agora partirmos para a prova do passo indutivo: 
 Hipótese: suponhamos que é verdadeira para um certo ; 
 Tese: devemos mostrar que também é verdadeira. 
Com efeito, como 
 
 
 
somando a ambos os lados desta igualdade, temos que 
 
 
 
O princípio de indução nos garante que é verdadeira para qualquer . 
 
Uma conseqüência imediata do Exemplo 6.3 é a fórmula para a soma dos primeiros números naturais, dada por 
 
Com efeito, como 
 
 
então dividindo por 2 ambos os membros da igualdade acima, obtemos a equação desejada. 
 
Continuando com o mesmo raciocínio, é natural nos perguntarmos se é possível obter uma fórmula para a soma dos 
primeiros quadrados perfeitos, ou seja, determinar onde: 
 
 
Para deduzir a fórmula, consideramos os valores de e numa tabela: 
 1 2 3 4 5 6 
 1 3 6 10 15 21 
 1 5 14 30 55 91 
 
Aparentemente não existe nenhuma relação entre e . Mas, se considerarmos o quociente , vejamos o que 
acontece: 
 1 2 3 4 5 6 
 3 / 3 5 / 3 7 / 3 9 / 3 11 / 3 13 / 3 
 
Isso nos sugere que vale a relação 
 
 
Logo nosso candidato para o valor de é 
 
 
Aplicações do P.I.F. na Demonstração de Desigualdades 
 
Exemplo 6.5 Prove que para todo . 
Denotamos por a propriedade . 
É claro que é válida, pois 
 
 
Agora supondo que é verdadeira temos que 
 
logo também vale. Observamos que na desigualdade acima usamos o fato de que para qualquer 
. 
Exemplo 6.6 Mostre que para todo número , , vale que . 
Demonstração 
Para a desigualdade é verificada, pois . 
Vamos assumir como hipótese de indução que a desigualdade é válida para . 
Então, precisamos mostrar que a mesma vale também para . De fato, por hipótese de indução: 
 
 
Como , podemos multiplicar o lado esquerdo da desigualdade por e o lado direito por , sem alterar o sinal 
de desigualdade. Logo, temos que: 
 
 
concluindo-se a demonstração. 
 
Exemplo 6.7 Prove que, para todo , 
 
 
Demonstração 
Claramente a desigualdade vale para , pois . 
Suponhamos que para certo a desigualdade acontece, então: 
 
 
 
Logo, adicionando 2 em ambos os lados desta igualdade tem-se 
 
 
 
Tomando a raiz quadrada em ambos os lados desta última igualdade obtemos 
 
 
 
como desejávamos. 
 
 
 
 
 
Aplicações do P.I.F. em Problemas de Divisibilidade 
 
Exemplo 6.8 Mostre que para qualquer é sempre divisível por 3. 
 
Para a afirmação é válida, pois , que obviamente é divisível por 3. 
Assumamos como hipótese indutiva que a afirmação vale para algum , isto é, 
 
 
Devemos mostrar que a afirmação também é verdadeira para , ou seja, temos que provar que 
 
 
Para provar isto último, usamos o fato de que 
 
 
agrupando adequadamente, 
 
 
 
 
concluindo assim a prova. 
 
Exemplo 6.9 Mostre que a soma dos cubos de três números naturais consecutivos é divisível por 9. 
 
Definamos a seguinte proposição: 
 
 
Notemos que é válida, pois 
 
 
Precisamos provar agora o passo indutivo, isto é, 
 Hipótese: é verdadeira para algum ; 
 Tese: também é verdadeira. 
Para provar isto, observamos que 
 
 
Ordenando adequadamente, temos que o lado direito da última igualdade se escreve como 
 
 
 
completando assim nossa demonstração. 
 
Muitas vezes, para conseguir mostrar que a hipótese é verdadeira, precisamos supor que é verdadeira para 
todo . Isto é a base do princípio forte da indução finita. 
 
 
 
Teorema 6.10 (Princípio Forte da Indução Finita) Considere um inteiro não negativo. Suponhamos que, para cada inteiro 
 seja dada uma proposição e que valem as propriedades 
a) é verdadeira; 
b) se para cada inteiro não negativo , com , temos que é verdadeira, então é também 
verdadeira. 
Então, a proposição é verdadeira para qualquer . 
 
Exemplo 6.11 (Teorema Fundamental da Aritmética) Todo número natural maior que 1 pode ser escrito como um produto 
 
 
onde é um número natural e os são números primos. Além disso, a fatoração dada é única se 
exigirmos que . 
 
Aplicações do P.I.F. em Geometria 
 
Um polígono convexo é um polígono tal que qualquer segmento de reta que liga dois de seus pontos está contido no interior 
dele. No caso de polígonos, isto é equivalente ao fato de que todo segmento que liga dois vértices ou é uma aresta ou está 
contido no interior do polígono. 
 
Exemplo 6.12 Mostre que a soma dos ângulos internos de um polígono convexo de lados é igual a 
radianos. 
 
No caso a soma é conhecida e verdadeira.Façamos mais um caso, tomando . Neste caso, podemos dividir um 
quadrilátero em dois triângulos, assim, a soma dos ângulos internos de um quadrilátero será radianos. 
 
 
Vamos considerar mais um polígono, o pentágono . Neste caso, para mostrar que a soma dos ângulos internos é 
 radianos, iremos dividir o pentágono em um quadrilátero e um triângulo . 
Assim a soma dos ângulos internos do pentágono é igual à soma dos ângulos internos do triângulo 
(igual a radianos) mais a soma dos ângulos internos do quadrilátero (igual a radianos), ou seja, igual a 
radianos. 
Finalmente, vamos assumir como hipótese de indução que para um certo mostramos que a soma dos ângulos internos 
do é dada pela expressão radianos. Precisamos mostrar que a soma dos ângulos internos de um 
 é radianos. De fato, podemos repetir o processo anterior. Vamos denominar de 
 os vértices consecutivos do . Podemos dividi-lo no e no 
triângulo . Logo, a soma dos ângulos internos do é . 
 
 
 
 
 
Exemplo 6.13 Mostre que o número de diagonais de um polígono convexo de é igual a . 
Observe que para temos que existem 
 
diagonais num triângulo. Para , temos 
 
diagonais num quadrilátero convexo. 
 
 
Vamos agora assumir como hipótese de indução que se é um convexo então o seu número de diagonais é 
 e vamos provar que a fórmula vale para um convexo. De fato, denote por 
 os vértices consecutivos do .. Podemos decompô-lo como a união do 
 e do triângulo . Neste caso, para contarmos as diagonais do devemos considerar 
os seguintes casos: 
 diagonais do ; por hipótese de indução, o número dessas diagonais é ; 
 diagonais que partem do vértice mais a diagonal . 
 
Assim, o número total de diagonais do é: 
 
 
Indução e Recorrências 
 
Em geral, uma equação de recorrência é uma equação envolvendo uma certa quantidade de termos de sequência . 
 
Definição 6.19 Uma equação de recorrência linear de grau é uma expressão da forma 
 
 
onde são números reais e . 
 
Definimos a Sequência de Fibonacci como sendo a sequência que satisfaz a seguinte equação de recorrência 
 
 
Exemplo 6.21 Considere a sequência de Fibonacci. Mostre que 
 
Definamos a proposição 
 
 
Para temos que 
 
de modo que é verdadeira. Suponhamos que 
 
 
sejam todas verdadeiras. Mostraremos que . Com efeito, 
 
 
 
 
Como , segue-se que 
 
Portanto, 
 
 
 
Exemplo 6.22 Dada a seguinte relação de recorrência 
 
Mostre que , para todo 
 
Definamos a proposição . 
Verificamos que é verdadeira pois . 
Suponhamos que é verdadeiro para cada inteiro tal que .Vamos mostrar que é verdade para 
. Com efeito, 
 
 
 
 
 
 
 
 
 
Devemos fazer algumas observações sobre as equações de recorrência linear: 
 se e são soluções da equação , então também é solução; 
 se é solução da equação e é um número real, então também é solução. 
 
 
 
 
O polinômio 
 
recebe o nome especial de polinômio característico da equação de recorrência . Qualquer raiz do polinômio característico 
gera uma solução particular da equação 
 
Vamos assumir que a equação 
 
possui raízes diferentes, digamos . Então vale o seguinte teorema: 
 
Teorema 6.23 Se escolhemos números reais então 
 
 
é uma solução da equação de recorrência, onde os termos iniciais para são: