Suites et Nombres premiers

[anthony_unac]

Bonjour,
On considère une suite définie pour tout par et
On considère la suite définie pour tout par
Montrer par récurrence que la proposition suivante est fausse : "Pour tout couple tel que est premier, est premier"

[samoufar]

Bonjour,

La négation de cette proposition est "il existe tel que...". Comme elle est fausse pour , c'est terminé.

Je ne vois pas l'utilité d'une récurrence ici

[anthony_unac]

Bonjour,
Il semblerait que je me sois mal exprimé néanmoins j'aimerais que vous me donniez la négation de cette proposition sans pointillés histoire de voir ou est ce que ça cloche.
L'idée était de montrer que tout couple tel que soit premier n'implique pas nécessairement que soit premier.

[samoufar]

Bonjour,

La proposition que vous donnez est :

"Pour tout couple tel que est premier, est premier"

Ce qui revient au même que
"Pour tout tel que est premier, est premier"

Par conséquent la négation de cette proposition est
"Il existe tel que est premier et n'est pas premier"


Cela repose essentiellement sur l'équivalence logique

Code: Tout sélectionner

¬(A ⇒ B) ≡ A ∧ (¬B)

où ¬ désigne "non" et ∧ désigne "et".


Pour en revenir au problème, il suffit donc d'exhiber un contre-exemple pour infirmer votre proposition, sans avoir recours à une quelconque récurrence (on a un "il existe" et non un "pour tout" dans la négation).

[nodgim]

@samoufar: la récurrence est une contrainte de l'énoncé, il faut bien faire avec...

[anthony_unac]

Ce qui revient au même que
"Pour tout tel que est premier, est premier"

Par conséquent la négation de cette proposition est
"Il existe tel que est premier et n'est pas premier"

Je suis ok avec ça, c'est imparable !
La démonstration avec un contre exemple est donc la voie royable dans cette configuration effectivement et je le possède déjà dans ma musette
Le défi serait de pouvoir démontrer la chose d'une autre manière (qu'à l'aide d'un contre exemple).
Le raisonnement par récurrence peut il être utilisé dans ce cas en supposant (phase d'hérédité) que si on considère que la proposition est vraie à un rang "n" cela n'implique PAS qu'elle soit vraie au rang "n+1" prouvant ainsi que la proposition est fausse.
J'avoue ne jamais avoir vu une démonstration par récurrence exécutée de cette manière (négative).
La manière la plus courante de démontrer une proposition (comme étant juste) étant de démontrer que vraie implique vraie.

[samoufar]

@samoufar: la récurrence est une contrainte de l'énoncé, il faut bien faire avec...

Sauf qu'ici la propriété à montrer est du type "il existe...", donc nécessite d'exhiber un n en particulier, alors que la récurrence sert à montrer une propriété du type "pour tout...".

La formule logique définissant la récurrence est

Code: Tout sélectionner

(P(n) ∧ (P(k) ⇒ P(k+1))) ⇒ ∀k ≥ n, P(k)

Le résultat serait donc quelque chose de valable pour tout entier, ce qui n'est pas ce que l'on cherche...

[anthony_unac]

Sauf qu'ici la propriété à montrer est du type "il existe...", donc nécessite d'exhiber un n en particulier, alors que la récurrence sert à montrer une propriété du type "pour tout...".

Oui celle ci par exemple (qui est fausse) :
"Pour tout tel que est premier, est premier"

La formule logique définissant la récurrence est

Code: Tout sélectionner

(P(n) ∧ (P(k) ⇒ P(k+1))) ⇒ ∀k ≥ n, P(k)

La on touche au coeur du problème, pouvons nous démontrer qu'une propriété (est fausse) à l'aide d'une non implication :
(P(n) ∧ (P(k) ¬⇒ P(k+1))) ⇒ ∀k ≥ n, ¬P(k)
A moins que la négation (concernant l'implication) ne s'écrive comme ceci :
(P(n) ∧ ¬(P(k) ⇒ P(k+1))) ⇒ ∀k ≥ n, ¬P(k)
Cette dernière étant alors logiquement équivalente (d'après les règles que vous m'avez enseignées) à :
(P(n) ∧ (P(k) ∧ ¬P(k+1))) ⇒ ∀k ≥ n, ¬P(k)

En gros pour revenir au problème on cherche à démontrer la fausseté de la proposition :
"Pour tout tel que est premier, est premier"
On montre qu'elle est vraie à un certain rang (mettons pour r=1) est vraie
Puis on considère qu'elle est vraie à un certain rang ( vraie) mais que ceci n'implique PAS qu'elle est vraie au rang suivant
Pouvons nous conclure que la proposition est fausse ?

[Pseuda]

Le raisonnement par récurrence peut il être utilisé dans ce cas en supposant (phase d'hérédité) que si on considère que la proposition est vraie à un rang "n" cela n'implique PAS qu'elle soit vraie au rang "n+1" prouvant ainsi que la proposition est fausse.
J'avoue ne jamais avoir vu une démonstration par récurrence exécutée de cette manière (négative).
La manière la plus courante de démontrer une proposition (comme étant juste) étant de démontrer que vraie implique vraie.

Bonjour,

Il me semble que cette proposition est erronée. En effet, une non implication ne prouve rien, ou autrement dit, on ne peut rien conclure avec une non implication.

Pour prendre un exemple simple, si on prend la suite .

On a la proposition suivante : . Cette proposition est vraie.

Cette suite peut être redéfinie en : .

n'implique pas : , car : n'implique pas :

La proposition vraie au rang n n'implique pas qu'elle est vraie au rang n+1, et pourtant cette proposition est vraie.

Ce ne serait pas plutôt : "si on considère qu'elle est fausse à un rang n, cela implique qu'elle est fausse au rang n+1" ? Dans ce cas, c'est une récurrence positive (il suffit de considérer la contraposée, qui est vraie).

Ne pas confondre : "implique que non pas" et n'implique pas".

Donc, à mon avis, la récurrence négative n'a aucun intérêt, on ne peut rien conclure avec.

Bonne journée.

[bolza]

La formule logique définissant la récurrence est

Code: Tout sélectionner

(P(n) ∧ (P(k) ⇒ P(k+1))) ⇒ ∀k ≥ n, P(k)

La on touche au coeur du problème, pouvons nous démontrer qu'une propriété (est fausse) à l'aide d'une non implication :
(P(n) ∧ (P(k) ¬⇒ P(k+1))) ⇒ ∀k ≥ n, ¬P(k)
A moins que la négation (concernant l'implication) ne s'écrive comme ceci :
(P(n) ∧ ¬(P(k) ⇒ P(k+1))) ⇒ ∀k ≥ n, ¬P(k)
Cette dernière étant alors logiquement équivalente (d'après les règles que vous m'avez enseignées) à :
(P(n) ∧ (P(k) ∧ ¬P(k+1))) ⇒ ∀k ≥ n, ¬P(k)

En gros pour revenir au problème on cherche à démontrer la fausseté de la proposition :
"Pour tout tel que est premier, est premier"
On montre qu'elle est vraie à un certain rang (mettons pour r=1) est vraie
Puis on considère qu'elle est vraie à un certain rang ( vraie) mais que ceci n'implique PAS qu'elle est vraie au rang suivant
Pouvons nous conclure que la proposition est fausse ?

La négation de c'est , il n'y a pas de ""

ensuite dans la formule de récurrence il manque un quantificateur, c'est :


Si maintenant tu veux savoir si


alors c'est vraisemblablement faux pour plusieurs raisons :
d'abord
ça veut seulement dire qu'ils existe quelques entiers (pas forcément tous) pour lesquels il n'y a pas hérédité.
Ensuite on peut très bien imaginé une propriété qui est vrai pour 5 entiers consécutifs, fausse pour les 3 entiers suivant, vrais pour les quinze entiers suivant, ...
Ici la propriété d'hérédité sera clairement fausse et pourtant tu trouvera toujours des intervalles d'entiers qui la vérifie...

[anthony_unac]

Merci à tous les intervenants pour cette discussion riche en enseignement

Voici une petite synthèse de ce qu'il faut retenir (n'hésitez pas à me corriger) :
- On peut démontrer la véracité d'une proposition du type : "Pour tout (à partir d'un certain rang), qqch... " à l'aide d'un raisonnement par récurrence.
- On peut démontrer la fausseté d'une proposition du type : "Pour tout (à partir d'un certain rang), qqch... " à l'aide d'un contre exemple sachant que démontrer la fausseté d'une proposition revient à démontrer la véracité de sa contraposée (j'utilise ce terme sans réellement le maîtriser) : "Il existe un tel que qqch ..."

En guise de conclusion, je vous propose de démontrer la fausseté de la proposition : "Tout entier pair est divisible par 3" à l'aide d'un (pseudo) raisonnement par récurrence tout en sachant que la bonne méthode est de donner un contre exemple.
Initialisation : La proposition est vraie au rang sachant qu'un entier pair s'écrit sous la forme , il vient : qui est divisible par donc est vraie.
Hérédité : On suppose la proposition vraie au rang vraie mais n'implique pas vraie.
est divisible par
n'est pas divisible par car n'est pas divisible par .
n'implique pas donc la proposition est fausse sauf que ce raisonnement lui même est faux !

[bolza]

Merci à tous les intervenants pour cette discussion riche en enseignement

Voici une petite synthèse de ce qu'il faut retenir (n'hésitez pas à me corriger) :
- On peut démontrer la véracité d'une proposition du type : "Pour tout (à partir d'un certain rang), qqch... " à l'aide d'un raisonnement par récurrence.
- On peut démontrer la fausseté d'une proposition du type : "Pour tout (à partir d'un certain rang), qqch... " à l'aide d'un contre exemple sachant que démontrer la fausseté d'une proposition revient à démontrer la véracité de sa négation (j'utilise ce terme sans réellement le maîtriser) : "Il existe un tel que qqch ..."

la contraposé c'est autre chose qui concerne l'implication :
la contraposé de est
en logique classique, une implication et sa contraposé sont équivalentes.
Le "raisonnement par contraposé" (ou contraposirtion) consiste à prouver
à la place de car c'est parfois plus simple.

Note : dans ta preuve, le 2n+2 est un contre exemple que tu peux utiliser
pour dire que la proposition est fausse

[Pseuda]

En guise de conclusion, je vous propose de démontrer la fausseté de la proposition : "Tout entier pair est divisible par 3" à l'aide d'un (pseudo) raisonnement par récurrence tout en sachant que la bonne méthode est de donner un contre exemple.

Bonjour,



La négation de "Tout entier pair est divisible par 3" est : "Il existe au moins un entier pair qui est non divisible par 3".

Tu vas avoir du mal à démontrer cette dernière proposition (qui commence par "il existe") par une quelconque récurrence.....

Quand je parlais de contraposée, je voulais parler d'une proposition exprimée par une négation (je me suis mal exprimée), par exemple : "Tout entier de la forme 2n+1 n'est pas divisible par 2 ".

Allons-y. Cette proposition est vraie pour n=0. Si 2n+1 n'est pas divisible par 2, alors 2(n+1)+2 = 2n+3 ne l'est pas non plus, car si 2n+3 était divisible par 2, comme 2 est divisible par 2, donc 2n+3-2=2n+1 le serait, donc contradiction.

Tout cela pour dire (comme dit Bolza) que le "n'implique pas" n'existe pas en mathématiques.

[anthony_unac]

Bonjour,
Nous sommes d'accord
Ceci dit et pour revenir sur le défi (message d'origine), il tient toujours
On considère une suite définie pour tout par et
On considère la suite définie pour tout par
Montrer que la proposition suivante est fausse : "Pour tout tel que est premier, est premier"

[Pseuda]

Effectivement, cela reste à démontrer, et pas par une récurrence .

Par contre, je ne suis pas d'accord avec Samoufar quand il dit :

Bonjour,

La négation de cette proposition est "il existe tel que ...". Comme elle est fausse pour , c'est terminé.

Pour n=1, 2n+1 = 3 premier, et premier, mais cela ne prouve pas qu'il existe n tel que 2n+1 premier, et pas premier? ni le contraire ?

[anthony_unac]

Nous sommes d'accord, le véritable défi ici est de trouver tout "simplement" le contre exemple (comme le disait Samoufar depuis le début). Sauf que ce contre exemple n'est pas et il le sait

[Pseuda]

Il va être difficile de trouver un contre-exemple, car la suite monte très vite. Il vaut mieux, à mon avis, essayer de le démontrer directement.

Mais je ne vois toujours pas comment on peut démontrer par récurrence qu'une proposition qui commence par "Pour tout n, ..." est fausse. Pour démontrer que c'est faux, il n'y a pas d'autre moyen que de montrer : "Il existe n...", et cela ne peut pas se montrer par récurrence.

Sauf à montrer l'initialisation (il existe tel que ...), et que s'il existe n tel que..., alors il existe n' plus grand que n tel que..., idiot, l'initialisation suffit.

[nodgim]

Sauf erreur:
u13 = 1 [5] et 1 [4] (la puissance de 13 est 0 [4], donc Fermat dit que a^4 = 1 [5])
u14 [5] = 4 ^ (1+4k) = 4 [5]
donc v13 = 0 [5].

[samoufar]

Oui effectivement n'est pas le bon contre-exemple, au temps pour moi

Et oui, il est très difficile de trouver un contre-exemple (sauf peut-être en utilisant les congruences à bon escient) puisque pour , ou la propriété est vraie (et au delà explose ).

[anthony_unac]

Et oui explose et très vite et c'est voulu (par son auteur un poil sadique)
On est d'accord qu'il n'y a pas d'autre issue que de trouver ce fichu contre exemple pour démontrer la fausseté de la proposition (chose qu'avait fait Euler en son temps vis à vis de la proposition de Fermat).
Je vous proposerai à la fin une démo toute simple pour dénicher ce contre exemple qui n'utilise même pas les congruences.