1. Introduction

Les méthodes de démonstration en combinatoire permettent d’établir des propriétés sur le dénombrement d’ensembles ou de structures combinatoires. Deux approches essentielles sont :

• La démonstration par récurrence
• La méthode combinatoire

2. La démonstration par récurrence

2.1 Principe de la récurrence

Elle consiste à prouver qu’une propriété P(n) est vraie pour tout entier naturel n à l’aide de deux étapes :

1. Vérifier la propriété pour un cas de base (généralement n=0 ou n=1).
2. Supposer qu’elle est vraie pour un entier n=k et en déduire qu’elle l’est également pour n=k+1.

2.2 Exemple

Propriété : La somme des n premiers termes de la suite \((u_n)\) définie par \(u_n = 2^n\) est : \[ \sum_{i=1}^n u_i = 2^{n+1} - 2 \]

1. Vérification pour n=1 : \[ u_1 = 2^1 = 2 \] \[ \sum_{i=1}^1 u_i = 2 \] Vérifié.
2. Supposons la propriété vraie pour n=k : \[ \sum_{i=1}^k u_i = 2^{k+1} - 2 \]

   Pour n=k+1 : \[ \sum_{i=1}^{k+1} u_i = \sum_{i=1}^k u_i + u_{k+1} = (2^{k+1} - 2) + 2^{k+1} = 2 imes 2^{k+1} - 2 = 2^{k+2} - 2 \] Ce qui vérifie la propriété pour n=k+1.

Donc, par récurrence, la propriété est vraie pour tout n.

3. La méthode combinatoire

3.1 Principe

Elle repose sur une interprétation concrète du problème, en comptant directement le nombre d’éléments d’un ensemble ou en établissant un lien avec une autre enumeration connue.

3.2 Exemple

Calculer le nombre de façons de choisir 3 éléments distincts parmi 5 : \[ inom{5}{3} = rac{5!}{3!(5-3)!} = 10 \]

Interprétation : Il y a 10 sous-ensembles de taille 3 dans un ensemble de 5 éléments. La méthode consiste à compter directement ou à utiliser la formule.

4. Conclusion

Les démonstrations par récurrence sont utiles pour prouver des propriétés mathématiques généralisées, tandis que la méthode combinatoire permet une compréhension concrète et intuitive des dénombrements.