Indução Infinita

 Indução Infinita!

O método da indução finita é um procedimento matemático para provar propriedades que são verdadeiras para uma sequência de objetos. É um método bastante utilizado em teoria dos números,geometria, análise combinatória, etc.. Mas trata-se de um tipo de demonstração que pode aparecer em qualquer domínio da Matemática.

Exemplo 1 Os seguintes resultados podem ser provados por indução.

i) Dado n ∈ IN vale $2^n$ < n!, se n$\geq$ 4.

ii) O número de diagonais de um polígono de n lados é $\frac{n(n−3)}{2}$.

iii) Todo número natural maior ou igual a dois admite decomposição em fatores primos, única a menos da ordem dos fatores.

Observemos que os três resultados acima falam de propriedade associadas a números naturais e que são afirmadas valer a partir de algum natural inicial (4 no primeiro, 3 no segundo e 2 no terceiro exemplo). Generalizando, o método se aplica para a prova de afirmações que contém no seu enunciado

a descrição de alguma propriedade P (n) que é afirmada valer para todo natural n$\geq$ $n_0$ , onde $n_0$ é dado explicitamente ou fica evidente pelo contexto do enunciado.

Princípio da Indução Finita - 1ª Forma

Seja P(n) um enunciado que descreve uma propriedade sobre um número natural n maior ou igual a um número natural $n_0$ fixado.

Definição 2 (PIF 1ª forma) Se pudermos provar que valem as duas condições:

C1: P($n_0$) é verdadeira (ou seja, vale a propriedade para $n_0$);

C2: É verdadeira a implicação P(n) ! P(n + 1) para todo n $n_0$.

Então podemos afirmar que a propriedade P(n) é verdadeira para todo n $n_0$.

No uso prático, para provar um teorema por indução finita devemos assim mostrar que as duas condições do princípio acima estão satisfeitas. Isso nos garante a validade da propriedade para a infinidade de casos aos quais o teorema faça referência.

No caso da segunda condição, como uma implicação só é falsa se sua premissa for verdadeira e a

conclusão falsa, basta excluir essa possibilidade para termos a validade da implicação desejada. Assim o que normalmente se faz é tomar um k genérico qualquer maior ou igual a $n_0$ e admitindo que P(k) seja verdadeiro, mostrar que necessariamente P(k + 1) também deve ser verdadeiro. Feita também a prova de que vale a propriedade para o primeiro natural n0, o princípio da indução nos garante a validade da propriedade em todos os casos afirmados.

Exemplo 3 Como $2^4$ = 16 e 4! = 4*3*2*1 = 24, então vale que 24 < 4! e portanto (C1), a primeira

condição do PIF, está satisfeita.

Admitindo que $2^k$ = k!(*) para um k genérico maior do que 4, como

$2^{k+1}$ =2*$2^k$ (k + 1)! = (k + 1)k! (k + 1) > 2 , se k > 4

a partir da desigualdade (*) obtemos que

$2^{k+1}$= $2*2^k$ < 2*k! < (k + 1)*k! = (k + 1)!

Fica assim estabelecida a validade de (C2), a segunda condição do PIF.

Portanto o princípio da indução finita garante que vale $2^n$ < n!, para todo n $\geq$ 4

Princípio da Indução Finita - 2ª Forma

Seja P(n) um enunciado que descreve uma propriedade sobre um número natural n maior ou igual a

um número natural $n_0$ fixado.

Definição 4 (PIF 2a¯ forma) Se pudermos provar que valem as duas condições:

CC1: P($n_0$) é verdadeira (ou seja, vale a propriedade para $n_0$);

CC2: Para todo n $\geq$ $n_0$, é verdadeira a implicação

P($n_0$) ^ P($n_0$ + 1) ^ ::: ^ P(n - 1) ^ P(n) ! P(n + 1):

Então podemos afirmar que a propriedade P(n) é verdadeira para todo n $\geq$ $n_0$.

Na prática, para provar uma propriedade utilizando a segunda forma de indução, devemos provar

que a propriedade P vale para $n_0$ e a seguir, dado um n qualquer maior do que $n_0$ admitindo que a propriedade P vale para todos os números entre n0 e n (inclusive), devemos provar que P também vale para n + 1. Ou ainda, devemos comprovar a seguinte implicação:

P(k) verdadeira para $n_0$ $\leq$ k $\leq$ n ! P(n) verdadeira:

Essa segunda forma pode ser necessária algumas vezes, como por exemplo no Teorema Fundamental

da Aritmética enunciado no item (iii) do primeiro exemplo e cuja existência da decomposição provaremos a seguir (só provaremos a existência neste texto, a unicidade a menos de ordem dos fatores não será feita aqui).

Exemplo 5 O primeiro número é o 2, que é primo. Como 2 = 2, podemos dizer que 2 admite uma

"fatoração"/ única em primos. E portanto (CC1) está satisfeita.

Admitamos que todos os números entre 2 e n, incluindo 2 e n, admitem uma fatoração em números

primos, única a menos da ordem dos fatores. Consideremos o número n + 1. Existem duas possibilidades: a) n+1 é primo, e nesse caso a sua "fatoração" é evidentemente única contendo como único "fator" o próprio primo n + 1, como no caso do número 2.

b) n + 1 é composto, por exemplo, n + 1 = p:q, onde p e q são números naturais menores do que n e maiores ou iguais a 2. Assim, por suposição (logo acima), também chamada de hipótese de indução, tanto p como q admitem decomposição em fatores primos. Multiplicando todos os fatores de p pelos fatores de q evidentemente obtemos o número n + 1.

Como as fatorações de p e q são únicas a menos da ordem dos fatores, deve-se ainda provar que, se houvesse outros primos que fatorassem n+1, distintos da fatoração já encontrada, obteríamos também

fatorações distintas para p e q, o que não é possível por hipótese. (Essa parte é mais técnica e não faremos aqui, fica como desafio para quem se interessar. Vocês verão a prova completa na disciplina

Álgebra I.)

Estamos editando!!

 Aguardem