Determine se cada uma das definições propostas a seguir é 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
Passo 1
O enunciado define uma função
por
e, para
:
- se
é ímpar, , - se
é par, .
O objetivo é (i) verificar que isso é uma definição recursiva válida e (ii) encontrar e provar uma fórmula fechada para.
Passo 2
Para ver que a definição é válida, note que
- há um caso base
, - para cada
, a definição de usa apenas valores ou , ambos já definidos pois são índices menores que .
Isso garante existência e unicidade depor indução nos inteiros não negativos.
Passo 3
Vamos calcular alguns valores iniciais para ver o padrão:
Observamos que, para
,
Passo 4
Com base nisso, propomos a fórmula fechada
Vamos provar por indução em
que ela satisfaz a definição recursiva:
Base
:
Passo indutivo: suponha que a fórmula valha para todos os
.
- Se
é ímpar, escreva . Então
, e
- Se
é par, escreva . Então
, e
Assim, a fórmula vale para
, concluindo a indução.
Resposta
A definição recursiva é válida, e a fórmula fechada é