Complementos sobre PIM

Prévia do material em texto

Fundac¸a˜o Centro de Cieˆncias e Educac¸a˜o Superior a Distaˆncia do Estado do Rio de Janeiro
Centro de Educac¸a˜o Superior a Distaˆncia do Estado do Rio de Janeiro
Complementos sobre Princ´ıpio de Induc¸a˜o Matema´tica H. Clark & C. Vinagre
O objetivo destes Complementos e´ apresentar alguns erros comuns cometidos na demonstrac¸a˜o de
afirmac¸o˜es por meio do Princ´ıpio de Induc¸a˜o Matema´tica - PIM.
Primeiramente, um problema sera´ apresentado e sua demonstrac¸a˜o correta sera´ apresentada. A
seguir, apontam-se os equ´ıvocos mais comuns que aparecem na resoluc¸a˜o, usando o mesmo problema
como exemplo.
Problema: Mostrar que a soma dos n primeiros nu´meros naturais ı´mpares e´ igual a n2. Ou seja,
mostrar que
1 + 3 + 5 + · · ·+ 2n− 1 = n2 para todo n ∈ N.
Prova: A propriedade P[n] e´ p1 + 3 + 5 + · · ·+ 2n− 1 = n2q.
Etapa 1: Como 2.1− 1 = 1 = 12 enta˜o P[1] e´ verdadeira.
Etapa 2: Hipo´tese de Induc¸a˜o - HI: Seja k ∈ N e suponha que P[k] e´ verdadeira, ou seja, que
1 + 3 + 5 + · · ·+ 2k − 1 = k2.
Desenvolvimento: Como e´ preciso mostrar uma igualdade, desenvolve-se um dos lados para chegar
ao outro, como segue:
1 + 3 + 5 + · · ·+ 2k − 1 + (2(k + 1)− 1) = k2 + (2(k + 1)− 1)
= k2 + 2k + 1
= (k + 1)2.
Ou seja, P[k+1] e´ uma propriedade verdadeira. Assim provou-se que: para todo k ∈ N, se P[k] e´
verdadeira enta˜o P[k+1] e´ verdadeira.
Pelas duas etapas acima e pelo PIM a afirmac¸a˜o 1 + 3 + 5 + · · · + 2n − 1 = n2 e´ verdadeira para
todo n ∈ N, como se queria.
Erros comuns:
1. Partir da conclusa˜o, desenvolvendo-a. Na segunda etapa, deve-se supor que vale P[k] para
um natural qualquer fixado e, a partir da´ı, prova-se que vale P[k+1]. Um erro muito comum e´ fazer
o desenvolvimento da segunda etapa da seguinte forma:
Desenvolvimento errado:
1 + 3 + 5 + · · ·+ 2k − 1 + (2(k + 1)− 1) = (k + 1)2
∴ k2 + (2(k + 1)− 1) = k2 + 2k + 1
∴ k2 + 2k + 1 = k2 + 2k + 1 .
O desenvolvimento acima comec¸a afirmando P[k+1] - que e´ a conclusa˜o - e usa P[k] para chegar a
uma identidade. Este procedimento na˜o prova nada e esta´ totalmente errado. Jamais se prova uma
igualdade desenvolvendo-se os seus dois lados, pois isto e´ afirmar a conclusa˜o. E jamais se pode afirmar
numa prova a conclusa˜o a que se deve chegar. Na˜o faz sentido!
1
2. Assumir que “vale tudo” na hipo´tese indutiva. Na segunda etapa de uma prova de induc¸a˜o,
supo˜e-se que P[k] e´ verdadeira para um natural arbitrariamente fixado e, a partir da´ı, prova-se que
vale P[k+1]. Um erro muito comum e´ assumir na hipo´tese de induc¸a˜o que P[k] e´ verdadeira para todo
k ∈ N.
Etapa 2 (hipo´tese indutiva errada): Suponha que P[k] e´ verdade para todo k ∈ N.
Procedimento totalmente errado, mostrando que o autor que na˜o entendeu a prova por induc¸a˜o.
A conclusa˜o final, o que se deseja provar usando o PIM e´ que vale P[n] para todo natural n, o que e´
o mesmo que afirmar que vale P[k] para todo natural k. Portanto, escrever a hipo´tese indutiva como
acima tira todo o sentido da prova. Se voceˆ escreveu assim alguma vez, volte ao enunciado do PIM
para entendeˆ-lo realmente.
Etapa 2 (forma correta): Suponha que P[k] e´ verdadeira para algum k ∈ N. (veja tambe´m o in´ıcio
do texto!)
3. Assumir na HI o enunciado que se quer provar. Outro erro comum e´ assumir na hipo´tese
de induc¸a˜o que: se P[k] e´ verdadeira para algum k ∈ N enta˜o P[k] e´ verdadeira.
Etapa 2: (hipo´tese indutiva errada): Suponha que se P[k] e´ verdade para algum k ∈ N enta˜o
P[k+1] e´ verdadeira.
Claramente, esta formulac¸a˜o da HI na˜o faz sentido: a segunda etapa numa prova por induc¸a˜o
requer que se assuma P[k] para algum k ∈ N e, a partir da´ı, prove-se P[k+1]. Reveja a forma correta
no in´ıcio do texto ou no item anterior.
E´ preciso entender que a linguagem matema´tica e´ um encadeamento de s´ımbolos e palavras que
teˆm um sentido muito preciso e que na˜o se pode escrever matema´tica de uma forma negligente; e´
preciso estudar para entender o que e´ preciso fazer. Se voceˆ ainda tem esta du´vida, volte ao enunciado
do PIM para resolveˆ-la.
4. Na˜o entender o significado da propriedade P[n] e/ou a sua descric¸a˜o.
No exemplo dado inicialmente, a propriedade P[n] e´ p1 + 3 + 5 + · · ·+ 2n− 1 = n2q e n varia
em N. Isto significa que:
P[1] e´ p2.1− 1 = 1 = 12q;
P[2] e´ p(2.1− 1) + (2.2− 1) = 1 + 3 = 22q;
P[3] e´ p(2.1− 1) + (2.2− 1) + (2.3− 1) = 1 + 3 + 5 = 32q ;
...
P[k] e´ p1 + 3 + 5 + · · ·+ 2k − 1 = k2q;
P[k+1] e´ p1 + 3 + 5 + · · ·+ (2k − 1) + (2(k + 1)− 1) = (k + 1)2q.
Um erro que ocorre a`s vezes e´, tendo escrito corretamente a hipo´tese indutiva, o aluno escrever
que a propriedade P[k+1] a ser provada tem a forma:
P[k+1] e´ p1 + 3 + 5 + · · ·+ 2(k + 1)− 1 = (k + 1)2q.
Etapa 2: Hipo´tese de induc¸a˜o: Seja k ∈ N tal que vale 1 + 3 + 5 + · · ·+ 2k − 1 = k2. Ou seja, tal que
P[k] e´ verdade.
Desenvolvimento errado:
1 + 3 + 5 + · · ·+ (2(k + 1)− 1) =???
Na˜o ha´ como usar P[k] desta maneira e a conta na˜o pode ser feita (reveja o exemplo corretamente
escrito no in´ıcio do texto).
2
5. Escrever de menos, fazendo crer que a prova pelo PIM consiste somente da segunda
etapa. Um erro que tambe´m ocorre e´ o aluno provar corretamente a primeira e a segunda etapas, e
terminar, como se a conclusa˜o final fosse P[k+1]; neste caso, o estudante na˜o considera que a conclusa˜o
pelo PIM depende das duas etapas e que e´ uma afirmac¸a˜o mais geral, demonstrando que ainda precisa
estudar melhor o assunto. Observe:
Etapa 1(correta): Como 2.1− 1 = 1 = 12 enta˜o P[1] e´ verdadeira.
Etapa 2 (corrreta): Hipo´tese de Induc¸a˜o - HI: Seja k ∈ N e suponha que P[k] e´ verdadeira, ou seja,
que 1 + 3 + 5 + · · ·+ 2k − 1 = k2.
Desenvolvimento correto: Como e´ preciso mostrar uma igualdade, desenvolve-se um dos lados para
chegar ao outro, como segue:
1 + 3 + 5 + · · ·+ 2k − 1 + (2(k + 1)− 1) = k2 + (2(k + 1)− 1)
= k2 + 2k + 1
= (k + 1)2.
Conclusa˜o errada: Portanto, P[k+1] e´ uma propriedade verdadeira.
A etapa 2 consiste em provar o enunciado geral p para todo k ∈ N, se P[k] e´ verdadeira enta˜o e´
verdadeira q. Para isso, como sempre que se precisa provar uma implicac¸a˜o desta forma, na impos-
sibilidade de se provar particularmente para todos os naturais k pois ha´ infinitos deles, considera-se
um natural k nas condic¸o˜es da hipo´tese (isto e´, tal que P[k] e´ verdadeira) e prova-se a partir da´ı que
P[k+1] e´ verdadeira.
O Teorema que e´ o PIM, para garantir que vale a conclusa˜o final, exige que valham os enunci-
ados das duas etapas anteriores. Portanto, ao final, o correto e´ indicar que a conclusa˜o p para todo n ∈
N, P[n] e´ propriedade verdadeiraq, e´ consequeˆncia das duas etapas anteriores e do Princ´ıpio da Induc¸a˜o
Matema´tica.
3