Récurrence très forte

L'invention de diverses récurrences, forte (comme la moutarde), et que sais-je encore, est relativement récente, et je pense qu'elle ne sert à rien.
Moi je ne connais qu'un principe de récurrence, que voici. Si l'assertion $P(0) $ est vraie et si pour tout $k \in \mathbb N$ l'assertion $P(k)\Rightarrow P(k+1) $ est vraie, alors $P(n) $ est vraie quel que soit $n \in \mathbb N$. Ce n'est pas une nouveauté.
Si l'on veut démontrer par récurrence une assertion $P(n)$ en fourrant dans l'hypothèse sa véracité pour tous les $k \leq n$, on applique le principe de récurrence que j'ai évoqué à l'assertion $P_1(n) $ qui est : $\forall k\in \{0,1,...,n\},P(k)$.
Et là, on voit tout de suite le tour de passe-passe d'acetonik, qui est sympa pour faire réfléchir.
J'avais tenté d'ouvrir un fil pour rassembler des raisonnements par récurrence, mais ça n'a pas pris. Pourtant, il y a bien à dire sur la riche variété d'exemples de cette méthode de démonstration, en sus des exemples convenus à quoi tout le monde pense de prime abord.
Bonne journée tangentielle.
Fr. Ch.

Bonjour,

Chaurien écrivait:

---

......et je pense qu'elle ne sert à rien.

Ce n'est pas parce que, si on ne vois pas le piège de Cyrano qu'on va nier l'utilité de la récurrence forte, sinon comment tu vas démontrer sans récurrence forte

Soit la suite (u_n) definie par $u_0=1$ et $u_{n+1}=\frac {u_0+u_1+...+u_n}{n+1},\forall n\in\N$, démontrer que $\forall n\in\N,\quad u_n=1$

J'ai connu l'exemple de Cyrano sous la forme démontrer par recurrence forte que $\forall n\in \N,\quad 2^n=1$

$2^0=1$ Vraie
On suppose $2^k=1,\quad \forall k\leq n $ alors $2^{n+1}=2^n\times 2^1=1\times 1=1$

C'est la même preuve que tous les paquets de crayons de couleurs n'ont en fait qu'une seul couleur ! (indication: c'est bleu)

Dans l'exemple que j'ai donné et qui ressemble à celui de Cyrano, mon prof ( Lycée) m'avait expliqué que pour utiliser $2^1=1$ il faut que dans la supposition $2^k=1,\quad \forall k\leq n$ que $n\geq 1$ ce qui oblige l'initialisation de porter sur $n=0$ et $n=1$
Etes-vous convaincus?:-D

désolé, pour cette confusion de dimanche.

Pour le moment aucun des intervenants n'a essayé d'expliquer la faille dans cette récurrence
extrait wiki https://fr.wikipedia.org/wiki/Raisonnement_par_récurrence

Hormis le biais de la preuve d'Acetonik il y a aussi un problème de rédaction à mon humble avis.
Quand on veut utiliser une récurrence forte dans la formulation de la propriété $P_n$ à démontrer on va avoir un "pour tout entier naturel $k\leq n$". (il peut y avoir un minorant entier dans cette inégalité)

PS:
La propriété $P_n$ va ressembler à: $P_n$: "pour tout $k$ entier naturel inférieur ou égal à $n$ la propriété $Q_k$ est vraie".

Alors je n'ai toujours pas compris ton message (pour ma part, j'avais oublié ce message que tu cites, désolé). Je n'y vois qu'une autre interprétation : Que la récurrence forte est une méthode fausse. Comme je ne crois pas que tu penses ça, ton message m'est incompréhensible.

Cordialement.

Ok, mais pourquoi ne pas l'avoir explicité toi-même ?
En tout cas, maintenant c'est fait.

Cordialement.

Il y a une autre grosse escroquerie. C'est la dimension !

Quand on suppose $P(n)$ au rang $n$, on prend A et B des matrices de $M_n(K)$ qui deviendraient miraculeusement des matrices de $M_{n+1}(K)$ au rang suivant.

@zeitnot

Cella, je ne l'ai pas vu. Heureusement que c’était intentionnel de la part de acetonic.

J'avais vu ton message ce matin. J'ai cru que c'était ça qu'il fallait "découvrir" au départ. ;-)

Je suis nul en français, j'ai pris intentionnel dans le sens involontaire

C'est surtout par ignorance

Edit: il est évident que Wikipédia se trompe dans ce cas ...

Non, où serait l'erreur ?
PS. @acetonik : dans ce message, beaucoup d'erreurs !

À part ça, une récurrence extra-forte ($n,k$ sont des variables de type "entiers naturels") :

Si $\forall n\ ( (\forall k <n\ \ P(k))\implies P(n))$, alors $\forall n\ P(n)$

acetonik écrivait:

---

> Si $Q(n)$ est la propriété $[\forall k\in \{0,1,...,n\},P(k) ]=> P(k+1) $
Déjà, embrouille entre $k$ et $n$

> son initialisation dans la récurrence simple est donc:
> $[ \forall k\in \{0\},P(k) ] => P(k+1) $ c'est à dire $ P(0) => P(1)$
L'embrouille continue à ce niveau.

Ensuite, comme l'a déjà signalé Chaurien et comme c'est écrit dans la page wikipedia, le prédicat sur lequel on utilise la récurrence "simple" est tout simplement $\forall k\ (k\leq n \implies P(k))$.
Il n'y a aucune faille dans la page wikipedia, par contre il y a une mauvaise compréhension de ta part, acetonik.

acetonik a écrit:

D'ailleurs dans mon message initial, j'applique correctement ce que dit Wiki... et j'obtiens un résultat absurde.

Non, ce n'est pas vrai. Tu ne démontres pas que pour tout $n\in \N$, $(\forall k\leq n\ \ P(k)) \implies P(n+1)$ : ce que tu écris dans ton message ne marche pas pour $n=0$, bien entendu !

Je suis très attaché au raisonnement par récurrence, qui est un procédé de démonstration extrêmement puissant. Dans un cours il n'est pas nécessaire de gloser à perte de vue sur forte, très forte, très-très forte, super-forte et que sais-je encore. Moi mon cours sur le sujet se borne au principe que j'ai rappelé plus haut.
$ \bullet$ Soit une assertion $P(n)$ concernant un entier naturel $n$. Si l'assertion $P(0) $ est vraie et si pour tout $k \in \mathbb N$ l'assertion $P(k)\Rightarrow P(k+1) $ est vraie, alors $P(n) $ est vraie quel que soit $n \in \mathbb N$.
Pour être tout à fait franc j'ajoute un principe qu'on pourrait dire « de récurrence restreinte », si l'on tient aux étiquettes.
$ \bullet$ Soit une assertion $P(n)$ concernant un entier naturel $n$ et soit $a \in \mathbb N$. Si l'assertion $P(a) $ est vraie et si pour tout $k \in \mathbb N, k \geq a$, l'assertion $P(k)\Rightarrow P(k+1) $ est vraie, alors $P(n) $ est vraie quel que soit $n \in \mathbb N, n\geq a$.
Vous me direz, le second principe est un corollaire immédiat du premier (et le premier du second !), mais en pratique, il est plus commode de l'appliquer tel quel. À tout prendre, on pourrait borner le cours à ce second principe.

À partir de là, il faut mettre en œuvre ce principe, tant dans les exercices illustratifs (qu'on souhaite non triviaux) que dans les démonstrations apparaissant dans la pratique mathématique. Il faut chaque fois énoncer soigneusement l'hypothèse de récurrence $P(n)$. La distinction récurrence forte ou pas apparaît alors superflue (sauf pour la moutarde).

J'ai retrouvé mon point de vue dans un fil de ce forum datant de 12 ans : http://www.les-mathematiques.net/phorum/read.php?2,244032,244092, message de Guego.

Par curiosité, j'ai cherché sur Internet des exemples de la dite « récurrence forte ». Je n'en ai pas trouvé beaucoup, et ceux que j'ai trouvés concernent la suite de Fibonacci $(F_n)_{n \in \mathbb N}$ définie comme l'on sait par : $F_{0}=0$, $F_{1}=1$, $F_{n+2}=F_{n+1}+F_{n}$. Or justement ces démonstrations ne nécessitent pas la « récurrence forte », mais au pire ce qu'on appellerait la « récurrence double » si l'on était féru d'étiquetage. Et bonjour les exemples intéressants ! Il y en a un qui après un baratin prétentieux logico-indigeste nous prouve que les nombres de Fibonacci sont ... des entiers naturels, ah ben ciel alors ! Et un autre nous prouve que $\displaystyle\overset{n}{\underset{k=0}{\sum }}F_{k}^{2}=F_{n}F_{n+1}$ et là, pas de bol, la brave récurrence « simple » suffit pour prouver ça !

Bon, j'arrête. Je vais sans doute reprendre le fil que j'avais ouvert au sujet de la récurrence ... si je le retrouve.

Bonne journée.
Fr. Ch.

Un exemple où la récurrence extra-forte est utile : démontrer que pour tout espace vectoriel $E$ de dimension finie et toute famille $(f_i)_{i\in I}$ d'endomorphismes diagonalisables commutant deux à deux, il existe une base de diagonalisation de $E$ commune à tous les $f_i$ (remarque : $I$ est quelconque, pas forcément fini).

Gébrane,

il n'y a pas besoin d'initialiser à 1, puisque l'hérédité va prouver pour 1. Par contre, la preuve ne doit pas utiliser la propriété à démontrer, même dans un cas particulier (dans le premier message, on utilise le fait que c'est vrai pour n=1), sauf éventuellement pour 0 si on a déjà fait l'initialisation. Mais ce n'est pas caractéristique de la récurrence forte.

Cordialement.

@MathCoss
@ GaBuZoMeu
La chose à bien expliquer aux élèves, c'est que l'assertion $P_1(n)$ que l'on se propose de démontrer par récurrence (dite « hypothèse de récurrence ») n'est pas nécessairement exactement l'assertion $P(n)$ que l'on souhaite démontrer. Ce peut être une assertion qui implique l'assertion souhaitée, et qui peut porter sur tous les entiers naturels $ k \leq n$. Pas besoin d'un chapitre dans le cours, mieux vaut présenter une collection d'exercices, si possibles non triviaux, pas « les nombres de Fibonacci sont des entiers ». .
Vos exemples sont excellents car il s'agit de de vraies propriétés mathématiques qui se prouvent par récurrence, avec une hypothèse de récurrence qui doit être soigneusement choisie et énoncée, selon une véritable stratégie de la récurrence.
Il me revient aussi une propriété du nombre de Bell $B_n$ qui est le nombre de partitions d'un $n$-ensemble : $ B_n \leq n!$ qui se prouve en le supposant vrai pour tous les $k \leq n$.

Bonne après-midi.
Fr. Ch.

Justement, il n'y a pas d'initialisation !
$\forall k <0\ P(k)$ est vrai, bien sûr. Donc si on a montré $\forall n\ ( (\forall k < n\ \ P(k))\implies P(n))$, on a en particulier montré $P(0)$.

Gebrane, il faudrait sérieusement réviser ta logique. Tu crois que la négation de $\forall k<n\ P(k)$ est $\forall k <n\ \neg P(k)$ ???
Pour ta gouverne, la négation de $\forall k<n\ P(k)$ est $\exists k <n\ \neg P(k)$. En particulier, la négation de $\forall k<0\ P(k)$ (qui est vrai quel que soit le prédicat $P$) est $\exists k<0\ \neg P(k)$ (qui est faux quel que soit le prédicat $P$).

Même moi, dont le faible niveau en logique est bien connu, je sais ça ;-).