Récurrence très forte — Les-mathematiques.net The most powerful custom community solution in the world

Récurrence très forte

Bonjour,
Petit amusement du dimanche (désolé pour ceux qui connaissent) :

Pour toutes matrices $A$ et $B $ de $M_p(K)$ et tout $n$ entier naturel on a: $ A^n B = B $

La preuve ?

Soient $A$ et $B$ deux matrices de $M_p(K)$ :
Pour $n$ entier naturel soit $P(n)$ la proposition $" A^n B =B"$

- La propriété est vraie au rang $n=0$ car $A^0 B = I_n B = B$

- Soit $n$ un entier naturel , supposons $P(n)$ vraie jusqu'au rang $n$.
$A^{n+1} B = A A^n B= AB $ (hypothèse au rang $n$ ) et $A B= B$ (hypothèse au rang $1$)
on obtient ainsi $A^{n+1} B =B$
$P(n+1)$ est vraie

Conclusion: .....

Trop forte cette récurrence :-)
Bonne journée

Edit: modification de la notation de l'ensemble des matrices ( dimension p au lieu de n)
«1

Réponses

  • 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.
  • Cette preuve est très proche de la preuve classique que tout ensemble à n>0 éléments a en fait un seul élément.

    Cordialement.
  • 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$
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Des exemples convenus sont ceux qui utilisent une propriété réflexive : a la même couleur que, est parallèle à, a la même longueur que, a la même mesure que, a la même dimension que, etc.

    @gebrane
    Relis le message de @Chaurien.
    Il suffit de modifier la propriété P(n) pour y inclure tous les entiers inférieurs à n.
  • 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)
  • @Dom
    J'ai arrêté la lecture à "elle ne sert à rien".
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • 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
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Variante : $2^n=(-1)^n$ pour tout $n$. En effet, $2^0=(-1)^0$ et les suites $(2^n)_{n\in\N}$ et $\bigl((-1)^n\bigr)_{n\in\N}$ satisfont à la relation de récurrence suivante : pour tout $n\in\N$, $u_{n+2}=u_{n+1}+2u_n$.
  • @ gebrane
    C'est sans importance , mais avec tout mon respect pour Cyrano , je tiens à préciser que lui et moi sont des intervenants différents.

    J'en profite pour signaler que j'apprécie que ce fil n'ait pas dévié .

    Cordialement à tous.
  • Oui gebrane, je n'ai pas compris pourquoi tu me citais. :-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écurrence70246
    11.jpg 81.4K
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Gebrane,

    tu parles de quelle faille ?

    Dans le "raisonnement" du premier message, on utilise explicitement le rang 1. Donc il faut que ce soit démontré pour le rang 1. Or la preuve pour le rang 1 utilise (hérédité) le fait que c'est vrai au rang 1. Cette preuve est donc circulaire pour n=0, donc n'est pas acceptable.
    Suis-je fondé à penser que tu n'avais jamais rencontré ces fausses preuves ? car si personne n'a "démonté" la "preuve" de Acetonik, c'est qu'on connait déjà.

    Cordialement.
  • 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".
  • gerard0 écrivait:

    > Suis-je fondé à penser que tu n'avais jamais
    > rencontré ces fausses preuves ?

    Suis-je fondé aussi que tu ne me lis pas ?:-D http://www.les-mathematiques.net/phorum/read.php?3,1575410,1575482#msg-1575482
    J'ai posé la question pour inciter un débat de dimanche ( Il fait très froid dehors)
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • 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.
  • @gerard0

    acetonik utilise la récurrence forte pour démonter un truc faux, donc j'ai dit qu'il y a une faille dans le raisonnement de acetonik et il serait bien de l'expliquer aux étudiants sinon si je comprends ton principe: moi je sais, les autres profs le savent, tant pis pour l’étudiant-élève qui ne le sait pas et si on a rien dit , c'est parce que, on le sait.
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Ok, mais pourquoi ne pas l'avoir explicité toi-même ?
    En tout cas, maintenant c'est fait.

    Cordialement.
  • bah c'est explicité par mon prof du Lycée, revoir mon message.
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Je voulais simplement mettre en évidence, sur un exemple, le fait qu'en utilisant de façon incorrecte la récurrence dite forte, on peut démontrer n'importe quoi.
    @Gebrane , tu as d'ailleurs dit fort justement qu'il fallait, en pratique, démontrer la propriété aux deux premiers rangs pour que la preuve soit correcte..Il suffit de mettre en forme le raisonnement comme proposé par Chaurien pour s'en convaincre.

    Si $Q(n)$ est la propriété $[\forall k\in \{0,1,...,n\},P(k) ]=> P(k+1) $ 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)$

    Ce qui revient à démonter non seulement $P(0)$ , mais aussi $P(1)$ .

    Pour moi, c'est clair...

    Edit: il est évident que Wikipédia se trompe dans ce cas ...
    Edit2: j'ai ajouté des crochets pour éviter toute ambiguité.
  • J'aime bien l'exemple de Math Coss. Étant donné deux suites définies par récurrence, on peut toujours trouver une récurrence commune satisfaite par les deux.
  • 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.
  • Oui, il fallait mettre un autre indcice , disons $M_p(K)$ ...
  • @zeitnot

    Cella, je ne l'ai pas vu. Heureusement que c’était intentionnel de la part de acetonic.
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • "il fallait mettre un autre indice" signifie que ce n'était pas intentionnel ( une traitrise de l'habitude ), mais tous ceux qui liront l'aurons compris , car cela enlèverait l'intérêt du fil ... qui a déjà beaucoup fait écrire ..
    Cordialement
  • J'avais vu ton message ce matin. J'ai cru que c'était ça qu'il fallait "découvrir" au départ. ;-)
  • Quand le sage montre la lune, je suis du genre à m'attarder sur le doigt.
  • Je suis nul en français, j'ai pris intentionnel dans le sens involontaire
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Tu as confondu intentionnel et inintentionnel, sans doute par inattention, ce qui a rendu ta phrase inintelligible.
  • C'est surtout par ignorance
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Si on veut positiver, on peut noter que c'est un schéma de preuve classique où $H_1$ est vrai et où $H_1$ et $H_n$ entraînent $H_{n+1}$.

    Et effectivement, souvent il y a un $H_0$ (trivial et inutile) qui peut amener les élèves à oublier de démontrer $H_1$.
  • 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)$
  • Je pensais avoir compris que, pour éviter le principe de récurrence forte pour démontrer une propriété $P(n)$ à partir du rang $0$ , il suffisait de montrer que:

    $P(0)$ vraie et $P(0) \implies P(1)$
    $\forall n \in \N^* , ( P(n) \implies P(n+1) )$

    aléa semble dire la même chose, sauf mauvaise interprétation de ma part.

    Bien sûr, si $Q(n)$ est est la propriété $ ( \forall k \in \N , k \leq n, P(k) ) \implies P(n+1) $ on démontre que :
    $Q(0)$ vraie
    $\forall n \in \N^* , ( Q(n) \implies Q(n+1) )$

    Mais Wiki confond $P$ et $Q$ , a mon humble avis
    D'ailleurs dans mon message initial, j'applique correctement ce que dit Wiki... et j'obtiens un résultat absurde.

    Un shadock pourrait-il se tromper ? c'est rare ...

    Bonne journée à tous

    PS/ Je dois avoir fait les mêmes erreurs que dans le message signalé . Je vais réfléchir à cela ...mais à mon âge il faut du temps et on peut dire des inepties ...
  • 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.
  • OK ,
    Merci
  • 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 !
  • Oui , j'ai glissé bêtement de
    $ \forall k\ (k\leq n \implies P(k)) $
    à
    $[\forall k\ , k\leq n , P(k) ]=> P(n+1)$
  • 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 standard de récurrence forte, c'est l'existence d'une factorisation dans $\N$ : tout entier $n\ge2$ peut s'écrire comme produit de nombres premiers. Connaître la propriété pour un entier $n$ (et éventuellement son prédécesseur $n-1$) n'aide pas pour la démontrer pour $n+1$.
  • 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).
  • Bonjour,
    @Gabu
    Est ce qu'il y a une faute de frappe dans
    $\forall n\ ( (\forall k <n\ \ P(k))\implies P(n))$, alors $\forall n\ P(n)$
    extrait du ce message http://www.les-mathematiques.net/phorum/read.php?16,1575410,1575714#msg-1575714

    Moi ce que je reproche à wiki c'est qu'il y a une initialisation cachée sur P(1), je m'explique, wiki dit : Soit P(n) une propriété sur $\N$

    Si
    i)P(0)
    ii) Pour tout $n\in \N,\, [\forall k\leq n, P(k)]\implies P(n+1)$

    Alors $P(n);\forall n\in N$

    Si on applique ii) à n=0, alors on doit démontrer que $P(0)\Longrightarrow P(1)$ donc l'initialisation porte sur P(1) aussi puisque P(0) est vraie d'apres i)

    Je prefere ecrire l'enoncé de wiki de la facon suivante
    Si
    i)P(0), P(1)
    ii) Pour tout $n\in \N^*,\, [\forall k\leq n, P(k)]\implies P(n+1)$

    Alors $P(n);\forall n\in N$
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • 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.
  • @gebrane :

    1°) Où vois-tu une faute de frappe ? Je maintiens ce que j'ai écrit. Si ça te pose un problème, écris clairement quel est ton problème, comme ça je pourrai te détromper.

    2°) Tant que tu y es, tu pourrais aussi dire qu'il y a une initialisation cachée sur $P(2)$ puisqu'après avoir montré $P(0)$ et $P(1)$ il faudrait montrer $(P(0)\text{ et }P(1)) \implies P(2)$ etc..
    As-tu vraiment compris ce qu'est la récurrence ?
  • @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.
  • @Gabu

    J'ai pensé à
    $\forall n\ ( (\forall k \leq n\ \ P(k))\implies P(n))$, alors $\forall n\ P(n)$

    Dans ta formulation, $\forall n\ ( (\forall k <n\ \ P(k))\implies
    > P(n))$, alors $\forall n\ P(n)$
    pour n=0 ,$\{k\in\N, k<n\}=\emptyset$, donc je ne vois pas l'initialisation
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • 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)$.
  • @Gabu

    C'est la mon problème, notons Q la négation de P
    Puisque $\{k\in\N, k<n\}=\emptyset$ je peux dire aussi que $\forall k <0\ Q(k)$ est vrai, donc on a à la fois $\forall k <0\ P(k)$ est vrai et $\forall k <0\ P(k)$ est faux
    et pour éviter, j'ai pensé à remplacer < par $\leq $
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • 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$).
  • Ok
    Merci
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Même moi, dont le faible niveau en logique est bien connu, je sais ça ;-).
  • @Chaurien

    Pourquoi te compares-tu avec un étudiant? :-D
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!