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.
para
Passo 1
O enunciado define
por
e para todo
O conteúdo aqui é resolução de recorrência simples por paridade de
. Vamos primeiro checar a validade da definição recursiva e em seguida encontrar uma fórmula fechada para
, provando por indução que ela satisfaz a definição.
Passo 2
Para uma definição recursiva ser válida precisamos de condições iniciais que cubram todos os casos base
e
estão dados) e de uma regra de recorrência que permita calcular
para todo
em termos de valores já definidos (aqui
em termos de
. Logo, a definição é bem posta e garante existência e unicidade de
.
Passo 3
Vamos resolver a recorrência separando
em par ou ímpar.
Para
com
, aplicamos a regra várias vezes:
Para
com
, de modo análogo:
Passo 4
Portanto, uma fórmula fechada é
Passo 5
Vamos provar por indução em
(ou em
decrescendo de 2 em 2) que essa fórmula satisfaz a recorrência:
Base: para
temos
e a fórmula dá
, ok; para
,
e
, ok.
Passo indutivo: suponha a fórmula válida para
.
- Se
, então e, por hipótese, . Logo
que bate com o caso
.
- Se
, então e . Logo
que bate com o caso
.
Assim a fórmula é consistente com a definição recursiva.