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)=2, f(1)=3, f(n)=f(n-1)-1 para n \geq 2

Passo 1

O enunciado define uma função recursiva f\colon \mathbb{N}_0\to\mathbb{Z} pelos casos iniciais
f(0)=2,\quad f(1)=3
e pela regra recursiva
f(n)=f(n-1)-1\quad\text{para }n\ge2.
Este é um problema de recorrência linear de primeira ordem com dois casos-base.

Passo 2

Para n\ge2 a definição usa apenas o valor f(n-1), que já foi definido em etapas anteriores, e temos dois casos-base n=0 e n=1. Logo, a definição é válida e determina unicamente cada valor de f(n).

Passo 3

Calculemos os primeiros termos para identificar um padrão: f(0)=2, f(1)=3, f(2)=f(1)-1=2, f(3)=f(2)-1=1, f(4)=f(3)-1=0, …
Parece que, para n\ge1,
f(n)=4-n.

Passo 4

Demonstração por indução em n\ge1 de que f(n)=4-n.
Base n=1:
f(1)=3 \quad\text{e}\quad 4-1=3,
portanto vale.
Passo indutivo: suponha que, para algum k\ge2, f(k-1)=4-(k-1). Então
f(k)=f(k-1)-1=(4-(k-1))-1=4-k,
que é exatamente o que queremos. Isso fecha a indução.

Resposta

A definição é válida e
f(n)= \begin{cases} 2, & n=0,\\[6pt] 4-n, & n\ge1. \end{cases}]

Exercícios de Livros Relacionados