Princípio da Indução Finita

Teoria Completa

FAAAAALA AÍ, meu anjo! Tudo bem com você?

Vou começar essa teoria com a seguinte situação: Imagine que você está numa fila da padaria, tem muitas pessoas MESMO na fila, tanto que você não sabe de cabeça a quantidade e, por isso, chamaremos essa quantidade de n .

Show, aí você está lá de boa esperando seu pão e, do nada, aparece um funcionário e ele começa a distribuir presunto desde a primeira pessoa da fila.

Aí você fica mega feliz né? (faz de conta, anjinho) “Vou ganhar presunto também, todos na minha frente estão ganhando!”

Meu anjo, PARABÉNS! Você acabou de usar o pensamento indutivo! Aqui, nós vamos trabalhar o Princípio da Indução Finita (que carinhosamente chamaremos de PIF), que é justamente a ferramenta matemática de PROVAR esse seu pensamento. Maneiro, né?

“Oi? Eu não fiz nada disso! Só pensei assim porque todos estavam ganhando, então eu também ganharia.”

Mas isso é um pensamento indutivo e é um pensamento perfeito!

“Mas pra quê serve esse PIF?”

O que acontece, queridx alunx, é que em várias Ciências apareciam situações que pareciam seguir um padrão. Mas o problema era o seguinte: os estudiosos podiam testar números o quanto quisessem, mas isso não seria o suficiente pra provar que o padrão existia.

Por exemplo: Você já deve ter visto como é a soma de n termos de uma P.A. de razão 1 :

1 + 2 + 3 + … + n = n n + 1 2

Tudo bem, hoje sabemos que essa igualdade é verdadeira, MAS matematicamente teríamos que provar. Sei lá, essa conta poderia dar certo pra 10000 e não dar certo para 10001 (e convenhamos que ninguém tem paciência de testar até esse número), entende? Por isso, usamos o PIF, para provar que isso é certo sempre!

Os sábios sabiam que para responder às questões colocadas pelos problemas, não bastava “testar” se as fórmulas eram verdadeiras apenas substituindo valores específicos para n . Por mais que tivessem testado para muitos valores, podia haver algum que não foi testado. Existe um abismo entre algo ser “provavelmente verdadeira” e “absolutamente certa”.

Bom, chega de blá-blá-blá e vamos para o PIF!

Princípio de Indução Finita (1ª versão)

Então temos aqui duas condições que devem ser satisfeitas! Prová-las nos garante a validade da proposição para a infinidade de termos que existem.

Exemplo:

U s e   o   P I F   1   p a r a   m o s t r a r   q u e   1 + 2 + 3 + … + n = n n + 1 2

Bom, vou te mostrar o passo a passo para resolver esse tipo de questão!

Passo 1:

O primeiro passo SEMPRE é você saber quem é P ( n ) , no seu caso.

P n = n n + 1 2

Ou seja, o que queremos provar aqui é que aquela soma é sempre igual a n n + 1 2

Passo 2:

O segundo passo é começar a atacar as duas condições, iniciando pela primeira.

O que a gente faz aqui é pegar um número n 0 tal que P ( n 0 ) seja verdadeira. Esse vai ser o seu caso base, sabe? Aquele que te resguarda no mais básico dos casos.

n 0 = 1

Agora, temos que verificar qual a soma de 1 termo na P.A. de razão 1 . Ora, é o próprio 1 , concorda? E depois de encontrarmos esse valor, calculamos o P ( 1 ) :

P 1 = 1 1 + 1 2 = 1

Opa! Então P ( 1 ) é verdadeira.

Passo 3:

Bom, todos os passos são importantes, mas esse aqui especificamente, é MEGA importante e requer toda a sua atenção!

Vamos usar a HIPÓTESE INDUTIVA!

“ahn? O que é isso?”

A hipótese indutiva nada mais é que você usar a segunda condição do PIF. Vamos assumir que essa relação P ( n ) é válida para algum k que seja maior que o n 0 = 1 , e então tentaremos provar que P ( k + 1 ) é verdadeira.

Então, estamos usando a HI (hipótese indutiva ou de indução), dizendo que:

P k = k k + 1 2

E queremos provar que P ( k + 1 ) é verdadeira. Dá uma olhada onde queremos chegar:

P k + 1 = k + 1 k + 2 2

Como fazemos isso? Olha isso:

1 + 2 + 3 + … + n = n n + 1 2

Sabemos que essa relação é válida para k , então:

1 + 2 + 3 + … + k = k k + 1 2

Agora queremos chegar em k + 1 , então somamos k + 1 nos dois lados:

1 + 2 + 3 + … + k + k + 1 = k k + 1 2 + k + 1

Perceba que eu NÃO SUBSTITUÍ, eu simplesmente somei. Bom, o lado esquerdo a gente não mexe, pois ele já tem o que precisamos, que é a soma até ( k + 1 ) , vamos então ajeitar o lado direito:

1 + 2 + 3 + … + k + ( k + 1 ) = k k + 1 + 2 ( k + 1 ) 2

1 + 2 + 3 + … + k + ( k + 1 ) = ( k + 1 ) k + 2 2

OPAAAAA, chegamos aonde queríamos! P ( k + 1 ) é verdadeira. Então, pelo Princípio da Indução Finita versão 1 (ou também chamado de Princípio da Indução Fraca), P ( n ) é verdadeira.

Não se assuste, esse passo não costuma ser tão grande, mas eu quis esmiuçar bem para você entender direitinho.

Princípio de Indução Finita (2ª versão)

Bom, esse PIF parece com o outro, mas tem uma aplicação bem diferente e bem mais forte, tanto é que esse é chamado de Princípio da Indução Finita versão 2 ou Princípio da Indução Forte.

Olha o exemplo:

M o s t r e   q u e   t o d o   n a t u r a l   é   u m   n ú m e r o   p r i m o   o u   é   u m   p r o d u t o   d e   p r i m o s .

Passo 1:

P n = n   é   p r i m o   o u   p r o d u t o   d e   p r i m o s

“Ah, isso não é verdade para o número 1

Ok, então pegaremos o número 2 . O importante no caso base, é que ele seja uma base para todos os outros casos maiores que ele. Então provaremos que essa proposição é verdadeira para todo n > 1 .

P n = n   é   p r i m o   o u   p r o d u t o   d e   p r i m o s ,     n > 1

Pronto, identificamos nossa proposição, aquilo que queremos provar.

Passo 2:

Bom, o primeiro passo das duas versões é igual, ou seja, precisamos de um caso base que seja verdadeiro.

2   é   p r i m o ,   e n t ã o   P 2   é   v e r d a d e i r a .

Temos um caso base.

Passo 3:

Agora é a hora de usarmos a HIPÓTESE DE INDUÇÃO, vamos aplicar a segunda condição.

Se a gente tentar usar o PIF 1, não chegaremos a lugar algum, usando que P ( k ) é verdadeira:

k   é   p r i m o   o u   p r o d u t o   d e   p r i m o s

Ok, e agora? Como eu faço pra provar que k + 1 também obedece a isso? É muito mais complicado. Então usaremos o PIF 2 e olha como ficará mais fácil.

Vou usar a hipótese indutiva, afirmando que:

n 0 ≤ k < n

2 ≤ k < n

Para todo k nesse intervalo, P ( k ) é verdadeira. Lembrando que tem que ser mesmo, na verdade estamos afirmando que:

P 2 ∧ P 3 ∧ P 4 ∧ P 5 ∧ … ∧ P n - 1   é   v e r d a d e i r a

Então o que nos resta provar é se P ( n ) é verdadeira.

Para o caso n , temos duas possibilidades: ou ele é primo ou não é. Se ele for primo, pronto, P ( n ) é verdadeira. Mas se ele não for, ele pode ser escrito da seguinte forma:

n = p . k

Onde esse p é um primo que divide n , já que se n não é primo, ele tem que ser divisível por algum primo.

Agora temos que ter em mente o seguinte: n ≠ p , então k > 1 .

Além disso, p > 1 , já que ele é um primo, então k < n .

Logo, tendo essas duas argumentações, podemos usar a hipótese indutiva afirmando que k   é   p r i m o   o u   p r o d u t o   d e   p r i m o s . (Afirmamos que isso era verdade para todo 2 ≤ k < n )

Logo, n está sendo escrito como um produto de primos, ou seja, P ( n ) é verdadeira pelo PIF 2 e a propriedade P vale para qualquer n > 1 .

Bora pros exercícios, meu anjo!

Expandir

Exercício Resolvido #1

Usando o Princípio da Indução Finita, prove que:

a   1 + 2 + 3 + … + n = n n + 1 2

b   A   s o m a   d o s   n   p r i m e i r o s   n ú m e r o s   í m p a r e s   é   n 2

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Mas você tá muito dedicado! Vou te contar, hein! Continue assim :D

Bom, aqui nem tem muito pra onde correr, o enunciado já diz para usarmos o PIF, então vamos à luta!

a   1 + 2 + 3 + … + n = n n + 1 2

Para provarmos que isso é verdade, precisamos de um caso base que seja verdadeiro.

Mas antes, vou enunciar o teorema pra você lembrar!

Lembrando que neste caso:

P n = n n + 1 2

Bom, vamos atacar a primeira condição. Escolherei n 0 = 1 :

1 1 + 1 2 = 1

Então P ( 1 ) é verdadeira.

Passo 2

Vamos agora atacar a segunda condição. Assumindo que a relação seja válida para algum k , essa é a nossa hipótese indutiva P ( k ) :

1 + 2 + 3 + … + k = k k + 1 2

Queremos encontrar:

P k + 1 = k + 1 k + 2 2

Verificaremos se a relação anterior é válida para P ( k + 1 ) :

1 + 2 + 3 + … + k + k + 1 = k k + 1 2 + k + 1

1 + 2 + 3 + … + k + k + 1 = k k + 1 + 2 ( k + 1 ) 2

Finalmente:

1 + 2 + 3 + … + k + k + 1 = ( k + 1 ) k + 2 2

Então P ( k + 1 ) é verdadeira.

Portanto, P ( n ) é verdadeira para todo n ≥ n 0 .

Passo 3

Se liga nessa próxima:

b   A   s o m a   d o s   n   p r i m e i r o s   n ú m e r o s   í m p a r e s   é   n 2

Traduzindo isso para números:

1 + 3 + 5 + 7 + … + 2 n - 1 = n 2

“Ah, por que você colocou ( 2 n - 1 ) e não ( 2 n + 1 ) ?”

Porque se a gente colocar ( 2 n + 1 ) , você não consegue chegar no número