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.
para
Passo 1
O enunciado define recursivamente a função
por
O conteúdo aqui é definição recursiva e prova por indução. Vamos verificar se a definição é válida e encontrar uma fórmula fechada para
.
Passo 2
Para ser uma definição recursiva válida precisamos de um caso base e de uma regra que expresse cada
em termos de valores anteriores. Aqui temos o caso base
e, para todo
, a regra
que depende apenas de
. Logo, a definição é bem formulada e garante existência e unicidade de
.
Passo 3
Calculando os primeiros termos vemos o padrão:
Percebe-se que os valores alternam entre
e
. Conjecturamos então
Passo 4
Prova por indução em
:
Base
:
Pela definição, , e
. Logo vale para
.
Pela definição,
Passo indutivo:
Suponha que para algum valha
. Então, usando a regra recursiva,
Suponha que para algum
Assim, a fórmula vale em
e, pelo princípio da indução, vale para todo
.
Resposta
A definição é recursiva válida e