Suponha que os números
são definidos por indução por
e
para todo
. Use o Segundo Princípio da Indução Finita para mostrar que
para todo inteiro positivo
.
Passo 1
Beleza, aqui o que a questão diz é: temos a sequência
e, pra todo
O que pedem é usar o Segundo Princípio da Indução (indução forte) pra mostrar que
para todo
Conteúdo que vamos usar:
1. Indução forte (supor a propriedade para todos os valores até
2. Desigualdade triangular e valor absoluto, para controlar o “menos” das subtrações.
3. Propriedade de soma de potências de 2.
Passo 2
Casos-base (verificar manualmente os primeiros
):
- Para
: e . Então . - Para
: e . Então . - Para
: e . Então .
Pronto, a desigualdade vale para.
Passo 3
Hipótese de indução forte: suponha que para todo inteiro
com
já temos
Repare que, ao controlar
, automaticamente controlamos
porque
.
Passo 4
Vamos provar que então
, o que implica
.
Usando a definição para :
Usando a definição para
Agora aplicamos a desigualdade triangular em valor absoluto:
Pela hipótese de indução forte, cada um desses três valores satisfaz
Somando-as:
Como
, temos
Logo
Isso conclui o passo de indução.
Resposta
Para todo inteiro positivo
, vale
como queríamos demonstrar.