Determine se cada uma das definições propostas abaixo é 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)=2, f(n)=2 f(n-2) para n \geq 2

Passo 1

O enunciado define f\colon \mathbb{N}_0\to\mathbb{Z} por
f(0)=1,\quad f(1)=2,
e para todo n\ge2
f(n)=2\,f(n-2).
O conteúdo aqui é resolução de recorrência simples por paridade de n. Vamos primeiro checar a validade da definição recursiva e em seguida encontrar uma fórmula fechada para f(n), provando por indução que ela satisfaz a definição.

Passo 2

Para uma definição recursiva ser válida precisamos de condições iniciais que cubram todos os casos base n=0 e n=1 estão dados) e de uma regra de recorrência que permita calcular f(n) para todo n\ge2 em termos de valores já definidos (aqui f(n) em termos de f(n-2). Logo, a definição é bem posta e garante existência e unicidade de f.

Passo 3

Vamos resolver a recorrência separando n em par ou ímpar.
Para n=2k com k\ge1, aplicamos a regra várias vezes:
f(2k)=2\,f(2k-2) =2\bigl(2\,f(2k-4)\bigr) =\dots =2^k\,f(0) =2^k\cdot1 =2^k.
Para n=2k+1 com k\ge0, de modo análogo:
f(2k+1)=2\,f(2k-1) =2\bigl(2\,f(2k-3)\bigr) =\dots =2^k\,f(1) =2^k\cdot2 =2^{k+1}.

Passo 4

Portanto, uma fórmula fechada é
f(n)= \begin{cases} 2^{k},&\text{se }n=2k,\\[6pt] 2^{\,k+1},&\text{se }n=2k+1. \end{cases}]

Passo 5

Vamos provar por indução em k (ou em n decrescendo de 2 em 2) que essa fórmula satisfaz a recorrência:
Base: para n=0 temos k=0 e a fórmula dá f(0)=2^0=1, ok; para n=1, k=0 e f(1)=2^{0+1}=2, ok.
Passo indutivo: suponha a fórmula válida para n-2.
  • Se n=2k, então n-2=2(k-1) e, por hipótese, f(n-2)=2^{\,k-1}. Logo
f(n)=2\,f(n-2)=2\cdot2^{\,k-1}=2^k,
que bate com o caso n=2k.
  • Se n=2k+1, então n-2=2(k-1)+1 e f(n-2)=2^{(k-1)+1}=2^k. Logo
f(n)=2\,f(n-2)=2\cdot2^k=2^{k+1},
que bate com o caso n=2k+1.
Assim a fórmula é consistente com a definição recursiva.

Resposta

f(n)= \begin{cases} 2^{\,n/2},&\text{se \(n\) for par},\\[6pt] 2^{\,(n+1)/2},&\text{se \(n\) for ímpar}. \end{cases}í]

Exercícios de Livros Relacionados