Hypothèse de récurrence et abstraction : un exemple amusant

Mon propos est ici d’illustrer sur un exemple simple, et donc montrable à beaucoup d’étudiants, une manière d’utiliser l’abstraction pour résoudre un problème, objectif que je poursuivais d’ailleurs implicitement dans l’article précédent. Ceux d’entre vous qui s’y essayeront constateront sans doute qu’il est assez difficile de montrer, avec les seuls moyens de l’arithmétique élémentaire, que l’inégalité

2^n>n^5-3n^2

a lieu dès que l’entier positif n est assez grand. En remplaçant le membre de droite de cette inégalité par un polynôme P à coefficients entiers quelconques, on semble compliquer le problème en lui conférant une grande généralité mais l’article révèle qu’au contraire, cela donne accès à une démonstration simple de la propriété, basée sur une récurrence sur le degré de P. On voit bien ici comment joue l’abstraction : en faisant apparaître un paramètre absent du problème initial, elle permet d’utiliser une méthode indisponible pour attaquer directement le problème. Cela dit, cet exemple est un peu artificiel dans la mesure où, comme je le signale dans le billet, la propriété de dominance de l’exponentielle sur les puissances antagonistes donne une preuve qui tient en une ligne de l’inégalité considérée.

J’ai rencontré le problème qui suit sur le forum M@TH en Ligne et je ne lui ai pas trouvé d’autre solution que celle que je vais vous présenter ici : n est un entier positif, f est une fonction n fois dérivable de ]0,+\infty[ dans \mathbb C et il s’agit de montrer que

(1) \left(x^{n-1}f(x^{-1})\right)^{(n)}=(-1)^nx^{-(n+1)}f^{(n)}(x^{-1})

(n) désigne la dérivée n-ième.

L’égalité (1) est immédiate à vérifier directement lorsque f est une puissance x\mapsto x^\alpha (non nécessairement entière) et par extension, lorsqu’il est un polynôme, par linéarité des deux membres de (1). En procédant par récurrence sur n, on va vérifier qu’elle est vraie pour la fonction exponentielle, par une tactique que nous réutiliserons pour le cas général. Je vous laisse le soin de vérifier les cas de base n=1,2 et passe à l’induction : on suppose (1) vrai pour f: x\mapsto e^x et lorsque n vaut p-2 et p-1. Nous avons alors, en effectuant une première dérivation (dénotée par une apostrophe),

(x^{p-1}e^{x^{-1}})^{(p)}= [(x^{p-1}e^{x^{-1}})']^{(p-1)}=[(p-1)x^{p-2}e^{x^{-1}}-x^{p-3}e^{x^{-1}}]^{(p-1)}

Par hypothèse de récurrence, appliquée avec n=p-1,

[(p-1)x^{p-2}e^{x^{-1}}]^{(p-1)}=(p-1)(-1)^{p-1}x^{-p}e^{x^{-1}}

et avec n=p-2,

[x^{p-3}e^{x^{-1}}]^{(p-1)}=[(x^{p-3}e^{x^{-1}})^{(p-2)}]'=((-1)^{p-2}x^{-(p-1)}e^{x^{-1}})'

soit

[x^{p-3}e^{x^{-1}}]^{(p-1)}=(-1)^{p-1}(p-1)x^{-p}e^{x^{-1}}-(-1)^{p-2}x^{-(p+1)}e^{x^{-1}}

et l’affaire est conclue.

Il est important de bien voir que cette récurrence fonctionne parce que l’exponentielle est sa propre dérivée, ce qui fait qu’on peut appliquer l’hypothèse de récurrence aux deux termes résultant de la première dérivée. Vu que les deux membres de (1) sont linéaires en f, on peut appliquer la même démonstration aux fonctions vérifiant f'=\alpha f, où \alpha est un nombre complexe, c’est-à-dire aux multiples des fonctions x\mapsto e^{\alpha x}. En particulier, en prenant \alpha imaginaire pur et en séparant les parties réelle et imaginaire, on obtient (1) pour les fonctions x\mapsto \cos(ax) et x\mapsto \sin (bx).

Par contre, la démonstration ci-dessus ne va pas pour les autres fonctions. Je veux dire par là que vous ne pourriez l’appliquer comme telle pour établir, par exemple, que

(x^{n-1}\arctan(x^{-1}))^{(n)}=(-1)^nx^{-(n+1)}\arctan^{(n)}(x^{-1})

pour tout n. En effet, elle suppose qu’on puisse appliquer (1) avec n=p-1 et f=\arctan et avec n=p-2 et f=(\arctan)', ce qui n’est pas possible puisque la dérivée de \arctan ne lui est pas proportionnelle.

La clé consiste alors à considérer toutes les fonctions simultanément, autrement dit à démontrer par récurrence sur n que pour tout f, l’égalité (1) est vraie(*). Ainsi, au lieu de fixer f et d’essayer de prouver (1) par récurrence sur n pour ce f, on généralise le problème en considérant f comme un paramètre. Le résultat est que, dans cette façon de faire, l’hypothèse de récurrence est beaucoup plus forte que selon l’autre angle d’attaque ce qui rend disponibles les arguments utilisés dans le cas particulier de l’exponentielle : appliquer (1) à f avec n=p-1 et à f' avec p-2.

Vous verrez, cela marche tout seul!

😉

––––––––––
(*) En quelque sorte, cela consiste à inverser les deux quantificateurs \forall f et \forall n.

4 réflexions sur “Hypothèse de récurrence et abstraction : un exemple amusant

  1. Très intéressant.
    Prendre le temps d’analyser quel est l’angle d’attaque optimal est un des aspects que l’on omet trop souvent à mon goût lorsqu’on enseigne la récurrence.

  2. Merci pour ces récurrences (commentaire tardif, j’avais essayé bien plus tôt mais avais eu des difficultés à me « connecter »). Je remarque une animation avec des flocons de neige, je vais aussi essayer d’ajouter une décoration pour Noël à mon blog😉

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