Des exercices et sujets corrigés pour s’entraîner.
Déterminer toutes les fonctions f: N ⟶ N
Telles que:
∀ n ∈ IN :
f(2n) = 2f(n) & f(2n + 1) = 2f(n) + 1
Solution:
Montrons que: ∀ n∈IN f(n)=n
On peut procéder par utiliser la récurrence forte.
– Initialisation :
On a f(2*0)=2f(0)
C-à-d f(0)=2f(0)
Donc f(0)=0
-Hérédité :.
Soit n un entier naturel, supposons que pour tout entier naturel k≤n on a f(k)=k, et montrons que ceci implique que f(n+1)=n+1 (*)
Si n est pair
On note n=2k
Alors f(n+1)=f(2k+1)=f(2k)+1=2k+1=n+1 (**)
Si n est impair
On note n=2k+1
D’où f(n+1)=f(2(k+1))=2f(k+1)
Puisque k+1<n
On obtient f(k+1)=k+1
Alors f(n+1)=2k+2=(2k+1)+1=n+1
Ainsi, d’après les résultats de (*) et (**) notre hérédité est vraie.
-Conclusion :
D’après le principe de récurrence forte
quel que soit n appartenant à IN, f(n)=n
Donc f=id c’est l’application identité CQFD.
Autre Réponse:
soit k un entier naturel quelconque
on pose la propriété P(k) : f(k)=k
* tout d’abord P(0)=0 et vraie
en effet f(0)=f(2*0)=2f(0) ==> f(0)=0
* soit n∈IN, supposons que la propriété P(k) est vraie jusqu’à l’ordre n.
et montrons qu’il est vraie aussi au rang suivant.
si n=2p alors f(n+1)=f(2p+1)=2f(p)+1 comme p=<n
d’après l’hypothèse de récurrence on ait f(p)=p
il s’ensuite que f(n+1)=2p+1=n+1 si n=2p+1
alors f(n+1)=f(2p+2)=2f(p+1)
comme p+1 =< n
d’après l’hypothèse de récurrence on ait f(p+1)=p+1
par conséquent f(n+1)=2p+2=(2p+1)+1=n+1. _
conclusion: quelque soit n dans IN P(n) est vraie,
autrement dit f=Id c’est l’application identité.
2 éme méthode directe ( un peu constructive )
soit n un entier naturel quelconque.
on sait que:
* f(4n)=2f(2n)=4f(n)
* f(4n+1)=f(2(2n)+1)=2f(2n)+1=4f(n)+1
* f(4n+3)=f(4n+2+1)=f(2(2n+1)+1)
=2f(2n+1)+1=2(2f(n)+1)+1=4f(n)+3
* f(4n+2)=f(2(2n+1))=2f(2n+1)=2(2f(n)+1)=4f(n)+2
si l’on travaille comme un entier résidu modulo 4
on peut constater directement que:
f(0mod[4])=0mod[4]
f(1mod[4])=1mod[4]
f(2mod[4])=2mod[4]
f(3mod[4])=3mod[4]
ce qui veut dire que f =Id .
By F.El Maftouhi
Olympiade de Maths, c’est une gymnastique de l’esprit, Ce qu’il faut c’est 4math.net et beaucoup de pratiques
4math.net Le première clé pour être bon en maths