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 é 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 as 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! Já adianto que duas versões do PIF e vamos ver uma de cada vez.

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

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) para um determinado k , 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 P k trata-se de um somatório de termos até k e P k + 1 é o mesmo somatório só que até ( k + 1 ) . Podemos escrever a fórmula de P k + 1 assim,

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

Perceba que eu NÃO SUBSTITUÍ, eu simplesmente somei. Bom, agora só vamos ajeitar o lado direito:

P k + 1 = k k + 1 + 2 ( k + 1 ) 2

P k + 1 = ( k + 1 ) k + 2 2

OPAAAAA, chegamos aonde queríamos! Mostramos que somando k + 1 a P k , chegaremos ao mesmo valor que substituindo k + 1 na formula de P ( n ) . Ou seja, 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.

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

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

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.

O teorema diz o seguinte,

Note que o teorema me dá duas afirmações, então vamos usar dois passos para provar a igualdade acima.

Então primeiro vamos mostrar que P n 0 é verdadeira para um certo n 0 ∈ N . O n 0 é o nosso primeiro termo, no caso vamos escolher n 0 = 1 .

Lembrando que neste caso:

P n = n n + 1 2

Então

P 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 1 , tendo em vista que os naturais começam no 1 . A gente precisa conseguir alcançar cada número dessa soma através de ( 2 n - 1 ) .

Vou colocar aqui novamente o PIF, pra clarear sua mente e entranhar no seu sangue:

Lembrando que neste caso:

P n = n 2

Vamos ao caso base, escolhendo n 0 = 1 :

P 1 = 1

E isso é verdade.

Passo 4

Agora vamos atacar a segunda condição. Supondo que a relação seja válida para algum k , que é a nossa hipótese indutiva P ( k ) , temos:

1 + 3 + 5 + … + 2 k - 1 = k 2

Sabendo que P ( k ) é válida, queremos que P ( k + 1 ) também seja, isto é:

P k + 1 = k + 1 2

Agora vamos escrever todo somatório para P ( k + 1 ) . Mas antes repara que aqui estamos tratando apenas de números ímpares, então eles andam de 2 em 2 . Então quando eu adicionar mais um termo, eu terei que somar dois. Deste modo, o final do meu somatório ficaria assim,

2 k - 1 + 2 = 2 k + 1

Entendido isso, vamos escrever toda soma para P ( k + 1 ) . Repara como ficou meu último termo,

1 + 3 + 5 + … + 2 k - 1 + 2 k + 1 = k 2 + 2 k + 1

Ajeitando essa equação ficamos com,

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

E não é que k + 1 2 = k 2 + 2 k + 1 ? Tô chocadaaaa!!! Chegamos então ao que queríamos:

P k + 1 = k + 1 2

Resposta

Demonstração por PIF

Exercício Resolvido #2

Prove que:

2 n < n ! ,     n ≥ 4

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

OPAAA! Esse já mais quentinho que o exercício 1 , né? Hahaha Relaxa, que vamos esmiuçar bem direitinho.

Novamente, vou colocar o PIF pra clarear sua mente e entranhar no seu ser:

Lembrando que P n : 2 n < n ! ,     n ≥ 4 .

Vamos checar se isso é verdade, e comecemos pela primeira condição.

Adotando n 0 = 4 :

2 4 = 16

4 ! = 24

2 4 < 4 !

Ou seja, P ( 4 ) é verdadeira.

Passo 2

Olhemos agora para a segunda condição. Suponhamos que a relação é válida para algum k , que é a nossa hipótese indutiva P ( k ) , então queremos que seja válida também para k + 1 . Isto é, queremos encontrar:

2 k + 1 < k + 1 !

Bora tentar trabalhar na expressão que temos até agora:

2 k < k !

Multiplicando por 2 dos dois lados:

2.2 k < 2 k !

2 k + 1 < 2 k !

Opa, já temos uma parte da expressão que queremos, meu anjo!

Passo 3

Perceba o seguinte:

k + 1 ! = k + 1 k !

Concorda comigo?

“Ihhhh, você já começou a roubar... De onde você tirou esse k + 1 ! ???”

Anjo, esse termo aparece na expressão que a gente quer encontrar, então alguma hora a gente precisa trabalhar com ele, fazer algum tipo de rataria pra chegar onde queremos.

Continuando:

k + 1 > 2 ,     n ≥ 4

Concorda comigo nesse ponto também?

“Concordo, mas você tá doida!”

Não tô não, olha só como tudo vai fazer sentido agora:

k + 1 k ! > 2 k ! ,     n ≥ 4

E dá uma olhada novamente da expressão que tínhamos:

2 k + 1 < 2 k !

É justo dizer que:

2 k + 1 < 2 k ! < k + 1 k !

“Até tô vendo um pouco de sentido, mas não tô seguro se posso fazer isso!”

Passo 4

Tudo bem, vou tentar te convencer... Veja se você concorda com o seguinte:

2 < 3

Show, concorda também que:

7 > 3

Então não é errado eu dizer que:

2 < 3 < 7

E aí eu digo:

2 < 7

Foi isso que fizemos agora. Continuando para a glória:

2 k + 1 < k + 1 ! ,     n ≥ 4

Yuuuupi!!! (Isso é com Y?) Chegamos no P ( k + 1 ) e ela é verdadeira.

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

Deixe-me conversar uma coisa com você... Essas técnicas e ratarias nessas demonstrações, você pega depois de fazer alguns exercícios. Então, mesmo que você esteja achando que é o fim do mundo, acredite: não é. Continue tentando! Estou aqui pra ajudar você!

Resposta

Demonstração pelo PIF.

Exercício Resolvido #3

Numa certa criação de coelhos o número de coelhos a n após n meses obedece a seguinte regra:

a n = 3 a n - 1 - 2 a n - 2

Sabe-se também que a 1 = 3 e a 2 = 7 . Mostre que:

a n = 2 n + 1 - 1 ,     n ≥ 1

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Oláááá, caro estudante dedicado! Bora resolver esse exercício! Usaremos aqui o Princípio da Indução Finita (versão 2). Não lembra o que é? Toma aqui:

Lembrando que neste caso P n = 2 n + 1 - 1 .

Vamos começar a atacar a primeira condição, escolhendo n 0 = 1 como caso base:

a 1 = 3

P 1 = 2 1 + 1 - 1 = 3

Show, então P ( 1 ) é verdadeira. Mas não paramos por aí!

Como o nosso a n envolve os DOIS termos anteriores, precisamos que nossa hipótese de indução seja válida para dois “ n 0 ”. Para isto, vamos verificar se P ( 2 ) é verdadeira.

a 2 = 7

P 2 = 2 2 + 1 - 1 = 7

Maneiro! P ( 2 ) é verdadeira!

Passo 2

Vamos atacar a segunda condição. Supondo que seja válido para todo n 0 ≤ k < n , que é a nossa hipótese indutiva P ( k ) , queremos que seja válida para k + 1 também ( k + 1 pode estar tão próximo de n quanto se queira). Sendo que:

P k + 1 = 2 k + 2 - 1

Então, de alguma forma precisamos chegar aí. Vamos usar a relação:

a n = 3 a n - 1 - 2 a n - 2

Como queremos de k + 1 :

a k + 1 = 3 a k - 2 a k - 1

“Nossa, agora eu tô até feliz! ¬¬”

Caaaaalma, a gente sabe que foi válida até k , então também foi válida para k - 1 :

a k + 1 = 3 2 k + 1 - 1 - 2 2 k - 1

Agora nós vamos manipular os termos:

a k + 1 = 3.2 . 2 k - 3 - 2.2 k + 2

a k + 1 = 6.2 k - 2.2 k - 1

a k + 1 = 4.2 k - 1

a k + 1 = 2 k + 2 - 1

Como queríamos demonstrar, então P ( k + 1 ) é verdadeira.

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

Resposta

Demonstração por PIF versão 2 .

Exercício Resolvido #4

O que está errado na seguinte demonstração:

Proposição: com a ≠ 0 , a n - 1 = 1 , para todo n natural.

Demonstração: a 1 - 1 = 1 vale sempre.

Assumindo a k - 1 = 1 , temos a k = a k a k - 2 a k - 2 = a k - 1 a a k - 2 a k - 2 = a k - 1 a k - 1 a k - 2 = 1.1 1 = 1

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Cara, de cara a gente já sabe que essa proposição é doida! Anjo, a 2 é igual a a 2 , não igual a 1 , carambolas! (A não ser que a = 1 )

Bora começar a julgar essa argumentação! Primeira coisa a ser dita foi:

a 1 - 1 = 1     v a l e   s e m p r e

Isso é verdade! Então isso não é o erro.

Passo 2

A próxima coisa dita foi:

A s s u m i n d o   a k - 1 = 1

Opa! Isso não está correto! Perceba que o argumentador está usando (erroneamente) o PIF versão 1 . Se liga nele:

“Ah, mas ele provou que funciona para n 0 = 1

É verdade, mas veja a nossa hipótese indutiva, a SEGUNDA condição: tem que valer PARA TODO k ≥ n 0 . No nosso caso, o n 0 = 1 .

Então, tem que valer aquela P ( k ) , para todo k ≥ 1 .

E NÃO VALE!!! Perceba:

a 2 - 1 = a ≠ 1

Logo, o erro está na hipótese de indução.

Resposta

O erro está na hipótese de indução.

Exercício Resolvido #5

Seja a 0 = 1 e, para n > 0 , seja a n = 2 a n - 1 + 1 . Os primeiros termos da sequência a 0 ,   a 1 ,   a 2 ,   a 3 ,   … são 1 ,   3 ,   7 ,   15 ,   …

Quais são os próximos dois termos?

Prove que a n = 2 n + 1 - 1

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

FAAAAALA MEU AMOR!!! Bora começar do começo!

Para dizermos quais são os próximos dois termos, NÃO podemos usar a fórmula que foi dada! (Aí seria muito molezinha né meu anjo!)

Então, já temos todos os termos até o a 3 , vamos em busca dos outros:

a 4 = 2 a 3 + 1 = 2.15 + 1 = 31

a 5 = 2 a 4 + 1 = 2.31 + 1 = 63

Passo 2

Bora, fazer o segundo passo, que é provar que a fórmula é verdade! Vamos usar o PIF versão 1 :

Lembrando que no nosso caso, P n = 2 n + 1 - 1

Vamos atacar a primeira condição, onde chamarei n 0 = 0

a 0 = 1

P 0 = 2 0 + 1 - 1 = 1

Show! P ( 0 ) é verdadeira!!!

Passo 3

Vamos atacar a segunda condição. Usando a hipótese indutiva de que P ( k ) é válida, temos:

a k = 2 k + 1 - 1

Queremos que P ( k + 1 ) seja verdadeira, então vamos usar a outra relação:

a k + 1 = 2 a k + 1

Mas, como k obedece a fórmula, podemos substituir:

a k + 1 = 2 2 k + 1 - 1 + 1

a k + 1 = 2 k + 2 - 1

Olha que lindo!!! P ( k + 1 ) é verdadeira! Lembrando que:

P k + 1 = 2 k + 2 - 1

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

Resposta

a 4 = 31

a 5 = 63

Demonstração por PIF versão 1 .

Esse conteúdo é exclusivo para cadastrados.

Cadastre-se grátis no maior portal de exatas do Brasil!

Relaxa, não vamos publicar nada no seu nome.

  • Resumões direto ao ponto
    Resumões
    direto ao ponto
  • Exercícios resolvidos passo a passo
    Exercícios resolvidos
    passo a passo
  • Videoaulas incríveis
    Videoaulas
    incríveis
  • Aulões Salva-Vidas
    Aulões
    Salva-Vidas