Principe de récurrence

Aide à la résolution d'exercices de mathématiques de tout niveau scolaire.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Principe de récurrence

Message non lu par adem19s »

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.
evariste_G
Utilisateur chevronné
Utilisateur chevronné
Messages : 1481
Inscription : vendredi 19 décembre 2008, 19:13
Statut actuel : Enseignant
Localisation : Bordeaux
Contact :

Re: Principe de récurrence

Message non lu par evariste_G »

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 : https://www.mathweb.fr
Cours particuliers de maths par webcam: https://courspasquet.fr
Trouver un vrai prof pour des cours particuliers: https://lesvraisprofs.mathweb.fr/
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Principe de récurrence

Message non lu par balf »

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

B.A.
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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}$.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Principe de récurrence

Message non lu par balf »

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 modification par balf le mercredi 15 avril 2015, 22:38, modifié 1 fois.
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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?
Clog

Re: Principe de récurrence

Message non lu par Clog »

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...
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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}$..?
rebouxo
Modérateur honoraire
Modérateur honoraire
Messages : 6962
Inscription : mercredi 15 février 2006, 13:18
Localisation : le havre
Contact :

Re: Principe de récurrence

Message non lu par rebouxo »

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.
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Principe de récurrence

Message non lu par balf »

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.
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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?
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Principe de récurrence

Message non lu par balf »

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.
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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 modification par adem19s le samedi 18 avril 2015, 17:46, modifié 2 fois.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Principe de récurrence

Message non lu par balf »

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.
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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.
Pièces jointes
Principe de récurrence.
Principe de récurrence.
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Principe de récurrence

Message non lu par balf »

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.
adem19s
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 163
Inscription : mercredi 22 mai 2013, 19:59

Re: Principe de récurrence

Message non lu par adem19s »

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?
balf
Modérateur spécialisé
Modérateur spécialisé
Messages : 4065
Inscription : mercredi 02 janvier 2008, 23:18

Re: Principe de récurrence

Message non lu par balf »

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.
Répondre