0=<f(0)<f(1)<f(2)=2 ==> f(0)=0 et f(1)=1 2=f(2)<f(3)<f(4)=f(2²)=f(2)²=4 ===> f(3)=3
Par récurrence sur m: pour tout m>=0 on a f(n)=n pour tout n=<2^m pour m=0 ou m=1 c'est ok supposons que c'est vrai pour un m soit n entier : n=<2^(m+1)
si n pair ==> n/2=<2^m alors par hypothèse f(n/2)=n/2 mais f(n)=f(2.n/2)=f(2)f(n/2)=n
si n impair ==> n=2k+1 et 2k+1<2^(m+1) ==> 2k+2=<2^(m+1) ==> k+1=<2^m alors par hypothèse f(k+1)=k+1 et f(k)=k or 2k<n<2(k+1) d'où 2k<f(n)<2(k+1) ==> f(n)=2k+1=n
Accueil 
