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

Passo 1

O enunciado define a função f:\mathbb{N}_0\to\mathbb{Z} por:
f(0)=1,
f(n)=3\,f(n-1)\quad\text{se \(n\) é ímpar \(n\ge1\)},éí
f(n)=9\,f(n-2)\quad\text{se \(n\) é par \(n\ge2\)}.é
Queremos verificar se essa definição é recursiva válida e encontrar uma fórmula fechada para f(n).

Passo 2

Para todo n\ge0 temos exatamente um dos casos:
  • Base n=0, já definimos f(0).
  • Se n\ge1 é ímpar, usamos f(n-1) cujo índice é menor que n.
  • Se n\ge2 é par, usamos f(n-2) cujo índice também é menor que n.
Como cada valor de f(n) recorre apenas a valores já definidos (com índice estritamente menor), a definição é bem definida e válida.

Passo 3

Vamos calcular alguns valores iniciais para perceber um padrão:
f(0)=1,\quad f(1)=3\,f(0)=3,\quad f(2)=9\,f(0)=9,
f(3)=3\,f(2)=27,\quad f(4)=9\,f(2)=81,\dots
Observa–se que 1,3,9,27,81,\dots são exatamente potências de 3. Então conjecturamos
f(n)=3^n.

Passo 4

Agora provamos por indução forte que f(n)=3^n para todo n\ge0.
Base n=0:
f(0)=1=3^0.
Passo indutivo: suponha f(k)=3^k para todo k<n.
  • Se n é ímpar, então
f(n)=3\,f(n-1)=3\cdot3^{\,n-1}=3^n.
  • Se n é par n\ge2, então
f(n)=9\,f(n-2)=9\cdot3^{\,n-2}=3^2\cdot3^{\,n-2}=3^n.
Em ambos os casos obtemos f(n)=3^n, fechando a indução.

Resposta

A definição é recursiva válida e
f(n)=3^n
para todo inteiro não negativo n.

Exercícios de Livros Relacionados