Use o princípio de indução para mostrar cada uma das afirmações seguintes:
Verifique a veracidade da seguinte sentença:
: Qualquer número natural
pode ser escrito da forma
com
.
Verifique a veracidade da seguinte sentença:
Passo 1
Vou deixar muito claro o que o enunciado pede e quais são os dados que temos.
- A sentença a verificar é
: “Qualquer número natural pode ser escrito da forma , com .” - Pedido: provar que
é verdadeira para todo . - Informações relevantes:
é um número natural maior ou igual a ; e devem ser números inteiros não-negativos (ou seja, ).
Nada mais será assumido sem prova; a demonstração pedida no enunciado é pelo princípio de indução (vou usar a forma forte de indução, explico por quê nos próximos passos).
Passo 2
Explicando o princípio de indução forte (e por que usar ele aqui).
- O princípio de indução forte diz, em palavras simples: se uma propriedade
é verdadeira para alguns primeiros valores de (casos base), e se sempre que é verdadeira para todos os inteiros entre o começo e um certo então essa verdade implica , então vale para todos os a partir do começo. - Em forma: suponha que existe
tal que (i) são verdadeiros para alguns casos base iniciais e (ii) para todo , se são verdadeiros então é verdadeiro. Então vale para todo . - Por que usar a versão forte aqui? Porque a demonstração natural consiste em reduzir
para (ou seja, usar uma representação de um número menor para construir a representação de ). Assim, ao provar convém já ter disponível a validade de ; isso é exatamente o que a hipótese de indução forte nos permite (assumir todas as verdades anteriores). A forma simples (assumir só para provar ) não é direta aqui sem manipular os casos base de forma extra.
Passo 3
Escolha e verificação dos casos base.
Vou provar explicitamente
. Mostrar alguns casos base suficientes é importante porque depois vou reduzir números subtraindo
; com três casos base conseguimos “cobrir” os resíduos mod
.
- Para
: tomar e . Verificar: Assim tem a forma pedida com . - Para
: tomar e . Verificar: - Para
: tomar e . Verificar:
Todos os três são representações com coeficientes inteiros não negativos. Então os casos base
são verdadeiros.
Observação intuitiva (opcional, para fixar): esses três casos base correspondem a cobrir as possibilidades de resto módulo
entre os números a partir de
.
Passo 4
Hipótese de indução (forte).
Fixe um inteiro
e suponha, como hipótese de indução forte, que a propriedade
é verdadeira para todo
com
Isto significa: para cada
tal que
existe um par de inteiros não-negativos
com
Essa é a hipótese que vamos usar para deduzir
.
Passo 5
Passo indutivo: provar
usando a hipótese de indução forte.
Queremos mostrar que existe
tais que
- Primeiro nota: se
for igual a ou já sabemos a afirmação pelos casos base. Então podemos supor que . Assim (o que já estava fixado). - Calcule
. Como temos . Logo está no intervalo onde a hipótese de indução forte garante . - Pela hipótese de indução forte existe
tais que - Some
em ambos os lados da igualdade anterior: - Defina
e . Então e Portanto é verdadeira.
A ideia é simples: se um número menor (no caso
) tem a forma desejada, adicionando
(ou seja, aumentando o coeficiente de
em
) obtemos a representação do número seguinte
.
Passo 6
Conclusão da indução e fechamento da prova.
- Temos os casos base
verdadeiros. - Mostramos que para qualquer
, se são verdadeiros então também é verdadeiro (indução forte). - Pelo princípio da indução forte, a propriedade
vale para todo .
Para fixar a intuição, alguns exemplos concretos gerados pela regra:
-
(pegou e somou ); -
(pegou e somou ); -
(pegou e somou ).
Pronto — a sentença foi provada por indução forte.
Resposta
A sentença
é verdadeira: todo
pode ser escrito na forma
com
.