Bonjour

Soit, pour n entier naturel, P(n) le prédicat à démontrer. Il te suffit de noter .

Mais il n'y a pas de prédicat ici. Je n'ai pas trop compris.

est une partie de quelconque.

Le but de la démonstration par récurrence, c'est de démontrer que le prédicat P d'une variable entier naturel, est vrai.
Autrement dit que pour tout n entier naturel, P(n) (est vrai).

Dans ton théorème rappelé, A est une partie de quelconque.
Eh bien oui j'en prends une particulière.

Le principe de récurrence est démontré dans mon livre. C'est le suivant :
Soit un prédicat défini sur . Si est vrai et si alors est vraie pour tout entier naturel.

Sauf que ce n'est pas ça qui m'intéresse, j'aimerais comprendre comment prouver le résultat suivant qui est donné sans preuve dans mon livre :

Si est une partie de contenant et telle que :

alors

salut

peux-tu exhiber un entier qui ne soit pas dans A ?
peux-tu prouver que 10 000 appartient à A ?

Bonjour,

Soit le complémentaire de dans . Si , alors la propriété est démontrée. Supposons non vide. L'on sait alors que posséderait un plus petit élément, noté . D'autre part, vu que , serait distinct de et posséderait donc un prédécesseur strictement inférieur à tout élément de . Ainsi aurait-on , ce qui avec



donnerait finalement ; d'où une contradiction avec notre hypothèse. Ainsi a-t-on nécessairement.

Quel est le titre de ton ouvrage ?

Ah pardon, je pensais que tu disais vouloir en déduire le principe de raisonnement par récurrence (ce qui n'est pas tout à fait la propriété énoncée par ailleurs).

On va donc démontrer cela sans le raisonnement par récurrence.

Supposons non vide ; c'est une partie de et nous notons donc ( car ). Par contraposition , ce qui contredit la définition de .

Devancé par ThierryPoma.

on peut même "utiliser la récurrence" pour montrer la récurrence sans même avoir à parler de minimum ou de maximum ou quoi que ce soit

si N/A n'est pas vide alors soit n un élément de N/A

considérons alors l'entier n - 1 :

alors il y a deux cas :

soit n - 1 appartient à N/A et on recommence avec n - 1

soit n - 1 appartient à A ... mézalor n - 1 +1 appartient à A


de toute façon ne pas utiliser la récurrence c'est en fait utiliser la récurrence parce qu'on ne monte pas mais on descend  et que N a le bon gout d'être minoré donc on est obligé de s'arrêter à 0 (utilisation d'un minimum à un instant du raisonnement <=> descendre (= récurrence) jusqu'à ... l'absurde : la contradiction)



en espérant que Ramanujan saura ronger l'os et en tirer la substantifique moelle ...

J'ai une petite question dans la démonstration du théorème suivant :

Soit un prédicat défini sur . Si est vraie et si : alors la propriété est vraie pour tout entier naturel .

Démonstration :
Supposons que n'est pas vérifiée sur . Alors est une partie non vide de , elle admet donc un plus petit élément noté .

Comme est vraie, donc . Comme donc .

est vraie donc est vraie soit d'où une contradiction.

Je n'ai pas compris l'intérêt de démontrer que .

Bonjour,

Si alpha = 0 , alpha - 1 n'appartient pas à N.

Or, P est défini sur N, donc on n'aurait pas pu écrire P (alpha - 1)

Ne vois-tu pas que c'est exactement la même démonstration que ce qu'on t'a proposé sur ta question précédente ?...

Confer mon premier message : une fois ta proposition démontrée, le principe de raisonnement par récurrence s'en déduit immédiatement.

Jezebeth @ 07-07-2019 à 16:39

Il te suffit de noter .

Donc de deux choses l'une :
- ou bien ton livre fait d'abord cette démonstration du raisonnement par récurrence avant de caractériser l'ensemble des entiers naturels en disant que toute partie contenant 0 et étant inductive est cet ensemble entier.
Dans ce cas ton résultat originel est trivial, puisque si A contient 0 et est inductive, par récurrence A contient ... ;
- ou bien ton livre commence par la démonstration de la caractérisation, et pas besoin de se casser la tête, le principe de raisonnement par récurrence en découle tout seul.

Cela rejoint la remarque de carpediem ; de grâce, un peu de bon sens : ne faisons pas les mêmes raisonnements plusieurs fois et soyons logiques dans l'enchaînement des résultats établis.

@Jezebeth
Oui les démonstrations se ressemblent.

Le livre fait d'abord la caractérisation des entiers en listant les propriétés admises, puis il donne le principe de récurrence (sans le démontrer) qu'a démontré Thierry Poma et enfin il donne le théorème de la récurrence avec le prédicat (celui-ci est démontré).

Elles ne se ressemblent pas juste, elles sont identiques, j'insiste !

Et c'est un peu idiot comme présentation des choses, je trouve. (Mais bon, les Dunod ne sont pas réputés pour leur finesse mathématique !)

Rebonjour,

Je rappelle le théorème 12 :
Soit un prédicat défini sur . Si est vrai et si alors est vraie pour tout entier naturel.

J'ai une nouvelle question concernant la récurrence à partir d'un entier . Je n'ai pas compris comment on applique le théorème 12. Déjà le théorème 12 commence par "si est vraie" or ici le prédicat n'est pas défini pour

Si est défini sur   avec :
vraie et
Alors le théorème 12 appliqué à nous donne :

Pose Q(n) = P(n0 + n)

tu devrais aller voir des exemples concrets (= des exercices) pour mieux comprendre les choses ...

ainsi par exemple je te propose les deux exercices classiques qui permettent de bien distinguer ce qui se passe entre l'initialisation et l'hérédité :

EX 1 : Soit n un entier naturel et P(n) la proposition
1) vérifier P(n) pour n {0, 1, ..., 10}
2) Montrer que la proposition P(n) est héréditaire à partir d'un certain rang à déterminer.
4) Pour quels entiers la proposition est-elle vraie ? Justifier.

EX 2 : Soit n un entier naturel et P(n) la proposition
1) vérifier P(n) pour n {0, 1, ..., 10}
2) Résoudre dans IR l'inéquation
3) en déduire que la proposition est héréditaire à partir d'un certain rang à déterminer.

4) Pour quels entiers la proposition est-elle vraie ? Justifier.

@Carpediem
Avant de m'attaquer à vos exos, je vais essayer de démontrer le résultat général de la récurrence à partir d'un entier en utilisant la remarque de Lionel.

Posons :

Là je m'emmêle les pinceaux avec le

J'ai résolu les exos de mon livre facilement, j'ai des difficultés dans les démonstrations générales...

Exemple :
Montrer qu'à partir d'un certain rang on a :
J'ai réussi à appliquer le principe de récurrence à partir d'un

que vaut Q(0) ? Q(1) ?, Q(2) ? ...

SI je veux appliquer le théorème à . On suppose vraie.
Mais comment savoir sur quoi est définie ?

Puis on suppose que si

Alors est vraie pour tout

Pas compris non plus comment on passe de :

vraie et :

A :

vraie et

Tkt pas je comprends même avec mon indication c'est assez compliqué comme exercice il faut voir que

  est vraie pour tout n, alors est vraie pour tout n, donc vraie pour tout . C'est assez compliqué à voir, ça demande beaucoup de reflexion d'arriver à un tel résultat, même le major de Polytechnique galère avec ça.

Et puis toujours la même remarque sur la propriété en rouge, mais visiblement tu n'as vraiment pas envie de t'en servir...

Sur le même modèle, on montre que si A est une partie de contenant et étant inductive, alors A est !

@Jezebeth
En pratique, on n'utilise jamais la propriété en rouge non ?

Encore une question sur la récurrence d'ordre 2 :

Soit une propriété définie sur avec et vraies ainsi que :



Alors la propriété est vraie pour tout .

Je n'ai pas compris la remarque du livre : il suffit d'appliquer le théorème 12 à la propriété.

Je ne vois pas comment appliquer le théorème 12 à

donc tu n'as pas compris le raisonnement par récurrence ...

le raisonnement par récurrence est constitué de deux arguments concernant une propriété dépendant d'un entier P(n) :

a/ une initialisation ... pour un certain entier ...(une trivialité sans intérêt mais nécessaire)
b/ l'hérédité de la propriété : P(n) => P(n + 1) ... (l'exercice ou activité mathématique par excellence)

b/ ne consiste pas à montrer que P(n) est vraie mais que : si P(n) est vraie alors P(n + 1) est vraie (on démontre donc la véracité de l'implication)

je te propose ces deux classiques :

1/ montrer que les propriétés :

a/ est multiple de 9

b/ est multiple de 9

sont héréditaires

2/ quelle propriété est vraie ?

Salut Ramanujan.

Tu poses et tu appliques ton théorème 12 avec .

C'est quoi ? Et c'est quoi l'hérédité dans ce cas ?

Bonjour

Ramanujan @ 08-07-2019 à 18:14

lionel52 @ 08-07-2019 à 14:16

Tkt pas je comprends même avec mon indication c'est assez compliqué comme exercice il faut voir que

est vraie pour tout n, alors est vraie pour tout n, donc vraie pour tout . C'est assez compliqué à voir, ça demande beaucoup de reflexion d'arriver à un tel résultat, même le major de Polytechnique galère avec ça.

Ok merci.

@Carpediem

Pour la a :

Supposons que est vraie à un rang .

Posons : : il existe un entier relatif tel que :



D'après l'hypothèse de récurrence :
La propriété est héréditaire.

Or est un multiple de 9, la propriété est vraie donc est vraie.

Pour la b :

Supposons que est vraie à un rang .

Posons : : il existe un entier relatif tel que :



D'après l'hypothèse de récurrence :
La propriété est héréditaire.

Or n'est pas un multiple de 9, la propriété est fausse donc n'est pas vraie pour tout entier

Bonsoir,

P(n) n'est pas vraie pour tout entier n: Exact
Mais, elle pourrait être vraie à partir d'un rang autre que 0.
A toi de le dire dans la démonstration

C'est 9 à la place de p erreur de frappe.

Ah oui vous avez raison car

Ah merci du coup j'ai compris la méthode, ça marche aussi pour la récurrence forte.

Soit une propriété définie sur avec vraie ainsi que :



Alors est vraie pour tout .

Il suffit d'appliquer le théorème 12 avec
Donc

C'est l'idée.

des démonstrations bien maladroites ...

   et l'hypothèse de récurrence permet de conclure que la propriété P est héréditaire ... par combinaison linéaire

   et l'hypothèse de récurrence permet de conclure que la propriété Q est héréditaire ... par combinaison linéaire


d'autre part P(0) est vraie donc par (le théorème de récurrence) P est vraie pour tout n

de plus on sait que    ce qui montre trivialement que est multiple de 9 (cours de première et sans utiliser le principe de récurrence)

enfin Q(0) est fausse, Q(1) est fausse, ..., Q(n) est fausse ... pour tout n en fait ...

on ne peut pas initialiser mais on ne sait pas si Q(n) est vraie pour un certain entier n

or

et (on sait que) 9 divise donc si 9 divise alors par combinaison linéaire 9 diviserait 2 ... contradiction

donc cette fois ci on est certain que Q(n) est fausse pour tout n

Petite correction cinq ans après la guerre :

Jezebeth @ 08-07-2019 à 16:55

Sur le même modèle, on montre que si A est une partie de contenant et étant inductive, alors A est !