Determine se cada uma das definições propostas abaixo é uma definição recursiva válida de uma função
a partir do conjunto dos números inteiros não negativos para o conjunto dos números inteiros. Se
for bem definida, encontre uma fórmula para
quando
for um número inteiro não negativo e demonstre que sua fórmula é válida.
se
for ímpar e
se
for par e
Passo 1
O enunciado define a função
por:
Queremos verificar se essa definição é recursiva válida e encontrar uma fórmula fechada para
.
Passo 2
Para todo
temos exatamente um dos casos:
- Base
, já definimos . - Se
é ímpar, usamos cujo índice é menor que . - Se
é par, usamos cujo índice também é menor que .
Como cada valor de
recorre apenas a valores já definidos (com índice estritamente menor), a definição é bem definida e válida.
Passo 3
Vamos calcular alguns valores iniciais para perceber um padrão:
Observa–se que
são exatamente potências de 3. Então conjecturamos
Passo 4
Agora provamos por indução forte que
para todo
.
Base
:
Passo indutivo: suponha
para todo
.
- Se
é ímpar, então
- Se
é par , então
Em ambos os casos obtemos
, fechando a indução.
Resposta
A definição é recursiva válida e
para todo inteiro não negativo
.