Seja f a seguinte função definida para os naturais:
f(n)= 0 & se n=0 1 & se n=1 2 f(n / 2) & se n for par e n>0 f(n-2)+2 & se n for impar e n>1
Consegue demonstrar que f(n)=n para todo o n >= 0 ?

Passo 1

O enunciado define a função recursiva f:NtoN por
f(n)=0 &se n=0,1 &se n=1,2,f(n/2) &se n>0 é par,f(n-2)+2 &se n>1 é ímparééí
Queremos provar que f(n)=n para todo n>=0. Vamos usar indução forte, pois o caso ímpar usa f(n-2).

Passo 2

Verificamos as bases da indução:
  • Para n=0: pela definição f(0)=0. OK.
  • Para n=1: pela definição f(1)=1. OK.

Passo 3

Passo da indução forte: suponha que para todo k valha f(k)=k. Vamos mostrar f(n)=n.
Caso 1: n>1 par. Então
f(n)=2,f(n/2)
Como n/2, pela hipótese de indução f(n/2)=n/2. Logo
f(n)=2timesn2=n

Passo 4

Caso 2: n>1 ímpar. Então
f(n)=f(n-2)+2
Como n-2, pela hipótese de indução f(n-2)=n-2. Logo
f(n)=(n-2)+2=n
Nos dois casos chegamos a f(n)=n, completando o passo indutivo por indução forte.

Resposta

f(n)=n

Exercícios relacionados