Comment démontrer une identité… : En donnant un argument combinatoire… — Tle spé maths | MetMat

Comment démontrer une identité combinatoire ?

En donnant un argument combinatoire (compter le même ensemble de deux façons différentes)

Démontrer une identité combinatoire en exhibant un ensemble dénombré de deux façons différentes qui correspondent aux deux membres.

Que ferais-tu face à un exercice de ce type ?

Démontrer combinatoirement que $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$ .

L'objectif

Démontrer une identité combinatoire en exhibant un ensemble dénombré de deux façons différentes qui correspondent aux deux membres.

Le principe

Si deux expressions dénombrent le même ensemble, elles sont égales : on cherche donc un problème de comptage naturel dont les deux membres sont deux stratégies de résolution.

La méthode

1
Identifier un ensemble $E$ dont le cardinal est naturellement lié à l'un des membres de l'identité (souvent le membre le plus simple).
2
Compter $|E|$ d'une première façon pour retrouver le membre gauche, puis d'une seconde façon (en partitionnant ou en changeant l'ordre du choix) pour retrouver le membre droit.
3
Conclure : puisque les deux dénombrements comptent le même ensemble, les deux membres sont égaux.

Pour comprendre, fais des exercices !

Exercice d'exemple

Démontrer combinatoirement que $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$ .

Étape 1 —

Identifier un ensemble

E

dont le cardinal est naturellement lié à l'un des membres de l'identité (souvent le membre le plus simple).

Soit $E$ l'ensemble de tous les sous-ensembles d'un ensemble $A$ à $n$ éléments. Clairement $|E| = 2^n$ (chaque élément est soit inclus, soit exclu).

Étape 2 —

Compter

|E|

d'une première façon pour retrouver le membre gauche, puis d'une seconde façon (en partitionnant ou en changeant l'ordre du choix) pour retrouver le membre droit.

On peut aussi partitionner $E$ selon la taille $k$ du sous-ensemble : il y a $\binom{n}{k}$ sous-ensembles de taille $k$ , donc $|E| = \sum_{k=0}^{n}\binom{n}{k}$ .

Étape 3 —

Conclure : puisque les deux dénombrements comptent le même ensemble, les deux membres sont égaux.

Les deux dénombrements donnent $|E|$ , donc $\sum_{k=0}^{n}\binom{n}{k} = 2^n$ .

$\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.