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)=2, f(n)=f(n-1) se n for ímpar e n \geq 1 \mathrm{e} f(n)=2 f(n-2) se n \geq 2

Passo 1

O enunciado define uma função f\colon \mathbb{Z}_{\ge0}\to\mathbb{Z} por
f(0)=2,
e, para n\ge1:
  • se n é ímpar, f(n)=f(n-1),
  • se n\ge2 é par, f(n)=2\,f(n-2).
    O objetivo é (i) verificar que isso é uma definição recursiva válida e (ii) encontrar e provar uma fórmula fechada para f(n).

Passo 2

Para ver que a definição é válida, note que
  • há um caso base f(0)=2,
  • para cada n\ge1, a definição de f(n) usa apenas valores f(n-1) ou f(n-2), ambos já definidos pois são índices menores que n.
    Isso garante existência e unicidade de f(n) por indução nos inteiros não negativos.

Passo 3

Vamos calcular alguns valores iniciais para ver o padrão:
f(0)=2, \quad f(1)=f(0)=2, \quad f(2)=2\,f(0)=4, \quad f(3)=f(2)=4,
f(4)=2\,f(2)=8, \quad f(5)=f(4)=8, \quad\text{etc.}
Observamos que, para k\ge0,
f(2k)=2^{k+1}, \quad f(2k+1)=f(2k)=2^{k+1}.

Passo 4

Com base nisso, propomos a fórmula fechada
f(n)=2^{\lfloor n/2\rfloor+1}.
Vamos provar por indução em n que ela satisfaz a definição recursiva:
Base n=0:
\lfloor 0/2\rfloor+1 =0+1=1 \quad\Longrightarrow\quad 2^1=2=f(0).
Passo indutivo: suponha que a fórmula valha para todos os m<n.
  • Se n é ímpar, escreva n=2k+1. Então
    \lfloor n/2\rfloor=\lfloor(2k+1)/2\rfloor=k, e
f(n)=f(n-1)=2^{\lfloor(n-1)/2\rfloor+1} =2^{\lfloor2k/2\rfloor+1} =2^{k+1} =2^{\lfloor n/2\rfloor+1}.
  • Se n\ge2 é par, escreva n=2k. Então
    \lfloor n/2\rfloor=\lfloor2k/2\rfloor=k, e
f(n)=2\,f(n-2)=2\cdot 2^{\lfloor(n-2)/2\rfloor+1} =2\cdot 2^{\lfloor(2k-2)/2\rfloor+1} =2\cdot 2^{(k-1)+1} =2^{k+1} =2^{\lfloor n/2\rfloor+1}.
Assim, a fórmula vale para n, concluindo a indução.

Resposta

A definição recursiva é válida, e a fórmula fechada é
f(n)=2^{\lfloor n/2\rfloor+1},\quad n\ge0.

Exercícios de Livros Relacionados