Enuncie precisamente o primeiro princípio de indução.
Passo 1
O enunciado pede para você “enunciar precisamente o primeiro princípio de indução”.
Informações dadas: nenhuma além do pedido.
O que vou entregar: uma explicação didática e passo a passo do que é o princípio, como usá-lo numa prova por indução e por fim a enunciação precisa (formal).
Informações dadas: nenhuma além do pedido.
O que vou entregar: uma explicação didática e passo a passo do que é o princípio, como usá-lo numa prova por indução e por fim a enunciação precisa (formal).
Passo 2
Primeiro vamos fixar as palavras que aparecem na enunciação (sem enunciá-la ainda). Defina uma propriedade dependente de um inteiro natural chamando-a de
; isto significa: para cada
em
(convenção usual abaixo), a expressão
é uma afirmação que pode ser verdadeira ou falsa. Dois pontos essenciais aparecem sempre em uma prova por indução:
- Caso base: verificar que
é verdadeira para o menor valor de no domínio (por exemplo ou , dependendo da convenção). - Passo indutivo: assumir que
é verdadeira para um arbitrário (essa suposição chama-se hipótese de indução) e a partir dela provar que também é verdadeira.
Essas duas peças (caso base + passo indutivo válido para um
arbitrário) são o protocolo que, se cumprido, permite concluir que
vale para todo
do domínio. Mais adiante eu mostro um exemplo concreto de aplicação para ficar claro como escrever numa prova de prova.
Passo 3
Exemplo prático — mostrar passo a passo como se escreve na prova (modelo que dá ponto na prova). Vou provar a propriedade
para todos
, tomando
.
Caso base. Verificar
:
logo
é verdadeira.
Hipótese de indução. Seja
fixo, e suponha como hipótese de indução que
é verdadeira, ou seja,
Passo indutivo. Devemos provar
. Começamos escrevendo a soma até
e usamos a hipótese:
Agora manipulamos a expressão algébrica cuidadosamente (fazer contas que o examinador vê):
Mas
é exatamente a fórmula para
. Portanto
é verdadeira. Conclusão do método: tendo verificado o caso base e mostrado que a hipótese
vale para todo
, podemos concluir que
vale para todo
.
Dicas sobre redação na prova: escreva claramente “Caso base”, depois “Hipótese de indução: seja
arbitrário tal que
é verdadeira”, depois “Mostro que
é verdadeira” e conclua “Logo, por indução, …”. A palavra “arbitrário” é importantíssima: não use "suponha para algum
", use “suponha para um
arbitrário”.
Passo 4
Por que esse método é válido? Esboço de prova do princípio (ideia do princípio do menor contramodelo). Suponha que exista uma propriedade
para a qual se verificam o caso base e o passo indutivo, mas que, entretanto, exista algum
tal que
seja falsa. Considere o conjunto dos contraexemplos
Se
fosse não vazio, pelo princípio do bom-ordenamento de
(todo subconjunto não vazio de
tem um menor elemento) existe um menor elemento
. Pelo caso base sabemos que
. Então
, de modo que
é natural e, por minimalidade de
,
deve ser verdadeira (se
fosse falsa então
e seria menor que
). Mas pelo passo indutivo,
, logo
seria verdadeira — contradição. Portanto
é vazio e
é verdadeira para todo
. Essa é a razão lógica do método.
Passo 5
Erros comuns e observações úteis:
- Atenção ao domínio: especifique se
começa em ou em . Ajuste o caso base conforme necessário (por exemplo, para propriedades envolvendo pode ser preciso verificar e ). - Às vezes é necessário mais de um caso base (por exemplo para recorrências que dependem de dois antecedentes, como Fibonacci); aí verifica-se
e e depois mostra-se que . - Existe a forma equivalente chamada “indução forte” (ou completa), onde na hipótese indutiva se assume
e prova-se . Muitas vezes elas são intercambiáveis, mas a forte pode ser mais direta para alguns problemas. - Na prova, seja claro ao indicar que
é arbitrário; não cometa o erro de verificar apenas um exemplo numérico e tentar generalizar sem a etapa algébrica lógica.
Força aí — na prova escreva os três blocos (caso base, hipótese, passo) com calma e você ganha pontos. Agora, abaixo está a enunciação precisa pedida.
Resposta
Seja
uma propriedade definida para
. Se valem
e
então