Un théorème sur la récurrence (L1)

blbl · January 2019

Bonjour,

Je tente depuis hier soir de comprendre la preuve du théorème suivant (issu du chapitre arithmétique du Ramis/Warusfel), en particulier j'ai du mal à identifier l'hypothèse de récurrence (plus généralement toute la preuve m'échappe) - un peu d'aide serait bienvenue .

Merci par avance. 83946

gerard0 · January 2019

Bonjour.

Avant de commencer, peux-tu dire ce que vaut f(1) ? f(2) ? f(5) ?
Puis relis la démonstration (je trouve ça plutôt lourd, écrit de façon un peu cavalière, mais ça a un sens).

A noter : Ce n'est pas une preuve par récurrence (il n'y a pas d'entier qui définisse f), mais une partie de la preuve se fait par récurrence.

Cordialement.

blbl · January 2019

Bonjour, merci d'avoir répondu,

f(0) = a (par définition)
f(1) = f(0 + 1) = g(f(0)) = g(a)
f(2) = f (1 + 1) = g(f(1)) = g(g(a))

jusqu'à f(n) = (g°...n fois...° g)(a)

(pardon si je n'ai pas su voir la direction qu'indiquent ces quelques résultats)

(je vais mieux préciser ce que je ne comprends pas dans la preuve :

Premièrement je n'ai pas de schéma général clair, en grandes étapes de la démonstration,
la première étape me semble évidente (même si je ne comprends pas pourquoi on s’intéresse à la restriction sur [0,n]), d'ailleurs en parlant de la restriction l'initialisation à n = 0 énoncée s'écrirait donc :

f(0) restreinte à [0,0] = a et f (m + 1) restreinte à [0,0] = g(f(m) restreinte à [0,0]) ?

Mais si f est restreinte à [0,0] elle ne peut donc pas prendre d'argument m autre que 0, donc f(m + 1) resteinte à [0,0] n'est pas définie (non ?)
(ce qui me fait dit que j'intreprete très mal ce qui est initialisé ici, et ça m'aiderait beaucoup d'avoir un éclairage là dessus pour débuter).

Cordialement.

gerard0 · January 2019

Difficile de comprendre ce que tu veux dire, soit tu mélanges arguments (ce qui est dans la parenthèse de fonction) et indice, soit tu ne parles pas de la démonstration.
Rappel : Il y a un bouton x₂ pour écrire les indices. Donc même si tu ne maîtrises pas LaTeX, qui est plus simple d'emploi, tu peux faire la différence entre $f$ et $f_n$.

La propriété qui est prouvée par récurrence est : Pour tout entier n, il existe une fonction $f_n$ telle que $f_n(0)=a$ et, pour tout entier positif m, $m<n,\ \Rightarrow f_n(m+1)=g(f_n(m))$

Pour l'initialisation (n=0), $f_0(0)=f(0)=a$ et la propriété $m<n,\ \Rightarrow f_n(m+1)=g(f_n(m))$ est vraie puisque m<0 n'est pas possible : Tu ne pourras jamais trouver un contre exemple !!

blbl · February 2019

Merci encore pour votre patience,
Je comprends peut être mal le raisonnement par récurrence alors.

Etant donnée la proposition que vous avez énoncé,

l'initialisation ne conduit-elle pas à vérifier les points suivants pour n = 0 ?

(i) f₀(0) = f(0) = a
(ii) m < 0 => f₀(m +1) = g(f₀(m))

Mon incompréhension est alors : puisque m > 0, alors ce qui est impliqué : "f₀(m +1) = g(f₀(m))" n'est pas vrai, et donc on échoue à prouver par récurrence non ? ou alors la condition (ii) est le fruit de ma mauvaise application du raisonnement par récurrence ?

edit : en relisant je crois comprendre que dire :

m < 0 est fausse => f₀(m +1) = g(f₀(m)) fausse

revient à dire (par définition de =>) que [m < 0 => f₀(m +1) = g(f₀(m))] est vrai (l'énoncé : 'chose fausse => autre chose fausse' est vrai) et donc l'initialisation marche, ai-je compris ?

Cordialement.

gerard0 · February 2019

Oui, c'est ça.

Si A est une proposition fausse, et B une proposition, par définition de l'implication, A ==> B est une proposition vraie. (C'est B ou nonA, et nonA est vraie).
Une autre façon de voir est que si A est une propriété, $\forall x \in \emptyset, \ A$ est vraie puisque son contraire ($\forall x \in \emptyset, \ \text{non}A$) est manifestement faux. Et ici, ta propriété est $\forall m\in\{m\in\mathbb N/m<0\},\ f_n(m+1)=g(f_n(m))$.

Cordialement.

Un théorème sur la récurrence (L1)

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 27