1 Echauffement

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

• Mathématiques
• Lyndon
• Schutzenberger
• Universidad de Niza Sophia Antipolis
• Antipolis
• Récurrence
• Exercice
• Formel
• Outil
• Licence
• Informatique

Informations

• Publié par: datat
• Nombre de lectures: 59
• Langue: Français

Extrait

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 :0∈P; rÈgle : six∈P, alorsx+ 3∈P

n Exercice 2)Montrer que quelque soitn≥0,n <2

0n base : pourn= 0on a0<12 =; pas inductif : pour toutn≥0, supposonsn <2et prouvons que n+1nn n+1 n+ 1<2. On a par hypothÈse de rÉcurrencen+ 1<12 +<2∙2 =2.

n Exercice 3)Montrer que pour toutn≥4,2< n!

4n base :pourn= 4on a162 =< n! = 24; pas inductif : pour toutn≥4, supposons2< n!et n+1n+1n prouvons que2<(n+ 1)!. On a par hypothÈse de rÉcurrence2 =2∙2<2∙n!< n∙n! = (n+ 1)!

3 Exercice 4)Montrer que pour toutn≥0,n+ 2nest divisible par3.

3 base : pourn= 0on an+ 2n= 0qui est divisible par3; pas inductif : pour toutn≥0, 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 :0∈P; rÈgle : six∈P, alorsx+ 2∈P

Exercice 7)CaractÉriser le sous ensemble deNdÉfini inductivement par • B={1} •L’opÉration unairef:x7→−2x