Supposons que vous soyez à une fête avec neuf autres personnes et que tout le monde se serre la main exactement une fois. Combien de poignées de main ont lieu ?

C'est le « problème de la poignée de main » et c'est l'un de mes favoris. En tant que professeur de mathématiques, j'adore cela car il existe de nombreuses façons différentes de trouver une solution, et la diversité et l'interdépendance de ces stratégies illustrent magnifiquement le pouvoir de la pensée créative en mathématiques.

Une solution est la suivante : commencez par chaque personne serrant la main de chaque autre personne. Dix personnes, avec neuf poignées de main chacune, produisent 9 × 10 = 90 poignées de main au total. Mais cela compte chaque poignée de main deux fois – une fois du point de vue de chaque shaker – donc le nombre réel de poignées de main est de $latex frac{90}{2} = 45$. Un argument de comptage simple et charmant pour la victoire !

Il existe également une manière complètement différente de résoudre le problème. Imaginez que les invités arrivent un par un et qu'une fois arrivés, ils serrent la main de toutes les personnes présentes. La première personne n’a pas de main à serrer, donc dans une fête composée d’une seule personne, il n’y a aucune poignée de main au total. Maintenant, la deuxième personne arrive et serre la main de la première personne. Cela ajoute une poignée de main au total, donc dans une fête de deux personnes, il y a 0 + 1 = 1 poignée de main au total. Lorsque la troisième personne arrive et serre la main des deux premiers invités, cela ajoute deux poignées de main au total. L'arrivée de la quatrième personne ajoute trois poignées de main au total, et ainsi de suite.

Cette stratégie modélise la séquence de poignées de main de manière récursive, ce qui signifie que chaque terme de la séquence est défini par rapport à ceux qui le précèdent. Vous connaissez probablement la séquence de Fibonacci, la séquence récursive la plus célèbre de toutes. Il commence par 1, 1, 2, 3, 5, 8, 13, 21 et continue avec chaque terme suivant égal à la somme des deux précédents.

Comme nous le verrons ci-dessous, la récursivité est un cadre flexible et puissant pour réfléchir à un large éventail d’idées mathématiques. Et même si d’anciens érudits indiens comme Hemachandra sont réputés connaître ce type de séquences dès 1150, elles offrent encore aujourd’hui des défis intrigants aux mathématiciens.

Voyons comment la pensée récursive aide à résoudre le problème de la poignée de main. Si nous laissons $latex a_n$ égal au nombre de poignées de main à un moment donné n-personne partie, on peut représenter cette relation récursive avec la formule suivante :

$latex a_n = a_{n-1} + n–1$

Cela nous indique que le nombre de poignées de main à un moment donné n-person party ($latex a_n$) est égal au nombre de poignées de main à un (n − Fête de 1) personne ($latex a_{n-1}$) plus n − 1 poignée de main supplémentaire, capturant l'idée que lorsqu'une nouvelle personne arrive, elle ajoute un certain nombre de nouvelles poignées de main à celles qui ont déjà eu lieu.

Dans notre version particulière du problème de la poignée de main, nous voulons connaître $latex a_{10}$, le nombre de poignées de main lors d'une fête de 10 personnes, afin de constater que nous utilisons la relation récursive

$latex a_{10} = a_9 + 9$

Pour trouver la valeur de $latex a_{10}$, il suffit de connaître la valeur de $latex a_9$ et d'y ajouter 9. Comment trouver la valeur de $latex a_9$ ? En utilisant la récursion, bien sûr !

$latex a_9 = a_8 + 8$

Maintenant, pour trouver la valeur de $latex a_8$, nous devons trouver la valeur de $latex a_7$, ce qui nécessite de connaître $latex a_6$, et ainsi de suite. À ce stade, vous pourriez craindre que cela se poursuive éternellement dans une sorte de descente infinie, mais une fois que nous atteignons $latex a_1$, nous avons terminé, car nous savons qu'il n'y a aucune poignée de main au total lors d'une fête entre une seule personne.

$latex a_1 = 0$

Cette valeur initiale ou « graine » est une caractéristique clé d’une séquence récursive. Il garantit que ce processus de retour en arrière dans la séquence utilisant la relation récursive prendra fin. Une fois que vous avez atteint la valeur de départ, le retour en arrière s'arrête et vous pouvez ensuite avancer dans la liste pour obtenir la valeur souhaitée.

$latex a_1 = 0$

$latex a_2 = a_1 + 1 = 0 + 1 = 1$

$latex a_3 = a_2 + 2 = 1 + 2 = 3$

$latex a_4 = a_3 + 3 = 3 + 3 = 6$

$cdots en latex$

$latex a_{10} = a_9 + 9 = 36 + 9 = 45$

En parcourant la liste, nous constatons qu’il y a 45 poignées de main au total lors d’une fête de 10 personnes, ce qui est conforme à notre calcul initial. Si vous êtes comme mes étudiants, vous pourriez vous demander pourquoi nous avons besoin d'une autre façon de résoudre ce problème alors que nous connaissons déjà la réponse, d'autant plus que cette deuxième approche semble prendre plus de temps.

C'est une bonne question. Une réponse est que l’approche récursive nous donne une vision totalement différente de ce qui se passe dans ce problème, et que différentes perspectives sont utiles en mathématiques, comme en toutes choses. Ils nous donnent différentes opportunités de comprendre les concepts et nous permettent d'utiliser différents outils, ce qui peut nous aider lorsque nous sommes bloqués.

En particulier, la récursivité est utile car elle est présente partout en mathématiques. Cela se produit, par exemple, dans les relations linéaires que tout le monde apprend en cours de mathématiques – celles caractérisées par un taux de changement constant et représentées par des lignes dans le plan. Une fonction linéaire comme $latex f(x) = 3x + 5$ peut être considérée comme une formule récursive :

$latex a_0 = 5$

$latex a_n = a_{n-1} + 3$

Bien que la façon la plus évidente de penser à $latex f(2)$ puisse être que $latex f(2) = 3 fois 2 + 5 = 11$, une autre façon est que $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. La modélisation récursive de la caractéristique fondamentale des fonctions linéaires – le taux de changement constant – nous donne une autre façon de penser cette relation. La même chose peut être faite avec des fonctions exponentielles caractérisées par un changement multiplicatif constant.

La pensée récursive fonctionne également au-delà des séquences de nombres. Si vous avez déjà résolu un système d’équations, vous avez probablement appliqué une approche récursive. Pour résoudre le système

$latex 2x + y = 10$

$latex 3x – y = 5$

vous pouvez d'abord additionner les deux équations pour éliminer le y variable, ce qui donne l'équation $latex 5x = 15$. Résolvez ceci pour obtenir $latex x =$ 3, remplacez-le pour trouver $latex y = 4$, et vous avez terminé. Cette approche utilise un algorithme récursif, dans lequel la solution d'un système est construite à partir de la solution de systèmes connexes plus petits. Par exemple, pour résoudre un système 3 × 3, vous éliminez une variable pour la transformer en système 2 × 2, puis à nouveau pour la transformer en système 1 × 1. Cette équation unique facile à résoudre est comme la valeur initiale de ce processus récursif. Cela signale la fin du retour en arrière, et à partir de là, vous remontez la chaîne d'équations, tout comme dans une séquence récursive.

Il existe même des techniques de preuve récursive. Par exemple, une formule célèbre en géométrie est la formule de la somme des angles du polygone, qui dit que la somme des mesures des angles intérieurs d'un nLe polygone à côtés est $latex (n-2) fois 180^{circ}$. Une façon de prouver ce résultat est de commencer par un n-allez et imaginez ce qui se passerait si vous supprimiez un triangle.

Supprimer un triangle transforme le n-aller dans un (n − 1)-gon, et il supprime également 180 degrés de mesure d'angle intérieur. Il s'agit d'une relation récursive : la somme des angles intérieurs pour un n-gon est 180 degrés de plus que la somme des angles intérieurs pour un (n − 1)-gon. Pour établir le résultat général, continuez à supprimer les triangles jusqu'à ce que vous atteigniez la valeur de départ, ce qui dans cette situation se produit lorsque vous avez supprimé tous les triangles sauf trois. n-les sommets de Gon. À ce stade, le polygone initial a été réduit à un triangle dont la somme des angles intérieurs est connue pour être de 180 degrés. Remontez maintenant en ajoutant 180 degrés à chaque étape et vous obtiendrez la formule.

Pour en revenir à notre parti, le problème de la poignée de main lui-même nous montre ce qui est possible lorsque nous pensons de manière créative et que nous connectons ensuite ces multiples perspectives différentes d'un problème. Si nous jouons avec le modèle récursif pour notre séquence de poignées de main :

$latex a_1 = 0$

$latex a_n = a_{n-1} + n – 1$

un joli motif émerge :

$latex a_2 = a_1 + 1 = 0 + 1$

$latex a_3 = a_2 + 2 = 0 + 1 + 2$

$latex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$cdots en latex$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

Nous disposons désormais d’une façon nouvelle et générale d’appréhender le problème : le nombre de poignées de main dans une n-personne partie est égale à la somme du premier n − 1 entier positif.

Repensez à notre approche originale. Dans un n-fête personne, chaque personne serrera la main de l'autre n − 1 personne. Le produit $latex n (n-1)$ compte chaque poignée de main deux fois, donc le nombre total de poignées de main est $latex frac{n(n-1)}{2}$. Mais comme nos différentes méthodes comptent la même chose, elles doivent donner le même résultat. Cela signifie notamment :

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

En connectant différentes approches du problème de la poignée de main, nous obtenons une formule fermée pour la somme des premiers n − 1 entiers positifs. Mais nous obtenons encore plus : l'expression $latex frac{n(n-1)}{2}$ implique une fraction, mais comme elle est égale à une somme d'entiers, elle doit également être un entier. Cela prouve un simple fait de la théorie des nombres : pour tout entier n, $latex frac{n(n-1)}{2}$ est un entier.

Ce même type d’argument continue d’alimenter les mathématiques modernes. À titre d'exemple, les chercheurs du début des années 2000 a prouvé des résultats surprenants sur les séquences récursives dites séquences Somos en montrant qu'elles aussi comptent quelque chose. Grâce au pouvoir des connexions créatives, les mathématiciens ont une fois de plus découvert où ils pouvaient aller en comprenant d'où ils venaient.

Des exercices

1. Trouvez une formule fermée pour la séquence définie récursivement comme
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. À la fin de la colonne, l'expression $latex frac{n(n-1)}{2}$ s'est avérée être un entier même si l'expression implique une fraction, car $latex frac{n(n-1 )}{2}$ est le résultat du comptage de quelque chose. Il existe également un argument de théorie des nombres qui montre que cette expression doit être un nombre entier. Qu'est-ce que c'est?

3. Trouvez les premiers termes de la séquence récursive
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Trouvez les premiers termes de la séquence récursive
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$