1 Echauffement

Documents
5 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Licence, Supérieur, Licence (bac+3) Université de Nice – Sophia Antipolis Licence Math-Info 2 Outils Formels pour l'Informatique 2011–2012 TD n4 Récurrence et Induction 1 Echauffement Exercice 1) Définir par induction l'ensemble des nombres entiers (non négatifs) multiples de 3 base : 0 ∈ P ; règle : si x ∈ P , alors x+ 3 ∈ P Exercice 2) Montrer que quelque soit n ≥ 0, n < 2n base : pour n = 0 on a 0 < 20 = 1 ; pas inductif : pour tout n ≥ 0, supposons n < 2n et prouvons que n+ 1 < 2n+1.
  • outils formels pour l'informatique
  • hypothèse de récurrence n3
  • hypothèse de récurrence
  • licence math-info
  • mots
  • mot
  • exercice
  • exercices

Sujets

Informations

Publié par
Nombre de lectures 59
Langue Français
Signaler un problème
UniversitÉ de Nice – Sophia Antipolis Outils Formels pour l’Informatique TD n4 RÉcurrence et Induction
1 Echauffement
Licence Math-Info 2 2011–2012
Exercice 1)DÉfinir par induction l’ensemble des nombres entiers (non nÉgatifs) multiples de3
base :0P; rÈgle : sixP, alorsx+ 3P
n Exercice 2)Montrer que quelque soitn0,n <2
0n base : pourn= 0on a0<12 =; pas inductif : pour toutn0, supposonsn <2et prouvons que n+1nn n+1 n+ 1<2. On a par hypothÈse de rÉcurrencen+ 1<12 +<22 =2.
n Exercice 3)Montrer que pour toutn4,2< n!
4n base :pourn= 4on a162 =< n! = 24; pas inductif : pour toutn4, supposons2< n!et n+1n+1n prouvons que2<(n+ 1)!. On a par hypothÈse de rÉcurrence2 =22<2n!< nn! = (n+ 1)!
3 Exercice 4)Montrer que pour toutn0,n+ 2nest divisible par3.
3 base : pourn= 0on an+ 2n= 0qui est divisible par3; pas inductif : pour toutn0, supposons 3 33 n+ 2ndivisible par 3 et prouvons que(n+ 1)+ 2(n+ 1)est divisible par 3. On a(n+ 1)+ 2(n+ 1)= 2 32 32 (n+ 1)(n+ 2n+ 1) + 2n=+ 2n+ 3n+ 3n+ 1 + 2n+ 2= (n+ 2n) + 3(n+n+ 1). Par 3 32 hypothÈse de rÉcurrencen+ 2nest divisible par 3 et donc(n+ 2n) + 3(n+n+ 1)est divisible par 3.
Exercice 5)Etudier sur le cours la dÉmontration de la propriÉtÉDeux mots commutent si et seulement si ils sont puissance d’un mme mot
Ce thÉorÈme est dÛ À Roger Lyndon et Marcel-Paul Schutzenberger (1962).
Exercice 6)Donner une dÉfinition inductive de l’ensemble des nombres entiers pairs
base :0P; rÈgle : sixP, alorsx+ 2P
Exercice 7)CaractÉriser le sous ensemble deNdÉfini inductivement par • B={1} L’opÉration unairef:x72x