Démonstrations par récurrence et méthode combinatoire en combinatoire

Ce cours explique comment démontrer des propriétés en utilisant la récurrence et la méthode combinatoire.

Objectifs

Démonstration par récurrence : Montrer qu'une propriété est vraie pour un premier cas, puis que si elle est vraie pour un cas n, alors elle l'est pour n+1.
Formulaire générique : Si une propriété P(n) est vraie pour n=1, et que \[ P(n) \Rightarrow P(n+1) \] alors, par principe de récurrence, elle est vraie pour tout n ≥ 1.
Méthode combinatoire : Compter le nombre d'objets en décomposant en sous-ensembles ou en utilisant des formules, comme la formule du nombre de combinaisons \( \binom{n}{k} \).

On souhaite démontrer que pour tout entier naturel n ≥ 1, \[ 1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}. \]

Étape 1 : Cas de base (n=1)

Calculons le côté gauche : \( 1 = \frac{1 \times (1+1)}{2} = 1. \)

Cas vérifié : la propriété est vraie pour n=1.

Étape 2 : Hypothèse de récurrence

Supposons qu'elle est vraie pour un certain n ≥ 1, \[ 1 + 2 + ... + n = \frac{n(n+1)}{2}. \]

Étape 3 : Passage à n+1

Calculons la somme jusqu'à n+1 :

\[ 1 + 2 + ... + n + (n+1) = \frac{n(n+1)}{2} + (n+1). \]

Factorisons : \[ \frac{n(n+1)}{2} + (n+1) = (n+1) \left( \frac{n}{2} + 1 \right) = (n+1) \frac{n+2}{2}. \]

Donc, \[ 1 + 2 + ... + n + (n+1) = \frac{(n+1)(n+2)}{2}. \]

Ce qui montre que la formule est vraie pour n+1 si elle l'est pour n, par conséquent, par principe de récurrence, elle est vraie pour tout n ≥ 1.

Voir la solution

Les étapes montrent clairement la validation du cas de base, l'hypothèse, puis la démonstration du pas inductif.

Quelle est la première étape dans une démonstration par récurrence ?

La première étape est de vérifier la propriété pour le cas de départ, ici n=1, ce qui établit la base de la récurrence.

Calculons le nombre de façons de choisir 3 éléments parmi n, \( \binom{n}{3} \), avec la formule :

Formule

\( \binom{n}{k} = \frac{n!}{k!(n-k)!} \)

Par exemple, pour \( n=5 \), on a :

\[ \binom{5}{3} = \frac{5!}{3!2!} = \frac{120}{6 \times 2} = 10. \]

Les méthodes combinatoires permettent aussi d’établir des identités, comme :

Identité

\[ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \]

Quelle formule exprime l'identité de Pascal ?

La formule de Pascal, ou identité de Pascal, s’écrit \( \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \).

La démonstration par récurrence permet de prouver une propriété pour tous les entiers naturels à partir d’un cas initial.
La méthode combinatoire s’appuie sur le comptage précis d’ensembles d’objets.
Les identités de Pascal et autres formules sont essentielles dans la simplification des calculs.

Démonstration par récurrence

Vérifier le cas initial, puis prouver la propriété pour n+1 à partir de n

Méthode combinatoire

Compter en décomposant ou utilisant des formules, notamment \( \binom{n}{k} \)

Identité de Pascal

\[ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \]