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
por
por
O conteúdo é definição recursiva (ou primitiva) de função em
.
Passo 2
Para ser uma definição recursiva válida, precisamos de:
- Um valor inicial em
, aqui . - Uma regra que para cada
expressa em termos de valores já definidos , garantindo que todo em receba um valor em .
A condição está satisfeita, logo a definição é válida.
Passo 3
Vamos calcular alguns valores para ver um padrão:
Parece que a cada passo subtraímos , então suspeitamos
Parece que a cada passo subtraímos
Passo 4
Conjecturamos que
para todo
.
Passo 5
Vamos provar por indução em
que
.
Base : pela definição
e
, ok.
Passo indutivo: suponha para certo
.
Então para vale
Base
Passo indutivo: suponha
Então para
Assim a fórmula mantém-se para
. Por indução, vale para todo
.
Resposta
A definição é válida e a fórmula fechada é