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)
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)
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.
Cordialement.
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
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$
@gebrane
Relis le message de @Chaurien.
Il suffit de modifier la propriété P(n) pour y inclure tous les entiers inférieurs à n.
J'ai arrêté la lecture à "elle ne sert à rien".
Etes-vous convaincus?:-D
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.
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
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.
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".
> 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)
Cordialement.
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.
En tout cas, maintenant c'est fait.
Cordialement.
@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é.
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.
Cella, je ne l'ai pas vu. Heureusement que c’était intentionnel de la part de acetonic.
Cordialement
Et effectivement, souvent il y a un $H_0$ (trivial et inutile) qui peut amener les élèves à oublier de démontrer $H_1$.
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)$
$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 ...
> 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.
Merci
$ \forall k\ (k\leq n \implies P(k)) $
à
$[\forall k\ , k\leq n , P(k) ]=> P(n+1)$
$ \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.
@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 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
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.
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 ?
@ 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.
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
$\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)$.
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 $
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$).
Merci
Pourquoi te compares-tu avec un étudiant? :-D