5) Seja F:N->N tal que F(1) = 1, F(2k +1) = F(2k) + 1, F (2k) = 2F(k), k (E) N. Determine F(n) em função de n.
Se você escrever n em binário fica fácil de ver que F(n)=n. Pra provar isso, vou usar a indução completa. Começando do 0, F(2.0)=2F(0) => F(0)=2F(0) => F(0)=0. Agora suponha que F(n)=n pra todo 0<=n<=a e vamos ver quanto vale F(a+1).
Pra isso vamos abrir dois casos:
caso 1: a é par. Se a é par, então a/2 é inteiro e F(a/2)=a/2 pela hipótese de indução. Daí k=a/2 => => F(2.(a.2)+1)=F(2.(a/2))+1 => F(a+1)=F(a)+1 Novamente pela hipótese de indução F(a)=a e chegamos a F(a+1)=a+1.
caso 2: a é ímpar. Então (a+1)/2 é inteiro e F((a+1)/2)=(a+1)/2 pela hipótese de indução. (Essa última requer (a+1)/2<=a ou seja a>=1. Mas F(1)=1 pelo enunciado, então a base de indução está ok) Fazendo k=(a+1)/2 => F(2.(a+1)/2)=2.F((a+1)/2) F(a+1)=2.(a+1)/2=a+1 => F(a+1)=a+1
Como F(a+1)=a+1 nos dois casos, então a prova por indução completa está finalizada. QED.
---------------------------------------------------------------- Ricardo Bittencourt http://www.mundobizarro.tk [EMAIL PROTECTED] "tenki ga ii kara sanpo shimashou" ------ União contra o forward - crie suas proprias piadas ------
========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
