Seja f a seguinte função definida para os naturais:
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.