Récurrence forte sans initialisation ?

FB

Bonjour,

Peut-on utiliser la récurrence forte sans initialisation ?
Si oui, avez-vous un exemple d'une telle démonstration ?

Merci,
FB

MrJ

Non! Considérons la suite $(u_n)$ définie par $u_0=1$ et
$$\forall n\in\mathbb{N},\quad u_{n+1} = u_0 +\cdots + u_n.$$

Si tu n’initialises pas ta récurrence forte, tu peux en déduire que $u_n$ est pair pour tout $n\in\mathbb{N}$, ce qui est trivialement faux.

Dom

Il me semble d’ailleurs qu’une récurrence forte n’est qu’une récurrence faible déguisée. 

ev

Bonsoir FB

Peux-tu donner un exemple, histoire de savoir ce que tu entends par récurrence forte ?

e.v.

gerard0

Bonsoir.

Il me semble que la récurrence forte, où on utilise "$\forall n \in \mathbb N, \ \left(\forall k\in \mathbb N,\ k<n,\Rightarrow P(k)\right) \Rightarrow P(n)$" ne nécessite pas d'initialisation.

Le contre-exemple de Mr J n'en est pas un, puisque pour $n=1$ on ne peut pas vérifier cette implication avec $P(n)="u_n$ est pair" puisque $\left(\forall k\in \mathbb N,\ P(k)\right)$ est faux et $P(1)$ vrai. Ce n'est qu'un cas de l'erreur habituelle de la preuve qui n'est valable que pour $n$ suffisamment grand.

Mais cela veut dire qu'il faut manier cette preuve avec soin !

Cordialement.

[édit : rectification de la première formule qui n'avait pas de sens. puis (5/12) rajout de la fermeture de l'édit pour test]

gebrane

Bonjour gerard0

J'ai du mal à saisir ta formulation pour une récurrence forte $\forall n\in\N,\ (\forall k\in\N,\P(k))\Rightarrow P(n)$.

Soit $P(n)$ une propriété définie sur  $\N$, j'ai appris la récurrence forte comme cela.

Si $(\forall k<n,\ P(k))\Rightarrow P(n)$ (pour tout $n\in\N$) alors $P(n)$ pour tout $n\in\N$.

MrJ

@gerard0. Je ne comprends pas ta remarque. Si on ne se soucie que de l’hérédité.
- Si $u_0$ est pair, alors $u_1=u_0$ est pair.
- Si $u_0$ et $u_1$ sont pairs, alors $u_2= u_0 + u_1$ est pair.
- etc.

Foys

Etant donné $n\in \N$, on désigne par $Préd(n)$ l'ensemble des entiers strictements inférieurs à $n$. Soit $A$ une partie de $\N$ telle que pour tout $x\in \N$, si $Préd(x) \subseteq A$ alors $x\in A$. Alors $A=\N$. En effet, sinon, il existe un plus petit élément $y$ dans le complémentaire de $A$ et par minimalité $Préd(y)\cap (\N \backslash A)=\emptyset$ et donc $Préd(y)\subseteq A $ ce qui contredit l'hypothèse.

La récurrence dite forte sur les entiers n'est rien d'autre que l'exploitation de cette propriété.

gerard0

Effectivement, Mr J, tu ne peux pas comprendre ma remarque, puisque tu n'utilises pas la propriété que j'ai signalée (ni celle de Foys, qui doit être la même). Tu n'utilises pas non plus ton propre énoncé, mais seulement une déclaration non mathématisée (avec des "si" du français courant, qui mélangent l'hypothétique contrefactuel avec le raisonnement d'implication).

Pour ma part, j'ai fait une erreur sur les indices, c'est pour 2 qu'il y a un problème.

La propriété ($u_0$ est pair) $\Rightarrow$ ($u_1$ est pair) est vraie (faux $\Rightarrow$ faux) mais ne dit pas que $u_0$ et $u_1$ sont pairs. Ton énoncé comporte une condition que tu ne peux pas laisser de côté ($u_0=1$). D'ailleurs, si la suite est définie avec $u_0=0$ ou $u_0=2$ il n'y a plus de problème. Tu ne peux pas raisonner avec ce que tu appelles "l'hérédité" en négligeant la définition précise de ta suite.

C'est pour cela que je parlais de "l'erreur habituelle".

Cordialement.

NB. Je rectifie mon message, j'avais oublié le $k<n$.

MrJ

Pour moi, l’hérédité d’une récurrence forte sur $n\in\mathbb{N}$ s’écrit généralement comme ci-dessous.

Hérédite. Si $n\in\mathbb{N}$ est tel que les propriétés $\mathcal{P}_k$ soient vraies pour tout $k\in\llbracket 0,n\rrbracket$, alors la propriété $\mathcal{P}_{n+1}$ est vraie.

On peut démontrer formellement la propriété ci-dessus, même si un tel entier $n$ n’existe pas (c’est le rôle de l’initialisation d’assurer son existence.
Mon exemple initial n’est pas très intéressant, car il n’y a que les deux premières valeurs qui posent problème, mais on peut le modifier légèrement en $u_0=1$ et $$\forall n\in\mathbb{N},\quad u_{n+1} = \sum_{k=0}^n 2^k u_k.$$

FB

La source de ma question est dans le Tout-en-un pour la licence Dunod (p.55 de la 3e edition).
(La section et l'exercice proposés ne m'ont pas éclairé).
Je cherche une propriété que l'on démontrerait sans initialisation, et où ce serait pertinent de le faire.
Merci.

gerard0

Vous pourrez remarquer que la propriété citée par FB n'est pas la même que ce que propose Mr J. Avec cette de FB, pour n=0, elle démontre que P(0) est vrai (la prémisse est vraie, faute de m pour la contredire). Elle ne marche pas avec les "contre-exemples" de Mr J.

Ce que propose Mr J n'est pas la propriété de récurrence forte, sauf à régler le problème du premier terme.

Et souvent, on ne peut pas démarrer la récurrence forte sans la valeur de départ - c'est le cas du premier exemple de Mr J avec $u_0=2$ à la place de 1 -  d'où le "en principe" du texte cité.

Par exemple, avec $u_0=2,\ \forall n\in \mathbb N \ u_{n+1}=\sum\limits_{k=0}^n u_k$, démontrer $(\forall m\in \mathbb N,\  m<n\Rightarrow u_m\in 2\mathbb N)\Rightarrow u_n\in 2\mathbb N)$ se fait en deux étapes : $n=0$, où c'est la parité de $u_0$ qui est utilisée, puis $n>0$, où s'utilise la formule générale. On voit bien ici pourquoi l'auteur dit "en principe".

Il me semble que Foys avait donné un exemple où on traitait directement le cas général, je ne le retrouve pas, peut-être le remettra-t-il ?

Cordialement.

gebrane

Bonjour gerard0

Pour le bien de FB, à rectifier encore une fois cette formule ∀n∈N, (∀k∈N, k<n,⇒P(k))⇒P(n)

Dom

Je crois qu’il est nécessaire de faire mieux : expliciter les théorèmes complets. 

Celui de la récurrence « classique » (parfois on dit « faible »). 

Celui de la récurrence « forte ». 

J’avoue être dans le « faites ce que je dis, mais moi je ne le fais pas ». En partie parce que déjà on a l’impression qu’il existe au moins deux récurrences fortes distinctes.

Remarque : de mon téléphone, les codes LateX se battent et je ne parviens pas à fixer vos formules. L’écran oscille entre « tout en bas » puis revient au bon endroit etc.

lourrran

On peut en effet distinguer 2 récurrences fortes :
1.  Pour tout n positif ou nul, si la propriété P est vraie pour tous les entiers naturels k strictement inférieurs à n, alors elle est vraie pour n.
Avec cette variante, pas besoin de traiter l'initialisation, la démonstration de l'hérédité va prouver en même temps que la propriété est vraie pour n=0.

2. Pour tout n positif ou nul, si la propriété P est vraie pour tous les entiers naturels k inférieurs ou égaux à n, alors elle est vraie pour n+1..
Ici, il faut vérifier l'initialisation.

Mais on est vraiment en train de couper des cheveux en 4. Dans le doute, on considère que la vérification de l'initialisation est obligatoire. Ca ajoute une étape, qui est en général triviale.

Martial

Je suis assez d'accord avec lourran et je préfère la version 2. Un exemple amusant : le lemme des mariages. Soit $n$ un entier non nul. $n$ filles désirant se marier dressent chacune lune liste de garçons susceptibles de l'intéresser. Le problème consiste à marier toutes les filles en respectant leurs desiderata. Il y a une condition nécessaire triviale : par exemple s'il y a 4 filles qui à elles toutes ne sont intéressées que par 3 garçons, on voit bien que ça va pas le faire.

Exercice. Montrer que cette condition nécessaire est en fait suffisante. En d'autres termes : s'il y a $n \geq 1$ fille(s) à marier et si, pour tout $p \leq n$, tout groupe de $p$ filles est intéressé, à elles toutes, par au moins $p$ garçons, alors il est possible de marier les $n$ filles en respectant leurs vœux.

Il faut évidemment raisonner par récurrence forte, et on voit bien que l'initialisation est nécessaire, et triviale : s'il n'y a qu'une fille et qu'elle est intéressée par $0$ garçon, on est dans la m...

Thierry Poma

Bonjour
Voici un montage du principe de récurrence mis en scène dans ce fil, extrait de la Théorie des ensembles de Bourbaki :


Puisque dans le critère C59, la lettre $x$ n'est pas une constante, il revient au même d'écrire les relations en jeu comme suit : \[(\forall\,x)\left((x\in{}E\text{ et }(\forall\,y)(y\in{}E\text{ et }y<x)\Rightarrow{}R(y))\Rightarrow{}R(x)\right)\text{ et }(\forall\,x)((x\in{}E)\Rightarrow{}R(x))\qquad(\star)\]Enfin, vu que l'ensemble $\N$ est bien ordonné par l'ordre usuel $\leqslant$, l'on déduit le principe de récurrence transfinie correspondant en faisant $E=\N$ dans $(\star)$. C'est un principe de récurrence que l'on utilise avec les ordinaux, les entiers naturels étant des ordinaux.

gebrane

Une vidéo pour FB pour éviter dans un exemple un piège de la récurrence forte

MrJ

Je constate que l’ambiguïté provient du fait qu'on ne parle pas de la même chose.

lourrran a très bien exposé les deux points de vue.

Personnellement (avec mes connaissances), je n'arrive pas à voir l’intérêt (mathématique ou pédagogique) que pourrait avoir le premier point de vue.

De toute manière, en dehors de la discussion initiale, je préfère penser la récurrence forte comme un cas particulier de récurrence "simple".

JLapin

FB a dit :
Peut-on utiliser la récurrence forte sans initialisation ?
Si oui, avez-vous un exemple d'une telle démonstration ?

Tu cherches un exemple pour ta culture personnelle ou pour montrer à des élèves ?

Si c'est le deuxième cas, mieux vaut éviter de les embrouiller avec ce type de rédaction.

Si c'est le premier cas, tu peux par exemple rédiger ainsi la preuve du théorème d'existence d'une décomposition en facteurs premier.

Pour $n\in \N^*$, on pose $P_n$ : $n$ est un produit de nombres premiers.

Soit $n\in \N^*$ tel que $\forall k\in [1,n-1], P_k$. Montrons $P_n$.

Si $n=1$, le produit vide convient.

Si $n$ est un nombre premier, $n=n$ convient.

Si $n\geq 2$ n'est pas un nombre premier, il s'écrit sous la forme $n=ab$ avec $a,b\in [2,n-1]$ et on conclut avec $P_a$ et $P_b$.

FB

C'est effectivement la première version de la récurrence forte proposée par Lourran qui m'intéresse.

@JLapin : Merci pour l'exemple.
En l'état, si je devais démontrer $P_n$, je ferais une étape d'initialisation.
Et j'ai l'impression que ça revient au même que ce que tu fais quand tu distingues le cas $n=1$.

Pour répondre à ta question : c'est pour ma culture, je n'oserais pas faire ça à mes étudiants, je les perdrais instantanément.

pldx1

Bilan:
Dans une récurrence il y a une phase d'initialisation, puis une phase de propagation. 
Quant à la fortification, cela consiste à faire comme si on était encore plus fort que les récurreurs ordinaires,
puis à s'indigner des haussements d'épaules. 
On peut oublier !

Foys

Il n'y a pas besoin d' "initialisation" ou autre toc vidophobe pour exploiter le fait que si le complémentaire d'une partie de $\N$ ne possède pas de plus petit élément alors cette partie est égale à $\N$.

pldx1

"Si le complémentaire d'une partie de $\N$ ne possède pas de plus petit élément alors cette partie est égale à $\N$". Quand on se sert de cela pour une descente infinie à la Fermat, on fait oeuvre utile. Quand on prétend utiliser cela pour fortifier une récurrence banale, c'est juste du brassage de vent.

FB

A défaut d'avoir trouvé un exemple qui me semble pertinent, j'ai essayé de démontrer que l'on a : 
$\forall n \in \N,  P(n)$  si, et seulement si, $ \forall n \in \N (\forall m < n, P(m)) \implies P(n)$

Et en fait, c'est assez facile à démontrer.
=> je ne saurais toujours pas quand l'utiliser (et ne voudrais probablement pas l'utiliser), mais au moins je suis convaincu !

Merci pour votre aide !

GaBuZoMeu

Bonjour,

Exercice : démontrer que si $(f_i)_{i\in I}$ est une famille d'endomorphismes diagonalisables d'un espace vectoriel de dimension finie qui commutent deux à deux, alors il existe une base de diagonalisation commune de tous les endomorphismes de la famille.

(On pourra employer une "récurrence forte" au sens du message ci-dessus).

pldx1

Banal. Il y en a trois lignes dans http://math.univ-lyon1.fr/~tchoudjem/ENSEIGNEMENT/MATH-III-ALG/notes-cours.pdf, page 116. Pas de quoi en monter une mayonnaise à base de moutarde forte. On remarquera néanmoins que considérer à part les homothéties ressemble fortement à une initialisation !

GaBuZoMeu

Bien sûr que c'est banal. On remarquera que le texte mis en lien parle bien de récurrence, et ne fait aucune initialisation..

Foys

Soit $n$ la plus petite dimension pour laquelle ce n'est pas vrai.  Soit $E$ un espace vectoriel de dimension $n$ et $(f_i)_{i\in I}$ une famille d'endomorphismes de $E$ réalisant un contre-exemple. Alors ces endomorphismes ne peuvent être tous des homothéties (sans quoi n'importe quelle base de $E$ -et il en existe toujours- les diagonalise tous). Soit donc $j\in I$ tel que $f_j$ n'est pas une homothétie et $(E_{\lambda})_{\lambda \in spec(f)}$ la décomposition en espaces propres de $f$. Pour tout $\mu\in spec(f)$, $\dim(E_{\mu})<n$ ($f$ est une homothétie sinon) et en recollant les bases $(\beta_{\lambda})_{\lambda \in spec f}$ diagonalisant les  $\left (f_i |_{E_{\lambda}} \right)_{i\in I}$ (on exploite le fait que les espaces propres de $f_j$ sont stables par toute application commutant avec $f_j$), une contradiction apparaît.

Je me demande comment il y aurait une "initialisation cachée" ici, seul le fait que l'ordre sur $n$ est un bon ordre est utilisé. Par contre:

un mathématicien intuitionniste a dit :
 Toutes ces doubles négations, je suis choqué

Si on décide de passer malgré tout par $\left (\forall n\in \N,\  (\forall k\in \N,\ k<n \Rightarrow P(k)) \Rightarrow P(n)\right) \Rightarrow \forall n\in \N,P(n)$, j'ai l'impression qu'il faudra se servir à un moment où à un autre de ce que "pour tout $i\in I$, $f_i$ est une homothétie, ou bien il existe $i\in I$ tel que $f_i$ n'est pas une homothétie".

La diagonalisation simultanée est-elle un théorème intuitionniste ?

gebrane

Dans un autre corrigé, on parle d'une récurrence (sur la dimension) mais on prend la peine de faire une initialisation pour n=1

https://minerve.ens-rennes.fr//images/Diagocommut.pdf

Va comprendre  !!

GaBuZoMeu

Eh bien, on prend la peine pour rien !

gebrane

Dans un examen de concours, il vaut mieux prendre cette peine d'initialiser car on se sait pas où va atterrir notre feuille de rédaction sur  quel genre de correcteur.

Riemann_lapins_cretins

C'est notre bel orgueil à nous les mathématiciens d'en écrire le moins possible, pas tant par flémme que pour montrer qu'on sait, nous, quelles sont les hypothèses minimales, et qu'on ne compte pas en écrire plus, uniquement pour le plaisir d'attendre que le lecteur/correcteur écrive sur la feuille "et l'initialisation ?" afin de lui répondre "elle est inutile !" de l'air désinvolte du vainqueur ridicule.

Enfin, dans la jeunesse fougueuse du moins.

b.b

RLC, le souci, c'est qu'à force, on arrive à douter de raisonnements valides. 

GaBuZoMeu

Faire l'initialisation dans ce type de situation montre en fait une incompréhension du raisonnement.

Dom

Je n’ai pas réussi à lire le pdf (mais je sais pourquoi… c’est de mon côté que ça déconne…). 

Ce qu’il manque pour la compréhension, ce sont des énoncés clairs avec des preuves qu’ils sont équivalents. 

Ensuite on applique un des théorèmes.

GaBuZoMeu

Qu'est-ce qui n'est pas clair pour toi, dom ?

Dom

Je disais qu’on n’énonce pas les théorèmes mais que l’on parle de « principe de récurrence » et qu’on donne des « méthodes ». Je dis cela au sujet des pratiques les plus courantes (dans ma formation initiale, par exemple, je n’ai jamais vu le théorème pour la récurrence simple). 

Je pense que les « incompréhensions du raisonnement » que tu pointes dans le message précédent viennent de là.

Dans un autre fil, c’est peut-être Foys qui avait rappelé le théorème (récurrence simple).
Il le fait dans ce fil aussi, je crois (désolé mais là lecture sur mon téléphone ce soir me fait des misères…).

Bon mais cela dit, je devrais essayer d’énoncer ces choses là (récurrence simple + les deux récurrences fortes distinguées en début de fil) et d’établir ces équivalences pour voir où j’en suis.

Pas ce soir 🤬

pldx1

Bonjour, 

Il y a deux stratégies pour prouver une propriété dépendant d'un nombre entier.  (1) partir d'une valeur de validité, puis propager (2) montrer que s'il y avait une exception, il y aurait une exception de taille minimale, et montrer que cela coince. On peut toujours dire que chacune des deux méthodes peut servir à prouver l'autre et que tout cela n'est qu'un morceau d'une théorie générale des ordinaux, elle même n'étant qu'un morceau... (et récursivement).

Il n'en reste pas moins que, lorsque l'on cherche une preuve, il vaut mieux choisir si l'on va procéder par montée ou bien si l'on va procéder par descente. Et lorsque l'on rédige une preuve par descente, il n'est pas raisonnable de l'appeler preuve par montée forte. 

Cordialement, Pierre.

gebrane

Bonjour

Soit $N\in \N^*$ fixé. Comment démontrer par récurrence (simple ou forte) que pour tout entier $ n$, il existe uniquement $N-1$ entiers entre $n$ et $n+N$ ?

(On convient que : il existe $ entier entre ... signifie qu'il n'existe pas d'entiers entre ..)

gerard0

Bonjour.

Pourquoi vouloir utiliser une récurrence, alors que cet ensemble (*) est, de façon évidente, en bijection avec le segment $[1,N-1]$ (**) de $\mathbb N$ ?

Cordialement.

(*) J'ai interprété comme "strictement compris".

(**) ensemble des entiers strictement compris entre 0 et N.

gebrane

Gerad0. On m'a demandé de proposer l'exercice. C’était sur un cours introduisant l'ensemble $\N$ et le raisonnement par récurrence.

gerard0

Alors une fois $N$ choisi, on fait une récurrence simple sur $n$. Où est le problème ? On passe de $n$ à $n+1$ en supprimant $n+1$ et en rajoutant $n+N$, ce qui fait le même compte. Mais c'est un exercice bien compliqué dans sa présentation, sauf à le réécrire "Montrer que pour tout $N\in \mathbb N^*$ et tout $n\in \mathbb N$, ...", qui permet de faire la récurrence sur $N$.

Cordialement.

gebrane

@gerard0 , je n'ai fait que publier l'exercice.

Je ne sais à quel niveau de connaissance, il faut traiter l'exercice. Par exemple pour N=1, il faut montrer qu'il n'existe pas d'entiers entre n et n+1 (autrement dit démontrer que n+1 est bien  le successeur de n).

Oublions donc !

gerard0

Dans l'arithmétique de Peano, $x+1$ est défini comme le successeur de $x$.

En fait, cet exercice est une sorte de piège, surtout si on ne précise pas les propriétés connues de $\mathbb N$.

Oublions donc !

gebrane

gerad0 disait Dans l'arithmétique de Peano, x+1 est défini comme le successeur de x.

Il me semble qu'on peut démontrer que le successeur de n est bien n+1 en supposant seulement que les entiers sont positifs, car par un  raisonnement par récurrence, on démontre que pour tout $n\in \N$ il n'existe pas d'entiers entre n-1 et n.

gerard0

A partir de quelle définition de $\N$ ???? Comment est défini n-1 ??? Et que veut dire "positif" dans l'arithmétique de Peano ?

Sans un contexte de propriétés connues donné, inutile de parler de "démontrer".

Cordialement.

gebrane

Voici une axiomatisation de l’ensemble des  entiers naturels

1. L’élément appelé zéro et noté 0, est un entier naturel.
2. Tout entier naturel a un unique successeur.
3. Aucun entier naturel n’a 0 pour successeur.
4. Deux entiers naturels ayant le même successeur sont égaux.
5. Si un ensemble d’entiers naturels contient 0 et contient le successeur de chacun de ses éléments, alors cet ensemble contient tous les entiers naturels.

gerard0

Oui, c'est l'axiomatique de Peano. C'était au programme de terminale math élem quand j'ai passé le bac, et mon sujet d'oral de capes (je n'avais rien préparé, je n'avais même pas apporté de bouquin pour cet oral unique).

Ensuite, il faut au moins définir l'addition, puis l'ordre. Pour l'addition, je ne vois pas de définition qui ne repose pas sur s(n)=n+1 ou qui ne le donne pas de façon immédiate (dans mon cours, on la définissait par récurrence par n+m+1 = s(n+m) si je me souviens bien). Je te laisse le faire, ainsi que la définition de l'ordre. On verra à ce moment-là.

Cordialement.

Martial

Quelques remarques : je ne fonctionne pas avec le système d'axiomes donné par gebrane, mais peu importe. A signaler toutefois que ce système est une version au second ordre de Peano. (Puisqu'on parle d'ensembles d'entiers naturels).

@gérard0 : "positif" dans ce contexte ne veut rien dire, sinon entier naturel, i.e. élément de la structure. Par contre avec le système de gebrane il est très facile de définir $n-1$. Soit $B$ l'ensemble de tous les entiers naturels qui sont le successeur d'un entier naturel. On pose $A=B \cup \{0\}$, et on va montrer que $A= \mathbb{N}$. :

a) $0 \in A$ : Clair.

b) Si $n \in A$, deux cas : ou bien $n=0$, donc $S(0)$ est le successeur de $0$, donc il est dans $A$. Ou bien $n \in B$, donc $n=S(p)$, et $S(n) =S(S(p))$, donc $n \in B$, donc $n \in A$.

Par l'axiome 5 tout entier naturel sauf $0$ est successeur d'au moins un nombre. Mais à cause de l'axiome 4 ce nombre est unique, et personne (même Dieu) ne peut t'empêcher de l'appeler $n-1$.

ev

Martial a dit :

(...) personne (même Dieu) ne peut t'empêcher de l'appeler $n-1$.

Mais je n'ai encore rien dit !

e.v.