Determine se cada uma das definições propostas a seguir é uma definição recursiva válida de uma função f a partir do conjunto dos números inteiros não negativos para o conjunto dos números inteiros. Se f for bem definida, encontre uma fórmula para f(n) quando n for um número inteiro não negativo e demonstre que sua fórmula é válida. f(0)=1, f(1)=0, f(2)=2, f(n)=2 f(n-3) para n \geq 3
Passo 1
O enunciado define uma função f:\mathbb{N}_0\to\mathbb{Z} por
f(0)=1,\quad f(1)=0,\quad f(2)=2,
e para n\ge3f(n)=2\,f(n-3).
O conteúdo é recursão com passo 3, e vamos usar indução (princípio da definição recursiva) e técnica de “desenrolar” a recorrência para obter uma fórmula fechada.
Passo 2
Para ver que a definição é válida, note que cada valor f(n) com n\ge3 é expresso em função de f(n-3), e n-3<n. Como fornecemos os valores iniciais em 0,1,2, por indução forte todos os f(n) ficam bem definidos e únicos. Logo, a definição é recursiva válida.
Demonstração por indução em n:
Base n=0,1,2 trivialmente satisfaz.
Passo indutivo: suponha a fórmula válida para todo m<n. Se n\ge3, escreva n=3k+r e note que n-3=3(k-1)+r. Então, pela hipótese indutiva,