1. Introduction

Les méthodes de démonstration en combinatoire et dénombrement permettent d'établir des identités ou des propriétés sur les nombres et arrangements. Nous étudierons deux méthodes principales : la démonstration par récurrence et la méthode combinatoire.

2. La démonstration par récurrence

2.1 Principe

La récurrence consiste à prouver qu'une propriété \(P(n)\) est vraie pour tout entier naturel \(n\) en suivant trois étapes :

1. Cas de base : Vérifier que \(P(n_0)\) est vraie pour un entier de départ \(n_0\).
2. Hypothèse de récurrence : Supposer que \(P(n)\) est vraie pour un certain \(n \geq n_0\).
3. Étape de récurrence : Montrer que cette hypothèse implique que \(P(n+1)\) est vraie.

Si ces étapes sont satisfaites, alors \(P(n)\) est vraie pour tout \(n \geq n_0\).

2.2 Exemple

Propriété : Pour tout \(n \geq 1\), \(\sum_{k=1}^n k = rac{n(n+1)}{2}\).

Preuve :

1. Cas de base : \(n=1\) : \(\sum_{k=1}^1 k = 1 = rac{1 imes 2}{2}\).
2. Hypothèse : supposer que pour un certain \(n\), \(\sum_{k=1}^n k = rac{n(n+1)}{2}\).
3. Étape : montrer que \(\sum_{k=1}^{n+1} k = rac{(n+1)(n+2)}{2}\).

\( \sum_{k=1}^{n+1} k = \sum_{k=1}^n k + (n+1) \)

\(= rac{n(n+1)}{2} + (n+1) = rac{n(n+1) + 2(n+1)}{2} = rac{(n+1)(n + 2)}{2}\).

La propriété est donc démontrée par récurrence.

3. La méthode combinatoire

3.1 Principe

La méthode combinatoire consiste à compter explicitement le même ensemble de façon différente pour établir une égalité ou une propriété.

Elle repose sur la bijection ou la correspondance entre deux ensembles finis.

3.2 Exemple

Propriété : Le nombre de manières de choisir 2 éléments dans un ensemble de \(n\) éléments, avec ordre (c'est-à-dire, permutations à deux éléments), est égal à \(n(n-1)\).

Explication :
Le nombre de permutations de 2 éléments parmi \(n\) est égal au nombre de façons de choisir le premier puis le second :

\(n imes (n-1)\).

Ce nombre peut aussi être obtenu en utilisant la formule des combinaisons et permutant :

\( C(n,2) imes 2! = rac{n(n-1)}{2} imes 2 = n(n-1). \)