Exercício 1.23. Considere a sequência numérica (
) definida recursivamente por
, e para todo
. Demonstre, utilizando o indução forte, que
Passo 1
O enunciado fornece uma sequência
definida por recorrência e pede para provar, por indução forte, a fórmula fechada
Informações dadas:
-
. -
. - Para todo
,
O que se pede: demonstrar que a fórmula
vale para todo
, usando indução forte.
Passo 2
Breve explicação do método que vou usar (indução forte), porque o enunciado pede isso e porque é natural aqui.
Indução forte é uma forma de prova por indução em que, para provar a propriedade para um certo
, assumimos que a propriedade já é verdadeira para todos os índices menores que
(não apenas para o caso
como na indução simples). Em símbolos: para mostrar que
vale para todo
, procede-se assim:
- Verificar casos base (normalmente vários, conforme necessário).
- Mostrar que, para qualquer
algum valor (a partir de onde começamos o passo indutivo), se é verdadeira para todo com , então também é verdadeira.
Aqui a recorrência usa
e
, por isso precisamos das bases
e
; com isso, ao assumir verdade para todos os
poderemos substituir
e
pelas suas formas fechadas.
Passo 3
Verificação do caso base
.
A fórmula proposta dá, para
,
Como o enunciado dá
, temos que a fórmula coincide com
. Portanto
é verdadeira.
Passo 4
Verificação do caso base
.
A fórmula proposta dá, para
,
Como o enunciado dá
, a fórmula coincide com
. Portanto
é verdadeira.
Passo 5
Passo indutivo (indução forte).
Seja
. Suponha, como hipótese de indução forte, que para todo inteiro
com
vale
Em particular, essa hipótese nos dá as expressões para
e
, que são justamente as que precisamos na recorrência.
Passo 6
Usar a recorrência e a hipótese de indução para calcular
.
Começamos pela recorrência dada:
Aplicando a hipótese de indução (substituindo
e
), obtemos
Agora desenvolvo separadamente as partes que envolvem potências de
e de
.
Para as potências de
:
Aqui usei que
, fatorando
.
Para as potências de
:
Aqui usei que
, fatorando
.
Somando as duas partes:
Portanto, sob a hipótese de indução forte, mostramos que
é verdadeira.
Passo 7
Conclusão final da indução.
Tendo verificado os casos base
e
e mostrado que, para todo
, a validade da propriedade para todos os
implica sua validade para
, pela princípio da indução forte concluímos que