Responde Aí
Acesse com GoogleAcesse com AppleAcesse com Facebook

Indução Finita: Princípio

Ver Todos os Exercícios

Teoria

Fala aí! Hoje vamos trocar uma ideia sobre o Princípio da Indução Finita, ou PIF (mas esse é só para os íntimos ☺️). Ele vai nos fornecer um método muito útil para provar que uma propriedade é verdadeira para um número infinito de proposições.

Quer ver como? Vem comigo!

⭐ Veja também ⭐

O que é o Princípio da Indução Finita?

Por meio do principio da indução finita, nós conseguimos pegar uma propriedade que sabemos ser verdadeira para um certo número de finito, e generalizá-la para todos os outros números.

Não entendeu?

Seguinte: imagine que você seja um aluno curioso estudando progressões aritméticas. Não satisfeito quando seu professor simplesmente mandou você copiar a fórmula, você quer provar que a soma dos primeiros números naturais é dada por:

Você pega o lápis e papel e começa a testar:

Para o 1, dá certo.

Para o 2, dá certo.

Para o 3, dá certo.

Para o 54, também dá certo…

E agora? Você só precisa que dê errado uma vez para a afirmação ser falsa. Pode ser que quando chegar lá no 23.847 não dê mais certo, mas vai ficar testando o mês inteiro?

É claro que não! Você vai usar o tal do PIF pra provar que isso sempre funciona!

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

A gente vai dividir o coitado em duas formas. A primeira delas é definida assim:

Seja P(n) uma propriedade genérica que satisfaz as seguintes condições:

  • P() é verdadeira para um certo ;
  • Para todo k , com k , tem-se: se P(k) é verdadeira, então P(k+1) é verdadeira.

Então, P(n) é verdadeira para todo n .

Esse aí é o chamado Princípio da Indução Fraca.

Se aquelas duas condições ali do meio forem satisfeitas, nossa proposição está provada para a infinidade de termos que existem.

Se liga no exemplo 👇

Exemplo: Use o PIF 1 para provar a soma dos primeiros n termos naturais.

Passo 1: Quem é ?

Beleza, o primeiro passo é sempre saber quem é , ou seja, a proposição que a gente quer provar.

Aqui, a gente quer provar aquela fórmula que eu tinha mencionado na historinha:

Passo 2: Provar a primeira condição.

Depois, a gente vai olhar para cada condição.

Começando pela primeira, a gente deve pegar um número qualquer para o qual a proposição seja satisfeita. A ideia é sempre pegar o número mais básico possível, geralmente o ou .

Então, temos que provar que a soma dos primeiros termos naturais, com , vale .

Beleza! A primeira condição tá provada.

Passo 3: Hipótese indutiva.

Esse passo aqui é muuuuito importante, fica esperto!

A hipótese indutiva nada mais é que usar a segunda condição do PIF.

Vamos assumir que a relação seja válida para algum maior que o . Então, a gente tem que provar que é verdadeira.

A nossa hipótese indutiva é:

E queremos provar que é verdadeira.

Lembra que esse é o somatório dos termos naturais até ? Então, vamos reescrever isso aí assim:

Só escrevi a soma dos k primeiros termos ali e adicionei o próximo termo , chegando à soma dos primeiros termos. Tranquilo?

Agora, vamos organizar isso aí:

Tira o MMC:

Coloca o em evidência:

Maravilha! A gente acabou de mostrar que somando a , chegaremos ao mesmo valor que substituindo na fórmula de .

é verdadeira e, portanto, pelo PIF 1, nossa proposição original é verdadeira!

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

A definição que vamos usar é essa aqui:

Seja P(n) uma propriedade genérica que satisfaz as seguintes condições:

  • P() é verdadeira para um certo ;
  • Para todo n , com n , tem-se: se P(k) é verdadeira para todo k , com $n_0\leq k , então P(n) é verdadeira.

Então, P(n) é verdadeira para todo n .

Esse PIF é bem parecido com o outro, né? Mas ele tem uma aplicação diferente e bem mais forte, tanto que ele é chamado por Princípio da Indução Forte.

Se liga no exemplo 👇

Exemplo: Mostre que todo natural é um número primo ou é um produto de primos.

Passo 1: Quem é ?

é primo ou produto de primos.

Mas olha só: isso aí não é verdade para o número 1.

Sem problemas, começamos pelo 2, então. Nossa proposição passa a ser verdadeira para todo n > 1.

é primo ou produto de primos, .

Passo 2: Provar a primeira condição.

Precisamos provar que a proposição é verdadeira para o nosso escolhido no passo anterior.

O natural 2 é um número primo, ou produto de primos?

Sim, 2 é primo, então é verdadeira.

Passo 3: Hipótese de Indução.

Se a gente tentar usar o PIF 1, teríamos o seguinte:

k é primo ou produto de primos.

E aí, como a gente prova que também obedece a isso? Complicado, né?

Agora, saca só como fica pelo PIF 2:

Pela hipótese indutiva, a gente afirma que:

$$n_0\leq k
$$2\leq k

Para todo k nesse intervalo, é verdadeira. Então, só falta saber se é verdadeira.

Temos duas possibilidades para o : ou ele é primo ou não é. Se ele for primo, pronto, é verdadeira. Se não, ele pode ser escrito da seguinte forma:

Esse é um primo que divide . Já que não é primo, ele tem que ser divisível por algum primo, não é?

Aí, repara só no seguinte: da hipótese indutiva, $k1$.

Com esses dois argumentos, podemos usar a hipótese indutiva e afirmar que é primo ou produto de primos. (Afirmamos que isso era verdade para todo $2\leq k

Logo, está escrito com um produto de primos (). é verdadeira pelo PIF 2.

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

Exemplo: Use o PIF 1 para provar a soma dos primeiros n termos naturais.

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

Exemplo: Mostre que todo natural é um número primo ou é um produto de primos.

Exercícios Resolvidos

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

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

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

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

∎

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

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 .