Menu
  1. Toutes les matières
  2. Maths
  3. Prépa HEC

Chapitre 1 :
Éléments de logique et raisonnement par récurrence

Éléments de logique et raisonnement par récurrence
I

Éléments de logique

Définition : Les quantificateurs
  • Le symbole `AA` signifie quel que soit ou pour tout.

  • Le symbole `EE` signifie il existe au moins un ou on peut trouver un.

Les quantificateurs sont toujours utilisés en début de phrases mathématiques et suivis d'expressions mathématiques.

Définition : Conditions nécessaires et conditions suffisantes

Soient A et B deux propositions.

  • A est une condition nécessaire de B si dès que B est vraie, alors A est vraie.

  • A est une condition suffisante de B si dès que A est vraie alors B est vraie.

Méthode
  • Pour infirmer une proposition universelle : utiliser un contre-exemple

  • Raisonnement par disjonction des cas : pour montrer qu'une proposition est vraie pour tous les éléments d'un ensemble `E`, montrer qu'elle est vraie pour tous les éléments de sous-ensembles disjoints de `E`.

  • Recours à la contraposée : en considérant deux propositions A et B, si A implique B, en déduire que si non-B alors non-A

  • Raisonnement par l'absurde : si on veut montrer qu'une propriété P est vraie, montrer que la proposition non-P mène à une absurdité

II

Raisonnement par récurrence

Théorème : Principe de récurrence

On considère comme définie pour tout entier `n>=n_0` une propriété `P_n`. Si :

  • `P_(n_0)` est vraie
  • `AAn>=n_0`, `P_n` vrai implique `P_(n+1)` vraie.

Alors `AAn>=n_0` la propriété `P_n` est vraie.

Exemple

On montre par récurrence que `AAninN`, `2^n>=n+1`.

  • Initialisation :

On vérifie que cette inégalité est vraie au rang `n=0`.

  • Hérédité :

On suppose qu'à un certain rang `n`, on a `2^n>=n+1`.
On montre alors qu'au rang `n+1`, on a `2^(n+1)>=n+2`.

En effet :
`2^(n+1)=2*2^n`
Donc `2^(n+1)>=2(n+1)=2n+2`
Or `2n+2-(n+2)=n>=0`
Donc `2n+2>=n+2`

Ce qui nous amène à l'inégalité suivante :
`AAninN` `2^(n+1)>=n+2`.

  • Conclusion :

On déduit du principe de récurrence : `AAninN`, `2^n>=n+1`.

Théorème : Principe de récurrence double

Initialisation : avec les deux premiers rangs

Hérédité : on suppose la propriété vraie à des rangs `n` et `n+1`, on la montre alors au rang `n+2`.

Conclusion : on déduit du principe de récurrence double que la propriété est vraie à tous les rangs.

Théorème : Principe de récurrence totale

Initialisation : avec le premier rang

Hérédité : on suppose la propriété vraie au premier rang jusqu'au rang `n`, on la montre alors au rang `n+1`.

Conclusion : par le principe de récurrence totale, la propriété est vraie à tous les rangs.

Chapitre suivant : Ensembles, parties d'un ensemble et applications >