Considere a sequência
e
, para
.
Prove, por indução em
, que
Prove, por indução em
Passo 1
O enunciado dá uma sequência definida por:
-
, -
, -
para .
O que se pede: provar, por indução em
, que
Passo 2
Breve explicação da técnica que vamos usar (indução adequada ao caso):
- Em provas por indução normalmente verificamos casos base e depois mostramos que, se a propriedade vale para um certo
, então vale para . - Como a recorrência aqui envolve dois termos anteriores (é de ordem 2), precisamos garantir os dois casos base (
e ) e, na etapa indutiva, assumir a desigualdade tanto para quanto para . Essa forma é às vezes chamada de indução forte ou indução por completo; é totalmente válida e natural quando a definição recursiva usa mais de um termo anterior.
Passo 3
Verificação dos casos base:
- Para
: calcular e comparar.
logo
. Portanto o caso
é verdadeiro.
- Para
: calcular e comparar.
logo
. Portanto o caso
também é verdadeiro.
Passo 4
Hipótese indutiva (passo indutivo):
Seja . Suponha, como hipótese indutiva, que as desigualdades
Seja
são verdadeiras. A tarefa é mostrar que dessa hipótese decorre
Passo 5
Usar a recorrência e manipular a desigualdade:
Pela definição da sequência,
Pela definição da sequência,
Pelo que assumimos na hipótese indutiva,
Fatando
obtemos
Agora comparo o fator
com
:
Portanto
Juntando as desigualdades obtemos
que é exatamente o que queríamos provar no passo indutivo.
Passo 6
Conclusão por indução:
Tendo verificado os casos base e mostrando que, para todo
, a validade da propriedade para
e
implica sua validade para
, segue por indução forte que
Tendo verificado os casos base
Bom trabalho — essa técnica de usar as duas hipóteses anteriores é padrão para recorrências de segunda ordem; a constante
funciona porque
, o que garante o fechamento da desigualdade no passo indutivo.