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 =========================================================================
