Annuler
connectez vous
logique en post-bac
- Description de mathématique formelle-termes et relations
- Théorèmes
- Théories logiques
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Espaces vectoriels et Applications linéaires - supérieur
- Un best-of d'exos de probabilités (après le bac)
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... LogiqueTopics traitant de logique [tout]Lister tous les topics de mathématiques
Niveau Prepa (autre)
Récurrence forte
Posté par jacksparrow
Bonjour /Bonsoir à vous,
Je suis un étudiant en classe préparatoire intégrée et j'ai quelques difficultés quant à un exercice donné en classe.
L'énoncé est le suivant:
Montrer par une récurrence forte que pour tout entier naturel n non nul, il existe deux entiers naturels p et q tels que:
n = 2p*(2q+1)
Voici ce que j'ai réalisé :
___________________________________________
On veut montrer 
n
*, 
p, q | n = 2p*(2q+1)
Initialisation:
Pour n = 1
P(1): 1 = 2p*(2q+1)
1 = 20*(2*0+1)
1 = 1*1
Pour n = 2
P(2): 2 = 2p*(2q+1)
2 = 21*(2*0+1)
2 = 2*1
La propriété est vérifiée pour les premiers termes
Hérédité:
Supposons qu'il existe n tel que P(n) et montrons P(n+1)) : il faut supposer que P(k) est vraie pour tout entier k entre 1 et n et démontrer P(n+1)
Nous devons considérer deux cas :
* n+1 n'est pas premier ;
* n+1 est premier.
______________________________________
A partir de là, je suis totalement bloqué et je n'arrive pas à continuer. Mon professeur de mathématiques m'a confirmé que mon début de trace sur l'hérédité était juste.
Serait-il, donc, possible d'avoir un déblocage afin que je puisse terminer l'exercice s'il vous plaît ?
Cordialement
Bonjour. Déjà ce n'est pas "Supposons qu'il existe n tel que P(n) et montrons P(n+1))" car d'une part l'hérédité ne démarre jamais par "il existe" mais par "quelque soit" et d'autre part tu veux faire une récurrence forte...
Ta rédaction doit commencer par un truc du genre "Donnons nous un entier naturel non nul n" puis "Supposons P(k) pour tout entier k entre 1 et n, montrons P(n+1)". Ensuite, pour prouver P(n+1), la primalité de n+1 ne va pas t'être très utile. Je te propose plutôt de t'intéresser à la parité : que se passe-t-il si n+1 est pair ? impair ?
salut
si la primalité joue un rôle !!!
l'hypothèse de récurrence est :
(à rédiger (un peu) mieux : p et q dépendant de k bien sur)
soit n + 1 est premier et n + 1 = ...
soit n + 1 n'est pas premier et ...
J'avoue que je commence à être un peu perdu donc j'ai réalisé ceci :
Hérédité:
On veut P(N): k
n, p, q | k = 2p(2q+1)
°Si n+1 est premier alors n+1= 2k+1
P(N+1): 2k+1= 2p'(2q'+1)
2k = 2p'(2q'+1) -1
k = (2p'(2q'+1) -1)/2
°Si n+1 n'est pas premier alors n+1= 2k
P(N+1): 2k = 2p'(2q'+1)
k = 2p'-1(2q'+1)
On pose p'-1= p'' :
k = 2p''(2q'+1)
Citation :
°Si n+1 n'est pas premier alors n+1= 2k
un peu de sérieux !!!
°Si n+1 n'est pas premier alors n+1= 2k
si n + 1 = 9 tu crois qu'on peu l'écrire 2k ?
qu'est-ce qu'un nombre premier ?
qu'est-ce qu'un nombre non premier ? (pourquoi on s'impose une récurrence "forte" ?)
Pour répondre: un nombre premier est un nombre qui ne peut être divisé que par lui-même ou par 1.
En réalité, je n'ai pas vu la récurrence forte en cours ( croyez le ou non ) donc j'ai fait des recherches à la "va-vite" et peut-être que c'est cela qui fait que je ne comprends pas.
Je suis à la fois reconnaissant pour vos réponses et désolé en même temps.
Je ne vois pas du tout dans quelle direction je dois chercher...
Ah bon on a besoin de la primalité ??? C'est clairement plus direct avec la parité...
Si n+1 est impair, n est pair et s'écrit n=2k, je choisis un tel k, puis j'écris n+1=2^0(2k+1).
Sinon, si n+1 est pair, on peut écrire n+1=2k, mais alors k est plus petit que n (et non nul), par hypothèse de récurrence forte k s'écrit 2^p(2q+1) puis n+1 = 2^(p+1)(2q+1)...