Use o princípio de indução para mostrar cada uma das afirmações seguintes:
Verifique a veracidade da seguinte sentença:
P(n) : Qualquer número natural n \geq 8 pode ser escrito da forma n=3 \cdot a+5 \cdot b ; com a, b \in \mathbb{N} \cup 0.

Passo 1

Vou deixar muito claro o que o enunciado pede e quais são os dados que temos.
  • A sentença a verificar é P(n): “Qualquer número natural n\ge 8 pode ser escrito da forma n=3\cdot a+5\cdot b, com a,b\in\mathbb{N}\cup\{0\}.”
  • Pedido: provar que P(n) é verdadeira para todo n\ge 8.
  • Informações relevantes: n é um número natural maior ou igual a 8; a e b devem ser números inteiros não-negativos (ou seja, a,b\in\mathbb{N}\cup\{0\}).
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 P(n) é verdadeira para alguns primeiros valores de n (casos base), e se sempre que P é verdadeira para todos os inteiros entre o começo e um certo k então essa verdade implica P(k+1), então P(n) vale para todos os n a partir do começo.
  • Em forma: suponha que existe m tal que (i) P(m),P(m+1),\dots,P(r) são verdadeiros para alguns casos base iniciais m\le r e (ii) para todo n\ge r, se P(m),P(m+1),\dots,P(n) são verdadeiros então P(n+1) é verdadeiro. Então P(n) vale para todo n\ge m.
  • Por que usar a versão forte aqui? Porque a demonstração natural consiste em reduzir n para n-3 (ou seja, usar uma representação de um número menor para construir a representação de n). Assim, ao provar P(k+1) convém já ter disponível a validade de P(k-2); isso é exatamente o que a hipótese de indução forte nos permite (assumir todas as verdades anteriores). A forma simples (assumir só P(k) para provar P(k+1)) não é direta aqui sem manipular os casos base de forma extra.

Passo 3

Escolha e verificação dos casos base.
Vou provar explicitamente P(8),P(9),P(10). Mostrar alguns casos base suficientes é importante porque depois vou reduzir números subtraindo 3; com três casos base conseguimos “cobrir” os resíduos mod 3.
  • Para n=8: tomar a=1 e b=1. Verificar: 3\cdot a + 5\cdot b = 3\cdot 1 + 5\cdot 1 = 3 + 5 = 8.Assim 8 tem a forma pedida com a,b\in\mathbb{N}\cup\{0\}.
  • Para n=9: tomar a=3 e b=0. Verificar: 3\cdot a + 5\cdot b = 3\cdot 3 + 5\cdot 0 = 9 + 0 = 9.
  • Para n=10: tomar a=0 e b=2. Verificar: 3\cdot a + 5\cdot b = 3\cdot 0 + 5\cdot 2 = 0 + 10 = 10.
Todos os três são representações com coeficientes inteiros não negativos. Então os casos base P(8),P(9),P(10) são verdadeiros.
Observação intuitiva (opcional, para fixar): esses três casos base correspondem a cobrir as possibilidades de resto módulo 3 entre os números a partir de 8.

Passo 4

Hipótese de indução (forte).
Fixe um inteiro k\ge 10 e suponha, como hipótese de indução forte, que a propriedade P(j) é verdadeira para todo j com
8 \le j \le k.
Isto significa: para cada j tal que 8\le j\le k existe um par de inteiros não-negativos a_j,b_j com
j = 3\cdot a_j + 5\cdot b_j.
Essa é a hipótese que vamos usar para deduzir P(k+1).

Passo 5

Passo indutivo: provar P(k+1) usando a hipótese de indução forte.
Queremos mostrar que existe a,b\in\mathbb{N}\cup\{0\} tais que
k+1 = 3\cdot a + 5\cdot b.
  • Primeiro nota: se k+1 for igual a 8,9 ou 10 já sabemos a afirmação pelos casos base. Então podemos supor que k+1\ge 11. Assim k\ge 10 (o que já estava fixado).
  • Calcule (k+1)-3 = k-2. Como k\ge 10 temos k-2 \ge 8. Logo k-2 está no intervalo onde a hipótese de indução forte garante P(k-2).
  • Pela hipótese de indução forte existe a',b'\in\mathbb{N}\cup\{0\} tais que k-2 = 3\cdot a' + 5\cdot b'.
  • Some 3 em ambos os lados da igualdade anterior: k+1 = (k-2) + 3 = 3\cdot a' + 5\cdot b' + 3 = 3\cdot (a'+1) + 5\cdot b'.
  • Defina a := a'+1 e b:=b'. Então a,b\in\mathbb{N}\cup\{0\} e k+1 = 3\cdot a + 5\cdot b.Portanto P(k+1) é verdadeira.
A ideia é simples: se um número menor (no caso k-2) tem a forma desejada, adicionando 3 (ou seja, aumentando o coeficiente de 3 em 1) obtemos a representação do número seguinte k+1.

Passo 6

Conclusão da indução e fechamento da prova.
  • Temos os casos base P(8),P(9),P(10) verdadeiros.
  • Mostramos que para qualquer k\ge 10, se P(8),\dots,P(k) são verdadeiros então P(k+1) também é verdadeiro (indução forte).
  • Pelo princípio da indução forte, a propriedade P(n) vale para todo n\ge 8.
Para fixar a intuição, alguns exemplos concretos gerados pela regra:
  • 11 = 3\cdot 2 + 5\cdot 1 (pegou 8=3\cdot1+5\cdot1 e somou 3);
  • 12 = 3\cdot 4 + 5\cdot 0 (pegou 9=3\cdot3+5\cdot0 e somou 3);
  • 13 = 3\cdot 1 + 5\cdot 2 (pegou 10=3\cdot0+5\cdot2 e somou 3).
Pronto — a sentença foi provada por indução forte.

Resposta

A sentença P(n) é verdadeira: todo n\ge 8 pode ser escrito na forma n=3\cdot a+5\cdot b com a,b\in\mathbb{N}\cup\{0\}.

Exercícios relacionados