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 uma função recursiva
pelos casos iniciais
e pela regra recursiva
Este é um problema de recorrência linear de primeira ordem com dois casos-base.
Passo 2
Para
a definição usa apenas o valor
, que já foi definido em etapas anteriores, e temos dois casos-base
e
. Logo, a definição é válida e determina unicamente cada valor de
.
Passo 3
Calculemos os primeiros termos para identificar um padrão:
,
,
,
,
, …
Parece que, para ,
Parece que, para
Passo 4
Demonstração por indução em
de que
.
Base
:
portanto vale.
Passo indutivo: suponha que, para algum
,
. Então
que é exatamente o que queremos. Isso fecha a indução.
Resposta
A definição é válida e