Récurer, ok, mais faire une récurrence ?

Salut sebsheep,

Tu trouveras sur le forum Pédagogie plusieurs discussions sur la façon de présenter les démonstrations par récurrence.
Je ne suis plus dans le circuit depuis pas mal de temps et je me suis étonné de cette présentation standard avec "initialisation" et "hérédité" . Les questions des rares lycéens qui viennent poster ici montrent souvent qu'il appliquent un schéma sans vraiment comprendre le fond du raisonnement.

Effectivement le raisonnement par récurrence s'appuie sur l'axiome que tu cites.

Je pense qu'un des moyens de le faire sentir est de distinguer les variables muettes $k$ et $n$ dans
"Si une propriété $\phi(n)$ est vraie au rang $0$ et vérifie $\forall k\in \N, \phi(k) \Rightarrow \phi(k+1)$, alors, $\forall n\in \N, \phi(n)$


et de faire réciter au débutant une petite litanie du genre
Puisque $\phi(0)$ est vraie, alors $\phi(1)$ l'est aussi.
Puisque $\phi(1)$ est vraie, alors $\phi(2)$ l'est aussi.
Puisque $\phi(2)$ est vraie, alors $\phi(3)$ l'est aussi.
etc...
et si vous me laissez le temps je saurai ainsi prouver que $\phi(2016)$ est encore vraie...
et si vous me laissez assez de temps je saurais ainsi établir que $\phi(n)$ est vraie quel que soit le rang $n$, grand soit-il.

C'est du moins ainsi que je m'y prenais avec des lycéens au siècle dernier, sans parler d'initialisation ni hérédité.
Amicalement. jacquot

sebsheep a écrit:

comment est défini une "propriété" ?

comment est defini un "ensemble" ? :-D

la formulation que tu propose correspond aux axiomes de Peano mais on peut la deduire de l'autre et inversement
Par exemple dans un cours d'algebre que j'ai lu on presente ces axiomes puis la page d'apres on demontre un theoreme "de recurrence" avec une propriété (comme ce que tu as cité au debut), c'est pratique pour pas avoir à sortir un ensemble defini en comprehension à chaque fois que on veut montrer une propriété pour tout $n\in \mathbb N$
cela dit tu as raison ce n'est pas vraiment un theoreme, plutot un "critère" (on peut pas quantifier sur les proprietes)

Siméon écrivait:

---

> Les deux hypothèses sont traditionnellement nommées initialisation et hérédité.

Juste un mot, dans la série « c'était mieux avant » et « quand les gens savaient écrire » etc., non ce n'est pas traditionnel.:-( C'est relativement récent, même si en l'occurrence, c'est relativement bien trouvé, contrairement à d'autres innovations langagières. :-D Peut-être même que ça peut aider à la compréhension, qui sait ?

Sebsheep : Dans ton premier post, selon ce que tu proposes, pour appliquer une récurrence il faut définir $E$ comme l'ensemble des entiers $n$ pour lesquels la proposition $\phi(n)$ est vraie. Pas sûr que l'on y gagne quelque chose.

Tu as raison. A part le "théorème de contraposition" et le "theorème de raisonnement par l'absurde" non je n'en connais pas d'autre. Tu remarqueras qu'ils n'ont habituellement pas le nom de théorème en L1/L2, juste de "raisonnement", comme la récurrence donc.

Si tu décides d’appeler ça "théorème de récurrence" ça sous entend une démonstration. Quelle est le niveau d'étude de tes élèves et que comptes tu leur dire à propos de cette démonstration ?

@remarque : j'en prends note. Saurais-tu de quand date l'apparition de ces deux noms ?

@sebsheep : le pseudo seul n'est pas trop dur à prononcer, mais « cher sebsheep » l'est beaucoup plus !

Tout nombre est supérieur à 1 milliard.
En effet soit $n\in \N$. Comme $n> 1000 000 000$, on a aussi $n+1>1 000 000 001>1 000 000 000$ d'où le résultat par récurrence.

gerard0 a écrit:

Oui Foys. Et alors ??

Ben je cherche toujours où est le milliard sur mon compte en banque.
Les choses ne se passent pas comme prévu...

Ce n'était qu'un exemple. Je me dis qu'on peut présenter des exemples caricaturaux aux élèves pour au moins leur faire comprendre l'intérêt de l'initialisation.

J'aimerais réagir à ceci toutefois:

sebsheep a écrit:

Mais la récurrence est hyper naturelle chez n'importe quel humain sensé ; quel intérêt y aurait-il à la "formaliser" si c'est en fait pour passer une couche de bouillie ? À ce compte, je préfère encore utiliser des "..." : par exemple $x^n= x \times \ldots \times x$ ($n$ fois).

Soit $N^*$ l'ensemble de tous les polynômes de $\Z[X]$ dont le coefficient dominant (message édité) est strictement positif (ie de la forme $pX^n+\sum _{k=0}^{n-1} p_k X^k$ avec $p>0, n,\in \Z$ et $\forall k, p_k\in \Z$). Soit $N:=N^* \cup \{0\}$. $N$ est évidemment stable par somme et par produit. Soit $S$ l'application de $N$ dans lui-même qui à $Q$ fait correspondre $1+Q$. Alors les affirmations suivantes sont vraies:
1° $\forall x\in N$, $x\neq 0 \iff \exists y:S(y)=x$
2° $\forall x , y \in N, S(x)=S(y) \implies x=y$
3° $\forall x , y \in N$, $x+y=y+x$ et $x\times y = y \times x$
4° $\forall x\in N,x+0=x$
5° $\forall x\in N, x \times 0=0$
6° $\forall x,y \in N, S(x)+y=S(x+y)$
7° $\forall x ,y \in N$, $S(x) \times y=y + x\times y$

Bref: $(N,0,S,+,\times)$ vérifie, à l'exception du schéma de récurrence, TOUS les axiomes de l'arithmétique de Peano.
Donc on ne peut pas trop s'en passer. Chercher "arithmétique de Robinson" sur le net pour plus de précisions.

Mes aventures avec la récurrence (2).

Il y a quelques années j'ai eu à rédiger un cours d'arithmétique de base pour des élèves du second cycle secondaire (dit « lycée » depuis 1975) pour les armer en vue de leur participation à des compétitions mathématiques. Je voulais démarrer ce cours avec une collection de propositions initiales, dénommées axiomes si l'on veut, et qui permettent à elles seules de tout démontrer, non pour me prendre pour un petit Bourbaki, mais simplement pour que les usagers de ce cours sachent bien d'où l'on part.

Je ne voulais pas faire toute une construction laborieuse et longue des entiers, avec liturgie logique-axiomatique, Peano, cardinaux, ou autres, je voulais énoncer tout de suite leurs propriétés afin de travailler avec sans tarder. Je me suis aperçu que le mieux était de partir de $\mathbb Z$ en donnant la liste de ses propriétés comme anneau ordonné, avec en plus le principe de succession, autrement dit que $\left] 0,1\right[ $ est vide. On peut présenter ces propriétés comme bien connues de longue date, avec toutefois une nouveauté, justement ce principe de récurrence qui n'a pas été encore vu dans les classes avant la Terminale (et qui aurait pu l'être plus tôt avec des élèves dûment sélectionnés).

C'est ainsi que procède aussi André Weil (avec Maxwell Rosenlicht) dans un petit livre : Number Theory for Beginners, Springer, 1979, ou bien : William J. LeVeque, Fundamentals of Number Theory, Addison-Wesley, 1977.

Un moment il m'avait semblé que le principe de récurrence était un corollaire du principe de succession, mais c'était une erreur. C'est l'inverse : le principe de succession est un corollaire du fait que l'ordre sur $\mathbb Z_+ =\mathbb N$ est un bon ordre. Et ce bon ordre est équivalent au principe de récurrence : c'est bien clair dans Bourbaki, Théorie des ensembles, chapitre 3, § 4, n° 3, ou bien dans le livre d'André Weil cité plus haut.

L'exemple de Foys de son « $N$ » alternatif où s'appliquent les axiomes de Peano sans le principe de récurrence est intéressant à ce propos car son $S(Q)=Q+1$ est le vrai successeur de $Q$. C'est un bon contre-exemple pour montrer que le principe de succession n'implique pas le principe de récurrence.

Mais bon, moi le raisonnement par récurrence ne m'intéresse pas spécialement comme objet d'étude, il m'intéresse d'abord comme procédé de démonstration. Et c'est sur point que j'interviendrai tantôt.

Bonne soirée, à la saison des longues nuits.
Fr. Ch.

NB. Marcel Gotlib est mort.:-( Encore un peu de nous qui s’en va.

Mes aventures avec la récurrence (3)

Comme j'ai dit j'ai enseigné à plusieurs reprises la récurrence, toujours en bornant mon cours au principe de récurrence sous ses deux formes que j'ai données dans mon message (1). On me dit que la deuxième se ramène à la première, c'est vrai, mais il m'a semblé préférable de donner un principe utilisable immédiatement.

L'hypothèse de récurrence $P(n)$ doit être énoncée avec soin. Elle peut être l'assertion que l'on veut prouver, comme dans l'Incontournable Premier Exemple $2^n>n$, mais elle peut être aussi une assertion qui implique celle-ci sans s'y réduire. Dans les questions concernant les suites récurrentes d'ordre $2$, par exemple ma chère suite de Fibonacci et sa sœur cadette de Lucas, on doit mettre deux valeurs consécutives de $n$ dans l'hypothèse de récurrence $P(n)$. Dans d'autres c'est toutes les valeurs depuis la première. Dans d'autres encore c'est plus caché. Il y a une stratégie de la récurrence.

Un cours aussi réduit avec abondance d'exercices, c'est une situation inhabituelle, et somme toute sympathique, car que sont donc les mathématiques sinon l'art de résoudre des problèmes et d'en poser d'autres ? Mais ceci ne convient pas aux cuistres, qui ces dernières années nous ont bombardés de terminologie ronflante, initialisation, hérédité, récurrence forte - alors qu'il n'en est pas de faible - et que sais-je encore. Et comme cette engeance se recopie pieusement, ces vocables sans intérêt occupent l'espace et leur apprentissage occupe le temps qui serait mieux utilisé à la résolution des problèmes.

Déjà Bourbaki détaillait les formes particulières habituelles de l'hypothèse de récurrence, mais il ne se donnait pas le ridicule de leur coller des dénominations.

Il me semblait que cette question avait déjà été abordée sur ce forum et j'ai eu du mal à la retrouver mais c'est fait, c'était il y a quatre ans :

http://www.les-mathematiques.net/phorum/read.php?18,773557,773777

Il s'y trouve des informations sur ce mode de raisonnement et son origine, avec des références, par exemple le livre de Sominskii. Par parenthèse, j'ai retrouvé ce fil avec Google, et non par le moteur de recherche interne au forum, sans savoir si c'est ce dernier qui ne fonctionne pas correctement, ou bien si c'est moi qui ne sais pas m'en servir...

J'ai retrouvé aussi un article qui développe à peu près les mêmes idées en donnant des exemples, qui est paru naguère dans un magazine, sous une forme charcutée. Je vous le communique sous sa forme véritable.

Comme j'ai dit moi je souhaiterais un fil de discussion qui rassemble des exemples variés de raisonnement par récurrence, simples ou plus ingénieux. C'est un procédé de démonstration d'une puissance inattendue pour une définition de départ si simple. Il faudra y revenir.

Bonne journée.
Fr. Ch.
07/12/2016

Merci à GaBuZoMeu pour ce texte. Un grand mérite est de ne pas recourir à un vocabulaire boursouflé pour distinguer les "schémas de récurrence". Quelle est la référence de ce texte ?

Je l'ai reçu sous une forme défectueuse Les deux dessins des dominos, page 1, ne sont pas visibles mais ce n'est pas très grave, on devine. Les dessins 1, 2, 3, 4, 6 ne sont pas visibles, ni l'inégalité du problème 7, page 15, ni l’empilement de racines carrées du problème 11, page 12..

Le problème 8, page 10, ne me semble pas avoir de lien avec la récurrence : on fait $n:=41$, et c'est non, et c'est tout.

Le problème le plus intéressant est pour moi le partage du disque, page 10, mais il est dommage qu'il ne soit pas traité.

Maintenant, on pourrait donner des exemples plus avancés de raisonnement par récurrence dans divers domaines mathématiques. Je vais essayer de le faire pour ma part. Les proches vacances y seront propices.

Bonne journée.
Fr. Ch.

,

Mes aventures avec la récurrence (4)

Dans l'article cité dans mon message (3), un des problèmes posés est : pour $p \in \mathbb N^*$, démontrer que le produit de $p$ entiers consécutifs est divisible par $p!$. On peut prouver ceci d'au moins trois façons autrement que par récurrence, mais comme la récurrence nous occupe aujourd'hui c'est à cette méthode que nous recourrons.

Il s'agit de prouver que pour tout $n \in \mathbb N$ et pour tout $p \in \mathbb N^*$, le nombre $\frac{n(n-1)...(n-p+1)}{p!}$, a priori rationnel, est en fait un entier.

Rien ne nous empêche de poser : $(_{p}^{x})=\frac{x(x-1)...(x-p+1)}{p!}$ pour $x \in \mathbb R$ et $p \in \mathbb N^*$. On définit bien ainsi un nombre réel, et même complexe s'il nous chantait de prendre $x \in \mathbb C$, mais restons dans $\mathbb R$ présentement.

Cette fonction $(_{p}^{x})$ satisfait à l'égalité : $(_{p}^{x})=(_{~~p}^{x-1})+(_{p-1}^{x-1})$, pour $x \in \mathbb R$ et $p \in \mathbb N,p\geq 2$, dont la preuve est immédiate. On étend cette égalité à $p=1$ en posant $(_{0}^{x})=1$ pour tout $x \in \mathbb R$. Cette égalité est bien connue, sous l'appellation : formule de récurrence de Pascal. Le mot récurrence apparaît lors même que la récurrence n'est intervenue en rien jusqu'ici, mais il s'agit pour ainsi dire d'une promesse de récurrence.

Alors nous pouvons prouver par récurrence l'assertion $P(n)$ :« $\forall p\in \mathbb N, (_{p}^{n})\in \mathbb N$ ». Vraie pour $n=0$ ; et si elle est vraie pour un certain $ n\in \mathbb N$, la formule de Pascal tient sa promesse, et l'assertion $P(n+1)$ est vraie.

C'est un premier exemple de traitement par récurrence d'assertions faisant intervenir plus d'une variable ; je donnerai d'autres exemples tantôt.
Bonne soirée.
Fr. Ch.
19/12/2016

Bonsoir sieur Chaurien,

un jour Raymond Smullyan m'a indiqué qu'il fallait faire gaffe à la définition/construction par récurrence. Je suis censé faire le malin avec ce post.

-> comment démontres-tu qu'il existe une suite $u$ d'entiers telle que $\forall n \in \mathbb{N}\, : u_{n+2}=u_{n+1}+u_n$ avec $u_0=0$ et $u_1=1$.

[small]C'est miraculeux que le soleil se lève chaque jour.
Ben ouais chaque jour il y a le soleil,
c'est la définition de jour.[/small]

S

Chaurien a écrit:

Ce que j'aurais aimé dans ce fil c'est une collection de résultats qu'on démontre par récurrence et qui ne se limite pas aux deux ou trois exemples triviaux qu'on présente d'ordinaire lorsqu'on évoque cette question spécifiquement.

As-tu consulté le bouquin de Gunderson, Handbook of mathematical induction (CRC Press) ? 800 pages de récurage, ça devrait étancher quelque peu ta curiosité.

Non, Chaurien, tu n'es pas boudé: la fonction "tak" me semble un objet non trivial pour illustrer la puissance de la récurrence.
Cordialement
Paul

Bonjour Monsieur Chaurien,

je suis très surpris de votre sérénité face à ma p'tite provocation, que même que j'aime bien ce genre de surprise.

J'avais lu cela dans Set Theory and the Continuum Problem de Raymond M.Smullyan et Melvin Fitting.


Ce n'était pas dans votre liste de cadeaux de Noël, mais ce scan est tombé du traîneau alors bon je vous le dépose là dans les sabots numériques du forum.

S