Carnet de Route du Séminaire de la Détente Mathématique

Les Formules Magiques

Le 3 mars 2021  - Ecrit par  Léo Dort Voir les commentaires (1)

Nous allons voir qu’il n’est pas nécessaire de faire des calculs longs et fastidieux pour démontrer des formules. Parfois il suffit de raconter des histoires et de faire des dessins !

C’est ce type de formules que nous allons appeler Formules Magiques.

Des Histoires ...

On note ${n \choose k}$, et on dit « $k$ parmi $n$ », le nombre de parties à $k$ éléments dans un ensemble à $n$ éléments. Mais voyons-le plutôt comme le nombre possibles d’assemblées de $k$ personnes dans une population de $n$ personnes.

Une mise en jambe : la formule du triangle de Pascal

Formule Magique 1 : \[ {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}. \]

Un village de $n$ habitants souhaite élire $k$ personnes au conseil municipal. Bob, un citoyen du village se demande combien de conseils municipaux il est possible de constituer.
Bien sûr, au vu de la définition donnée ci-dessus, il y en ${n \choose k}$.

Mais dans chacun de ces conseils municipaux :

  • soit Bob fait partie du conseil, et dans ce cas-là, il reste à élire $k-1$ personnes parmi les $n-1$ habitants restants. Ce qui fait ${n-1 \choose k-1}$ possibilités ;
  • soit Bob ne fait pas partie du conseil, et dans ce cas-ci, il faut élire les $k$ conseillers municipaux parmi les $n-1$ villageois restants. Ce qui fait ${n-1 \choose k}$ possibilités.

On retrouve donc bien la formule du triangle de Pascal :

Une formule un peu plus compliquée

Formule Magique 2 : \[ k {n \choose k} = n {n-1 \choose k-1}. \]

Comme avant, nous allons nous intéresser au nombre de conseils municipaux, mais cette fois-ci avec un maire à sa tête. On peut constituer un tel conseil de deux manières différentes :

  • on constitue le conseil, puis on choisit le maire parmi les $k$ membres du conseil. Ce qui nous donne
  • ou bien on élit d’abord le maire (qui fait parti du conseil municipal), puis on élit le reste du conseil parmi les villageois restants. Ce qui nous donne

En résumé, on retrouve bien notre formule magique
\[ k {n \choose k} = n {n-1 \choose k-1}. \]

Une formule difficile

Terminons par une formule beaucoup moins intuitive.

Formule Magique 3 : Si $k$ est un entier compris entre $0$ et $\frac{n}{2}$, alors \[ \sum_{m=k}^{n-k} {m \choose k} {n-m \choose k} = {n+1 \choose 2k+1}. \]

Supposons qu’un nouvel habitant, disons Michel, s’installe au village. Il y a donc à présent $n+1$ villageois. Très persuasif, Michel convainc le village d’élire un nouveau conseil municipal de $2k+1$ habitants. Il y a donc ${n+1 \choose 2k+1}$ conseils municipaux possibles.

Mais Michel propose une toute nouvelle méthode d’élection.

  • Étape 1 : on classe les habitants par âge croissant.
  • Étape 2 : on tire une personne au sort qui fera partie automatiquement du conseil. On appelle cette personne pivot.
    Mais attention, cet habitant pivot ne doit être ni trop jeune, ni trop âgé ! Il doit y avoir au moins $k$ personnes plus jeunes, et au moins $k$ personnes plus âgées parmi le reste des habitants.
    Dans le classement des âges, le pivot à la place $m+1$, où $m+1$ doit donc satisfaire :
  • Étape 3 : les $m$ personnes plus jeunes que le pivot élisent entre elles une assemblée de $k$ habitants qui siègeront au conseil, et les $n-m$ habitants plus âgées que le pivot font de même.
  • Étape 4 : le conseil municipal est alors formé par le pivot, et des deux assemblées précédentes.

Donc si le pivot est à la pace $m+1$ dans le classement des âges, alors on peut constituer

selon cette méthode d’élection.

Puis, comme on l’a remarqué plus haut, le pivot doit être entre les places $k$ et $n-k$. Par conséquent, on peut constituer

D’où la formule magique
\[ \sum_{m=k}^{n-k} {m \choose k} {n-m \choose k} = {n+1 \choose 2k+1}. \]

Exercice

Retrouvez les formules magiques précédentes par le calcul.

... et des Dessins

Paver des rectangles

Reconnaissez-vous cette suite de nombres ?
\[ 0, \quad 1, \quad 1, \quad 2, \quad 3, \quad 5, \quad 8, \quad 13, \quad \dots \]

Il s’agit de la célèbre suite de Fibonacci, et on la définit comme suit :
\[ F_0 = 0, \quad F_1 = 1, \quad \textrm{ et } \quad F_{n+2} = F_{n+1} + F_{n} \:\:\: \textrm{ si } n \geq 0. \]

En faisant quelques calculs (qu’on laisse au lecteur intéressé), on peut montrer que pour tout entier $n \geq 0$ :
\[ F_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right). \]

C’est une belle formule, mais elle n’est pas magique.. Intéressons-nous alors à la formule suivante qui est cette-fois magique.

Formule Magique 4 : \[ F_{n+m+1} = F_{m+1} F_{n+1} + F_m F_n. \]

A priori, rien d’évident. Mais nous allons voir que la suite de Fibonacci possède un lien avec les pavages !

On souhaite paver un rectangle de taille $n$, c’est-à-dire un rectangle de $n$ cases (ou $n$ cellules) disposés sur $1$ ligne

avec les deux briques élémentaires suivantes :

Exemple de pavage du rectangle de taille $9$ :

Pour la suite, on pose $r_0 = 0$, et si $n\geq1$, alors on note $r_n$ le nombre de pavages du rectangle de taille $n$.

Ainsi par l’exercice précédent, on a
\[ r_1 = 1, \quad r_2 = 2, \quad r_3 =3, \quad r_4 = 5 \quad \dots \]
Ça ne vous rappelle rien ?

Il semblerait que pour tout entier $n\geq1$
\[ r_n = F_{n+1}. \]

En effet, un pavage d’un rectangle de taille $n+2$ peut être décrit en fonction de la dernière brique élémentaire qui la compose.

  • Soit cette dernière brique est . Dans ce cas, il reste à paver un rectangle de taille $n+1$. Il y a $r_{n+1}$ pavages possibles pour ce rectangle.
  • Soit cette dernière brique est en avant dernière position, et dans ce cas, il reste à paver un rectangle de taille $n$. Il y a $r_n$ pavages possibles pour ce dernier.

En résumé, on a
\[ r_{n+2} = r_{n+1} +r_n. \]
Et puisque $r_0 = F_1$, $r_1 = F_2$ et que la suite $(r_n)_{n\geq0}$ satisfait la même réaction de récurrence que la suite de Fibonacci, on en déduit que $r_n = F_{n+1}$.

Il en découle que pour déduire des propriétés sur la suite de Fibonacci, on peut étudier le nombre de pavages des rectangles !

Formule Magique 5 : \[ r_0 + r_1 + \dots + r_n = r_{n+2}-1. \]

Considérons un rectangle de taille $n+2$. Alors $r_{n+2} - 1$ correspond au nombre total de pavages de ce rectangle, sans compter celui où il n’y a que des briques .

Par ailleurs s’il n’y pas QUE des briques , alors il y a au moins une brique dans le pavage. Intéressons-nous à l’emplacement de la dernière de ces briques .

  • Si elle est en dernière position, alors il existe un rectangle de taille $n$ à paver, ce qui fait $r_n$ possibilités.
  • Si elle est avant-dernière position, alors il reste un rectangle de taille $n-1$ à paver, ce qui représente $r_{n-1}$ possibilités.
  • Et ainsi de suite jusqu’à ce que la dernière brique soit en première position.

Ainsi en distinguant les différents cas possibles, on obtient bien :
\[ r_{n+2}-1 = r_0 + r_1 + \dots + r_n. \]

Revenons à la formule $F_{n+m+1} = F_{m+1}F_{n+1} + F_m F_n$. D’après ce qu’on a vu, il est équivalent de montrer que
\[ r_{n+m} = r_m r_n + r_{n-1}r_{m-1}. \]
Pour démontrer cette formule, introduisons une nouvelle notion.

Définition : On dit qu’un pavage est cassable au niveau $k$, si on peut le séparer en deux pavages, le premier portant sur les $k$ premières cellules et le second sur les cellules restantes.

Exemple : Le pavage ci-dessous est cassable en 3, mais pas en 4.

Nous pouvons à présent démontrer notre formule.

$r_{n+m}$ est le nombre de pavages d’un rectangle de taille $n+m$. On réalise alors une disjonction des cas selon que le pavage est cassable en $n$ ou non !

  • Si le pavage est cassable en $n$, alors par définition il est la concaténation d’un pavage de taille $n$, et d’un pavage de taille $m$.

    Il y a donc $r_n r_m$ possibilités.

Puis remarquons que :

Propriété : Un pavage n’est pas cassable en $k$ si, et seulement si, la $k$-ième cellule du rectangle est la 1ère cellule d’une brique .
  • Par conséquent, si un pavage n’est pas cassable en $n$, alors en retirant cette brique problématique, on remarque que ce pavage est la concaténation d’un pavage de taille $n-1$, de la brique problématique , puis d’un pavage de taille $m-1$. Il y a donc $r_{n-1} r_{m-1}$ possibilités.

Ainsi on en conclut que
\[ r_{n+m} = r_n r_m + r_{n-1} r_{m-1}. \]
Et puisque $r_n = F_{n+1}$, on obtient alors notre formule magique
\[ F_{n+m+1} = F_{n+1} F_{m+1} + F_n F_m. \]

Paver des cercles

Pour terminer, connaissez-vous cette nouvelle suite de nombre ?
\[ 2, \quad 1, \quad 3, \quad 4, \quad 7, \quad 11, \quad 18, \quad \dots \]

Les termes suivants sont $29, 46,$ etc... Il s’agit de la célèbre suite de Lucas ! Elle est définie par la même relation de récurrence que la suite de Fibonacci, et seules les conditions initiales sont différentes :
\[ L_0=2, \quad L_1=1, \quad \textrm{ et } \quad L_{n+2}=L_{n+1} + L_{n} \: \textrm{ si } n\geq0. \]

Si nous avons décrit un lien entre la suite de Fibonacci et les pavages de rectangles, nous allons maintenant voir que la suite de Lucas a un lien avec les pavages de cercles.
Pour paver un cercle, on commence par le munir d’une origine.

Puis, si on coupe le cercle en $n$ parties égales (en partant de l’origine et en tournant dans le sens des aiguilles d’une montre par exemple), alors on pave les cercle avec des arcs élémentaires de 1 ou 2 morceaux.

Notons $c_n$ le nombre de pavages du cercles à $n$ cellules. Alors on peut montrer, de la même manière que précédemment, que pour tout entier $n\geq1$, on a
\[ c_n = L_n. \]

Exercice

A vous de le démontrer !

Nous avons vu que la suite de Lucas est liée à la suite de Fibonacci. Il est donc naturel de se demander quelle(s) relation(s) lie(nt)) les suites $(r_n)_{n\geq0}$ et $(c_n)_{n\geq0}$ ?

Remarquons que le pavage d’un cercle peut être de deux manières différentes.

  • Soit l’origine n’est pas contenue dans un arc élémentaire de taille 2. On dit que le pavage est en phase ;
  • Soit l’origine est contenue dans un arc élémentaire de taille 2. On dit alors que le pavage est déphasé.

Dans le premier cas, on déroule le cercle pour obtenir un rectangle de taille $n$ pavé.

Dans le second cas, on ne peut dérouler le cercle à partir de l’origine puisqu’il faudrait alors casser l’arc élémentaire de taille 2 qui la contient. On retire donc cet arc problématique, et on déroule le pavage restant pour obtenir un rectangle de taille $n-2$ pavé.

On en déduit ainsi notre dernière formule magique.

Formule magique 6 : Pour tout entier $n\geq2$, on a \[ c_n = r_n + r_{n-2}. \]

Vous pouvez trouver ici les notes manuscrites de cet exposé au format pdf, et cliquez pour en savoir plus sur le séminaire et la MMI.


Article édité par Laurent Bartholdi

Partager cet article

Pour citer cet article :

Léo Dort — «Les Formules Magiques» — Images des Mathématiques, CNRS, 2021

Commentaire sur l'article

  • Les Formules Magiques

    le 4 mars à 20:24, par santic

    Bonjour,
    Dans la suite de Fibonacci, il manque F4 = 3.
    Merci pour l’article.
    S.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Dossiers

Cet article fait partie du dossier «Carnets de route de la MMI» voir le dossier