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).

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 P(n); isto significa: para cada n em \mathbb{N} (convenção usual abaixo), a expressão P(n) é uma afirmação que pode ser verdadeira ou falsa. Dois pontos essenciais aparecem sempre em uma prova por indução:
  • Caso base: verificar que P(n) é verdadeira para o menor valor de n no domínio (por exemplo n=1 ou n=0, dependendo da convenção).
  • Passo indutivo: assumir que P(k) é verdadeira para um k arbitrário (essa suposição chama-se hipótese de indução) e a partir dela provar que P(k+1) também é verdadeira.
Essas duas peças (caso base + passo indutivo válido para um k arbitrário) são o protocolo que, se cumprido, permite concluir que P(n) vale para todo n 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
P(n):\quad 1+2+\cdots+n=\frac{n(n+1)}{2},
para todos n\in\mathbb{N}, tomando \mathbb{N}=\{1,2,3,\dots\}.
Caso base. Verificar P(1):
1=\frac{1\cdot(1+1)}{2}=\frac{2}{2}=1,
logo P(1) é verdadeira.
Hipótese de indução. Seja k\ge 1 fixo, e suponha como hipótese de indução que P(k) é verdadeira, ou seja,
1+2+\cdots+k=\frac{k(k+1)}{2}.
Passo indutivo. Devemos provar P(k+1). Começamos escrevendo a soma até k+1 e usamos a hipótese:
1+2+\cdots+k+(k+1)=\left(1+2+\cdots+k\right)+(k+1)=\frac{k(k+1)}{2}+(k+1).
Agora manipulamos a expressão algébrica cuidadosamente (fazer contas que o examinador vê):
\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}.
Mas \frac{(k+1)(k+2)}{2} é exatamente a fórmula para n=k+1. Portanto P(k+1) é verdadeira. Conclusão do método: tendo verificado o caso base e mostrado que a hipótese P(k)\Rightarrow P(k+1) vale para todo k\ge1, podemos concluir que P(n) vale para todo n\in\mathbb{N}.
Dicas sobre redação na prova: escreva claramente “Caso base”, depois “Hipótese de indução: seja k arbitrário tal que P(k) é verdadeira”, depois “Mostro que P(k+1) é verdadeira” e conclua “Logo, por indução, …”. A palavra “arbitrário” é importantíssima: não use "suponha para algum k", use “suponha para um k 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 P(n) para a qual se verificam o caso base e o passo indutivo, mas que, entretanto, exista algum m\in\mathbb{N} tal que P(m) seja falsa. Considere o conjunto dos contraexemplos
S=\{n\in\mathbb{N}\mid P(n)\\ \text{é falsa}\}.é
Se S fosse não vazio, pelo princípio do bom-ordenamento de \mathbb{N} (todo subconjunto não vazio de \mathbb{N} tem um menor elemento) existe um menor elemento m=\min S. Pelo caso base sabemos que m\neq 1. Então m>1, de modo que m-1 é natural e, por minimalidade de m, P(m-1) deve ser verdadeira (se P(m-1) fosse falsa então m-1\in S e seria menor que m). Mas pelo passo indutivo, P(m-1)\Rightarrow P(m), logo P(m) seria verdadeira — contradição. Portanto S é vazio e P(n) é verdadeira para todo n. Essa é a razão lógica do método.

Passo 5

Erros comuns e observações úteis:
  • Atenção ao domínio: especifique se \mathbb{N} começa em 0 ou em 1. Ajuste o caso base conforme necessário (por exemplo, para propriedades envolvendo n-1 pode ser preciso verificar P(0) e P(1)).
  • Às vezes é necessário mais de um caso base (por exemplo para recorrências que dependem de dois antecedentes, como Fibonacci); aí verifica-se P(0) e P(1) e depois mostra-se \forall k\ge1 que P(k)\wedge P(k-1)\Rightarrow P(k+1).
  • Existe a forma equivalente chamada “indução forte” (ou completa), onde na hipótese indutiva se assume P(1),P(2),\dots,P(k) e prova-se P(k+1). Muitas vezes elas são intercambiáveis, mas a forte pode ser mais direta para alguns problemas.
  • Na prova, seja claro ao indicar que k é 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 P(n) uma propriedade definida para n\in\mathbb{N}=\{1,2,3,\dots\}. Se valem
P(1)
e
\forall k\in\mathbb{N}\\ \bigl(P(k)\Rightarrow P(k+1)\bigr),
então
\forall n\in\mathbb{N}\\ P(n).

Exercícios relacionados