Exercícios Resolvidos de Princípio da Indução Finita

Ver Teoria

Enunciado

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