Principe de récurrence

Aide à la résolution d'exercices ou de problèmes de niveau Lycée.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

Principe de récurrence

Messagepar adem19s » Mercredi 08 Avril 2015, 11:02

Pour démontrer qu'une propriété $P(n)$ est vraire pour tout $ n\geq n_0$.
1.je vérifie que $P(n_0)$ est vraie.
2. je suppose que $P(n)$ est vraie pour un nombre $n\geq n_0 $ et je démontre que $P(n+1)$ est vraie.
ce que je veux savoir est ceci:
lorsque je suppose que $P(n)$ est vraie pour $n\geq n_0 $ c'est à dire je suppose qu'il existe un nomb$n\geq n_0$ tel que $P(n)$ est vraie.
...merci.
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Publicité

Re: Principe de récurrence

Messagepar evariste_G » Mercredi 08 Avril 2015, 13:15

Bonjour.

Le principe de récurrence repose sur le fait que si : $P(n_0)$ est vraie (initialisation) et ($P(n)$ est vraie implique $P(n+1)$ est vraie pour un $n\geqslant n_0$) [hérédité] alors $P(n)$ est vraie pour tout $n\geqslant n_0$.
Mathématiques, LaTeX et Python : http://www.mathweb.fr
Cours de math, aide à distance : https://cours-particuliers-bordeaux.fr/
evariste_G
Téra-utilisateur
 
Messages: 1408
Inscription: Vendredi 19 Décembre 2008, 19:13
Localisation: Bordeaux
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar adem19s » Mercredi 08 Avril 2015, 20:07

evariste_G a écrit:Bonjour.

Le principe de récurrence repose sur le fait que si : $P(n_0)$ est vraie (initialisation) et ($P(n)$ est vraie implique $P(n+1)$ est vraie pour un $n\geqslant n_0$) [hérédité] alors $P(n)$ est vraie pour tout $n\geqslant n_0$.

alors on suppose que $P(n)$ est vraie à un rang $n$..et puis on démontre que $P(n+1)$ est vraie.
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar balf » Samedi 11 Avril 2015, 15:48

On suppose que $\mathcal P(n)$ soit vraie pour un $n$ quelconque ($\geqslant n_0$).

B.A.
balf
Zetta-utilisateur
 
Messages: 3804
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Principe de récurrence

Messagepar adem19s » Samedi 11 Avril 2015, 20:25

balf a écrit:On suppose que $\mathcal P(n)$ soit vraie pour un $n$ quelconque ($\geqslant n_0$).

B.A.

on suppose que la proposition $P$ est vraie à un rang $n$.($n$ fixé et $\geqslant n_0$).
c'est à dire la proposition $P(k)$est vraie pour $k=n_0,n_0+1,.....,n $.
le $n$ doit etre fixé puis on démontre que $P(n+1)$ est vraie.
pour etre précis on suppose que la proposition est vraie sur un ensemble fini..$E$=$\left\lbrace n_0,n_0+1,....,n \left\rbrace $.
bien sur $E \subset \mathbb{N}$.
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar balf » Samedi 11 Avril 2015, 23:11

C'est la récurrence forte.

Je voulais insister sur le fait que l'hypothèse de récurrence, forte ou « faible » doit être spécifiée pour un entier $n$, ou jusqu'à un entier $n$ quelconque (mais bien entendu fixé. Il n'est pas rare que les élèves ne comprennent pas pour quoi il y a quelque chose à démontrer, uisqu'on suppose que $\mathcal P(n)$ soit vraie.

B.A.

P.-S. — une petite précision : « supposer que », au sens de « faire une hypothèse », est construit avec le subjonctif.
Dernière édition par balf le Mercredi 15 Avril 2015, 21:38, édité 1 fois.
balf
Zetta-utilisateur
 
Messages: 3804
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Principe de récurrence

Messagepar adem19s » Mardi 14 Avril 2015, 09:16

balf a écrit:C'est la récurence forte.

Je voulais insister sur le fait que l'hypothèse de récurrence, forte ou « faible » doit être spécifiée pour un entier $n$, ou jusqu'à un entier $n$ quelconque (mais bien entendu fixé. Il n'est pas rare que les élèves ne comprennent pas pour quoi il y a quelque chose à démontrer, uisqu'on suppose que $\mathcal P(n)$ soit vraie.

B.A.

P.-S. — une petite précision : « supposer que », au sens de « faire une hypothèse », est construit avec le subjonctif.

Ce qui concerne le premier principe de récurrence où la récurrence faible lorqu'on suppose que $P(n)$ est vraie au rang $n$ cela veut dire tout simplement
que seulement $P(n)$ est vraie , les autres propriétés $P(n-1)$,$P(n-2)$......etc. On ne peut pas les considérer comme vraies ou meme
les utiliser pour démontrer que $P(n+1)$ est vraie...c'est ça?
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar Clog » Mardi 14 Avril 2015, 14:37

Bonjour :)

La récurrence se fait en deux étapes, en effet. La première consiste à montrer que la propriété est vraie pour le premier rang, ici $n_0$.
La deuxième étape se montre sans utiliser la première. Tu supposes que la proposition est vraie pour un certain $n \geq n_0$ quelconque, mais tu ne supposes effectivement rien sur les rangs compris entre $n_0$ et $n$. Tu dois alors montrer que dans ce cas, la proposition est vraie pour le rang $n+1$.

Tu peux alors conclure que la propriété est vraie pour n'importe quel $n \geq n_0$, puisque tu as montré qu'elle était vraie pour $n_0$ ET que si elle était vraie à un rang, elle l'était au rang suivant ; Si elle est vraie pour $n_0$, elle est vraie pour $n_0 +1$. Si elle est vraie pour $n_0 +1$, elle est vraie pour $n_0 +2$, etc...
Clog
Déca-utilisateur
 
Messages: 19
Inscription: Lundi 11 Février 2013, 19:11
Statut actuel: Post-bac | Doctorat

Re: Principe de récurrence

Messagepar adem19s » Mercredi 15 Avril 2015, 09:06

Clog a écrit:Bonjour :)

La récurrence se fait en deux étapes, en effet. La première consiste à montrer que la propriété est vraie pour le premier rang, ici $n_0$.
La deuxième étape se montre sans utiliser la première. Tu supposes que la proposition est vraie pour un certain $n \geq n_0$ quelconque, mais tu ne supposes effectivement rien sur les rangs compris entre $n_0$ et $n$. Tu dois alors montrer que dans ce cas, la proposition est vraie pour le rang $n+1$.

Tu peux alors conclure que la propriété est vraie pour n'importe quel $n \geq n_0$, puisque tu as montré qu'elle était vraie pour $n_0$ ET que si elle était vraie à un rang, elle l'était au rang suivant ; Si elle est vraie pour $n_0$, elle est vraie pour $n_0 +1$. Si elle est vraie pour $n_0 +1$, elle est vraie pour $n_0 +2$, etc...

Je considère la suite de Fibonacci : $u_0=u_1=1$ et $u_{n+2}=u_{n+1}+u_n$.
Soit $P(n)$:$ u_n$ est un entier naturel.
1. Initialisation:
je dois vérifie que $P(0)$ est vraie.
2.pour la deuxième étape:
je suppose que / $P(n)$ est vraie au rang $n+1$ avec $n\geq 1$ et je démontre que $P(n+2)$ est vraie pour conclure que $P(n)$ est vraie pour tout $n \in \mathbb{N}$.
ici se pose le problème suivant:
puisque $P(n+1)$ est vraie alors $u_{n+1}$ est un entier naturel mais je ne peux pas dire que $u_n$ est un entier naturel.( car j'ai uniquement supposé que la propriété est vraie au rang $n+1$).
donc le premier principe est insuffisant pour conclure que $u_n$ est un entier naturel pour tout $n \in \mathbb{N}$..?
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar rebouxo » Mercredi 15 Avril 2015, 18:03

Que veux-tu démontrer ? Il n'y a rien à démontrer ici, c'est une définition d'une suite récurrente.
D'ailleurs depuis le début, je me demande ce que tu cherches.

Olivier
A line is a point that went for a walk. Paul Klee
Par solidarité, pas de MP
rebouxo
Modérateur
 
Messages: 6906
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar adem19s » Jeudi 16 Avril 2015, 05:59

rebouxo a écrit:Que veux-tu démontrer ? Il n'y a rien à démontrer ici, c'est une définition d'une suite récurrente.
D'ailleurs depuis le début, je me demande ce que tu cherches.

Olivier

ce que je cherchais est le suivant:
lorsque j'utilise le premier principe de récurrence pour démontrer qu'une propriété $P$ est vraie pour tout $n\geq$...
la deuxième étape de ce principe:
si je suppose que $P(n)$ est vraie au rang $n$ pour $n$ fixé et $n\geq n_0$ cela ne ne veut pas dire que les propriétés de rang $n-1$ , $n-2$..etc sont vraies.
j'éspère que je suis clair.
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar balf » Jeudi 16 Avril 2015, 08:44

Je ne vois pas où est le problème. Il y a un principe de récurrence *forte* et un principe de récurrence *faible*, certes, mais ces deux principes sont équivalents au fait que l'ordre sur N est un bon ordre, et sont donc équivalents entre eux.

J'ajouterai que dasn le cas de la suite de Fibonacci, il s'agit plus précisément d'une récurrence d'ordre 2, qui n'est qu'une récurrence simple appliquée à l'énoncé

$$\forall n [\mathcal P(n)\wedge\mathcal P(n+1)]\Rightarrow\mathcal P(n+2)$$



B.A.
balf
Zetta-utilisateur
 
Messages: 3804
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Principe de récurrence

Messagepar adem19s » Jeudi 16 Avril 2015, 10:33

Ma question est :supposons qu'on veut démontrer pa récurrence faible une propriété.
lorsque je suppose que $P$ est vraie au rang $n$,
est ce que $P(n-1)$ est vraie?
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar balf » Jeudi 16 Avril 2015, 22:55

Non, ça ne fait pas partie de l'hypothèse de récurrence. Comme je l'ai fait observer, pour une récurrence d'ordre 2, on effectue une récurrence faible sur un autre énoncé (voisin…)

B.A.
balf
Zetta-utilisateur
 
Messages: 3804
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Principe de récurrence

Messagepar adem19s » Vendredi 17 Avril 2015, 06:51

Exemple:
On considère la suite $(u_n)_{n\in\mathbb{N}}$ définie par:
$u_0=3$ et $u_1=5$
$u_{n+1}=3u_n-2u_{n-1}$
Question:Démontrer par récurrence que pour tout entier naturel $n$ ; $u_n=2^{n+1}+1$.
dans cet exemple ,on ne peut pas utiliser la récurrence faible car le calcul d'un terme de cette suite dépendra de deux termes.
par exemple $u_{10}=3u_9-2u_8$...etc.
donc on doit utiliser la récurrence forte pour répondre à la question...c'est bien ça?
Dernière édition par adem19s le Samedi 18 Avril 2015, 16:46, édité 2 fois.
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar balf » Vendredi 17 Avril 2015, 15:17

Si. La récurrence se fait sur l'énoncé:

$$(u_n=2^{n+1}+1)\wedge(u_{n-1}=2^{n}+1)\Rightarrow u_{n+1}=2^{n+1}+1$$


avec pour initialisation $(u_1=5)\wedge(u_0=3)$.

Enfin, c'est la justification que la récurrence simple entraîne la récurrence d'ordre $2$. On n' a pas véritablement besoin de la récurrence forte ici.

B.A.
balf
Zetta-utilisateur
 
Messages: 3804
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Principe de récurrence

Messagepar adem19s » Vendredi 17 Avril 2015, 21:53

Si j'ai bien compris,je dois réorganiser l'énoncé comme suit:
$P(n)$ : $u_n=2^{n+1}+1$ et $u_{n-1}=2^n+1$ et je démontre que la propriété $P(n)$ est vraie pour tout $n\geq1$.
1.L'initialisation se fait pour n=1.
1. L'hérédité:
je suppose que $P$ est vraie au rang $n$($n$ fixé et$ n\geq1$)
et je démontre que $P(n+1)$ est vraie...
ou j'utilise carrément le second principe de récurrence.voir fichier jointe.
Fichiers joints
principederecurrence.jpg
Principe de récurrence.
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar balf » Vendredi 17 Avril 2015, 22:46

Oui. De toute façon, ils sont logiquement équivalents (et en dernier ressort, c'est le fait que tout ensemble non vide de N possède un plus petit élément).

B.A.
balf
Zetta-utilisateur
 
Messages: 3804
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Principe de récurrence

Messagepar adem19s » Samedi 18 Avril 2015, 17:10

Je reprends l'exemple suivant:
On considère la suite $(u_n)_{n\in\mathbb{N}}$ définie par:
$u_0=3$ et $u_1=5$
$u_{n+1}=3u_n-2u_{n-1}$
Question:Démontrer par récurrence que pour tout entier naturel $n$ ; $u_n=2^{n+1}+1$.

1.Initialisation:
$u_0=2^{0+1}+1=3$ et comme dans l'énoncé on :$u_0=3$ ceci donne que $P(0)$ est vraie.
2.Hérédité:
je supose que $P$ est vraie au rang $n+1$ et je démontre que $P$ est vraie au rang suivant c'est à dire $n+2$.
je vais montrer que :$u_{n+2}=2^{n+2}+1$.
d'aprés l'énoncé on : $u_{n+2}=3u_{n+1}-2u_n=3\times(2^{n+2}+1)-2\times( 2^{n+1}+1)$
ce qui donne aprés simplification :
$u_{n+1}=2^{n+2}+1$
d'après le premier principe de récurrence la propriété $P(n)$ est vraie pour tout entier naturel $n$.
Remarque:
Si on répondrais à la question posée de cette manière, alors on peut dire tout simplement que la réponse est fausse?
adem19s
Kilo-utilisateur
 
Messages: 155
Inscription: Mercredi 22 Mai 2013, 18:59
Statut actuel: Actif et salarié | Enseignant

Re: Principe de récurrence

Messagepar balf » Samedi 18 Avril 2015, 18:20

D'abord il faut supposer la propriété vraie au rang $n$ puisque son libellé fait intervenir $u_n$/ Ensuite, il sera nécessaire de savoir aussi la propriété vraie au rang $n-1$ (récurrence d'ordre $2$ parce que la suite est définie par une récurrence d'ordre $2$.

Du coup, il faut aussi initialiser à $n=1$.

B.A.
balf
Zetta-utilisateur
 
Messages: 3804
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Suivante

Retourner vers Exercices et problèmes : Lycée

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Exabot [Bot] et 4 invités