Un petit tour de magie pour illustrer la méthode de preuve par récurrence

Si vous voulez surprendre de manière amusante vos élèves, montrez leur vos talents de télépathe à l’aide du petit tour suivant. Il s’agit pour vous de découvrir un nombre qu’ils vont calculer secrètement à partir d’un naturel n. Leur calcul consiste à décomposer n en une somme de deux termes, à retenir le produit de ceux-ci, à faire de même avec les termes, à répéter l’opération jusqu’à ce que tous les termes obtenus soient égaux à 1 (qu’on ne décompose pas) et à additionner tous les produits retenus à chaque étape. Ils vous communiquent alors n et attendent que vous « deviniez » cette somme.

Avec 7, on a par exemple les décompositions

7=4+3=(2+2)+(2+1)=(1+1)+(1+1)+(1+1)+1

et la somme des produits successifs — la somme à deviner — est

12+4+2+1+1+1=21

Je me suis récemment livré avec mes étudiants à ce petit « tour de magie », lors une leçon d’introduction à la méthode de démonstration par récurrence. J’étais fort intéressé à découvrir leurs réactions. Passé un petit effet de surprise provoqué par cette façon inhabituelle d’introduire une propriété, ils ont rapidement compris que le tour fonctionne parce que la somme s(n) obtenue dépend uniquement de l’entier n : Il doit y avoir une formule! se sont-ils exclamés. Je le leur ai confirmé tout en leur demandant de la trouver. La réponse est venue sans tarder, pour ne pas dire a fusé, l’un d’eux ayant aussitôt pensé à la suite particulière de décompositions

n=1+n-1=1+(1+n-2)=\cdots

laissant ainsi présager que la valeur cherchée est la somme des entiers de 1 à n-1 :

(1) s(n)=\frac 1 2 n(n-1)

Nous avons alors établi cette égalité, par récurrence sur n.

La phase d’induction consiste à montrer que

Si l’égalité (1) est vraie pour les valeurs de n inférieures à m, alors elle est vraie lorsque n=m.

Voici comment nous avons vérifié cela. Notons m=p+q la première étape d’une suite de décompositions de m. Les suivantes donnent des suites de décompositions de p et de q. Ainsi

s(m)=pq+s(p)+s(q)

Puisque p,q sont strictement plus petits que m, il résulte de l’hypothèse de récurrence que

s(m)=\frac 1 2(2pq+p(p-1)+q(q-1))=\frac 12\left((p+q)^2-(p+q)\right)=\frac 12 m(m-1)

Cette démonstration nous impose de poser s(1)=0. Ceci ne découle pas formellement des règles du tour de magie mais présente par ailleurs l’avantage de régler la phase d’initialisation de la récurrence — le cas de base comme on dit souvent.

La cause est donc entendue.

Ce que je trouve intéressant, méthodologiquement, dans cette démonstration, c’est que la phase d’induction utilise toutes les valeurs plus petites que m et pas seulement m-1, comme c’est souvent le cas dans les illustrations de la méthode de démonstration par induction.

Cela dit, voici une explication géométrique de la formule (1). Elle est illustrée dans le dessin suivant pour n=7.

magie

On considère un carré pavé avec n\times n carrés. La première étape n=p+q d’une suite de décompositions de n donne le produit pq que l’on interprète comme l’aire d’une partie rectangulaire du carré (en brun sur l’exemple). Les étapes suivantes ajoutent des aires de rectangles accolés aux côtés de ceux déjà construits. Dans l’exemple, p=4 a été décomposé en 2+2, ce qui rajoute les quatre carrés dessinés en bleu. Le processus ce poursuit jusqu’à obtenir tous les carrés situés au-dessus de la diagonale principale, en nombre

\frac 12 (n^2-n).

😉

7 réflexions sur “Un petit tour de magie pour illustrer la méthode de preuve par récurrence

  1. Sympa et assez inhabituel en effet… De quoi sortir les étudiants de leur torpeur. Et l’interprétation géométrique ajoute encore un intérêt au problème.
    🙂

  2. J’aime beaucoup ces approches par « tâtonnement expérimental » pour faire comprendre des notions mathématiques.
    Concernant la particularité de ce type de raisonnement par récurrence, j’avais trouvé dans un manuel (ou dans le cours d’un prof, je ne me rappelle plus très bien) de Terminale S deux définitions pour la récurrence :
    – la récurrence faible qui ne fait intervenir une seule hypothèse sur le rang précédent pour la démonstration de l’hérédité
    – la récurrence forte (comme ici) dans laquelle, pour démontrer l’hérédité, on suppose que la propriété P(n) est vraie pour tout k plus petit que n, et non pas pour seulement n.

  3. C’est ce qu’on appelle je crois une «récurrence forte».
    Je n’avais pas beaucoup d’exemples de récurrences fortes. Un grand merci pour celui-ci !

  4. On peut formuler le théorème de récurrence forte ainsi :
    (\forall n\in\mathbf N, (\forall k<n, P(k))\Rightarrow P(n))\Rightarrow (\forall n\in\mathbf N, P(n)). Ou en français : si une propriété est vraie pour un entier dès qu'elle est vraie pour tous ses prédécesseurs, alors cette propriété est vraie pour tous les entiers.

    C'est amusant car la fameuse "initialisation" de la récurrence semble avoir disparu🙂

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s