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\ge3 f(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.

Passo 3

Vamos escrever n na forma
n=3k+r,\quad r\in\{0,1,2\},\;k=\left\lfloor\frac n3\right\rfloor.
Aplicando a relação recursiva repetidamente, obtemos
f(n)=2\,f(n-3)=2^2\,f(n-6)=\cdots=2^k\,f(r).

Passo 4

Como r\in\{0,1,2\} e \{f(0),f(1),f(2)\}=\{1,0,2\}, concluímos
f(n)=2^k\,f(r) =\begin{cases} 2^k\cdot1=2^k,&\text{se }r=0,\\\\ 2^k\cdot0=0,&\text{se }r=1,\\\\ 2^k\cdot2=2^{k+1},&\text{se }r=2. \end{cases}
Ou seja,
f(n)= \begin{cases} 2^k,&n=3k,\\\\ 0,&n=3k+1,\\\\ 2^{k+1},&n=3k+2. \end{cases}

Passo 5

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,
f(n)=2\,f(n-3) =2\bigl(2^{\,k-1}f(r)\bigr) =2^k\,f(r),
que coincide com a fórmula fechada. Assim, por indução, vale para todo n.

Resposta

\text{Para }n\ge0,\quad f(n)= \begin{cases} 2^k,&\text{se }n=3k,\\\\ 0,&\text{se }n=3k+1,\\\\ 2^{k+1},&\text{se }n=3k+2, \end{cases} \quad k=\bigl\lfloor n/3\bigr\rfloor.

Exercícios de Livros Relacionados