bonjour c'est encore moi!
une petite question sur le principe de récurrence :
on définit l'axiome de récurrence en démontrant que si une propriété Pest
vrai pour le rang 0, et on suppose que P est vrai pour n. si on démontre que
P est vrai pour n+1, alors P est vrai pour tout n.
mais est-ce que l'on peut faire la même chose en prenant la propriéte P
fausse?
je m'explique :
prenons une propriété P supposé fausse pour n. on démontre que P est fausse
pour n+1 et pour n=0, P est fausse. donc P est fausse pour tout n ?
sur un exo, je dois montrer que u(n)=alpha(n), je démontre facilement que
u(n+1)>=alpha(n+1). comme u(1)<alpha(1), donc P fausse pour n=1, je dis que
P est fausse pour tout n donc que u(n)<alpha(n) pour tout n.
je pense que ce n'est pas totalement juste.
avez-vous une réponse?
merci
Lolo
Récurrence
11 messages
- Page 1 sur 1
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
> une petite question sur le principe de récurrence :
> on définit l'axiome de récurrence en démontrant que si une propriété Pest
> vrai pour le rang 0, et on suppose que P est vrai pour n. si on démontre
> que P est vrai pour n+1, alors P est vrai pour tout n.
> mais est-ce que l'on peut faire la même chose en prenant la propriéte P
> fausse?
Oui, bien sûr : c'est une récurrence sur Q = non P.
si Q est vraie pour n=0 et "Q vraie pour n ==> Q vraie pour n+1"
Alos Q est vraie pour tout n.
> je m'explique :
> prenons une propriété P supposé fausse pour n. on démontre que P est
> fausse pour n+1 et pour n=0, P est fausse. donc P est fausse pour tout n ?
Oui
> sur un exo, je dois montrer que u(n) en prenant la propriété u(n)>=alpha(n), je démontre facilement que
> u(n+1)>=alpha(n+1). comme u(1) que P est fausse pour tout n donc que u(n) je pense que ce n'est pas totalement juste.
Non.
Si tu prends comme propriété P que tu veux démontrer fausse pour tout n :
"u(n)>=alpha(n)"
Alors il faut démontrer :
P faux pour n = 1 : "u(1)>=alpha(1)" faux. OK
Si P faux pour n, alors P faux pour n+1 , soit
"u(n)>=alpha(n)" faux implique "u(n+1)>=alpha(n+1)" faux
Ce qui n'est pas ce que tu démontres, puisque tu fais :
"u(n)>=alpha(n)" vrai implique "u(n+1)>=alpha(n+1)" vrai
Si tu as un doute, écris clairement la définition de ta propriété P puis
écris le raisonnement à faire en fonction de P et remplace alors P par sa
définition.
Cordialement
Patrick
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
"GuizLolo" a écrit dans le message de news:
41c68eb7$0$21080$626a14ce@news.free.fr...
> prenons une propriété P supposé fausse pour n. on démontre que P est
> fausse
Oui, si l'on veut
on démontre par récurrence :
la propriété Qn est vraie, avec Qn :" la propriété Pn est fausse"
Voilà
41c68eb7$0$21080$626a14ce@news.free.fr...
> prenons une propriété P supposé fausse pour n. on démontre que P est
> fausse
Oui, si l'on veut
on démontre par récurrence :
la propriété Qn est vraie, avec Qn :" la propriété Pn est fausse"
Voilà
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
On Mon, 20 Dec 2004 09:35:17 +0100, GuizLolo wrote:
> prenons une propriété P supposé fausse pour n. on démontre que P est fausse
> pour n+1 et pour n=0, P est fausse. donc P est fausse pour tout n ?
Oui, reformulons.
Soit l'assertion, H(n) : " La propriété P(n) est fausse. "
Si on démontre que H(n) est vraie pour tout naturel n, on
aura alors montré que P(n) est fausse pour tout naturel n,
es-tu d'accord ?
[color=blue]
> sur un exo, je dois montrer que u(n) en prenant la propriété u(n)>=alpha(n), je démontre facilement que
> u(n+1)>=alpha(n+1). comme u(1) P est fausse pour tout n donc que u(n) P(n+1) fausse.
Tu ne peux donc pas conclure si facilement.
Par exemple, a priori tu ne peux rien présager du comportement
de u(2) et a(2)
Contre-exemple :
Je choisis u(n) telle que u croisse très vite par rapport à a.
u(n) = 2^n
a(n) = 2n+2
u(1) = 2
a(1) = 4 donc u(1) = a(n), ie 2^n >= 2n+2
=> 2^(n+1) >= 2(2n+2) >= 2(n+1)+2
donc u(n+1) >= a(n+1)
J'ai donc vérifié toutes tes hypothèses.
Mais pour autant on n'a pas qqs n, 2^n = a(n) pour n>=3,
on s'en convaint assez facilement avec un graphique)
--
Michel [overdose@alussinan.org]
> prenons une propriété P supposé fausse pour n. on démontre que P est fausse
> pour n+1 et pour n=0, P est fausse. donc P est fausse pour tout n ?
Oui, reformulons.
Soit l'assertion, H(n) : " La propriété P(n) est fausse. "
Si on démontre que H(n) est vraie pour tout naturel n, on
aura alors montré que P(n) est fausse pour tout naturel n,
es-tu d'accord ?
[color=blue]
> sur un exo, je dois montrer que u(n) en prenant la propriété u(n)>=alpha(n), je démontre facilement que
> u(n+1)>=alpha(n+1). comme u(1) P est fausse pour tout n donc que u(n) P(n+1) fausse.
Tu ne peux donc pas conclure si facilement.
Par exemple, a priori tu ne peux rien présager du comportement
de u(2) et a(2)
Contre-exemple :
Je choisis u(n) telle que u croisse très vite par rapport à a.
u(n) = 2^n
a(n) = 2n+2
u(1) = 2
a(1) = 4 donc u(1) = a(n), ie 2^n >= 2n+2
=> 2^(n+1) >= 2(2n+2) >= 2(n+1)+2
donc u(n+1) >= a(n+1)
J'ai donc vérifié toutes tes hypothèses.
Mais pour autant on n'a pas qqs n, 2^n = a(n) pour n>=3,
on s'en convaint assez facilement avec un graphique)
--
Michel [overdose@alussinan.org]
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
On Mon, 20 Dec 2004 10:16:45 +0100, Patrick Coilland wrote:
> Ce qui n'est pas ce que tu démontres, puisque tu fais :
> "u(n)>=alpha(n)" vrai implique "u(n+1)>=alpha(n+1)" vrai
La confusion provient sûrement du cas d'école
(P => Q) => (non P => non Q)
qui n'est pas vrai dans le cas général.
--
Michel [overdose@alussinan.org]
> Ce qui n'est pas ce que tu démontres, puisque tu fais :
> "u(n)>=alpha(n)" vrai implique "u(n+1)>=alpha(n+1)" vrai
La confusion provient sûrement du cas d'école
(P => Q) => (non P => non Q)
qui n'est pas vrai dans le cas général.
--
Michel [overdose@alussinan.org]
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
c'est bien ce que je pensais, ça m'a travaillé toute la nuit.
dans ce cas , je vais exposer mon pb, il est simple :
soit la suite u(n)=sqrt(n+sqrt((n-1)+....+sqrt(2+sqrt(1)))) pour n>0
la relation de récurrence s'écrit alors : u(n+1)=sqrt((n+1)+u(n))
ensuite je dois montrer que u(n) est croissante
je pose donc
u(n+1)-u(n)=sqrt((n+1)+u(n))-u(n)=(n+1+u(n)-u²(n))/(sqrt((n+1)+u(n))+u(n))
il est clair que un>0 pour n>0
donc u(n+1)-u(n) est du signe de -u²(n)+u(n)+n+1
soit la fonction f définie par f(x)=-x²+x+n+1 pour x>0
f(x) est positive entre les 2 racines de f(x)=0
on a une racine positive et une négative
appelons alpha(n) la racine positive : alpha(n)=(1+sqrt(4*n+5))/2
pour montrer que u(n) est croissante, il faut donc que u(n)=alpha(n)), je trouve que u(n)>=alpha(n) et que
u(n+1)>=alpha(n+1)
et comme P est faux pour n=1, j'en aurais déduit que u(n)>=alpha(n) est faux
pour tout n donc que u(n)<alpha(n) pour tout n !
une piste?
merci
Lolo
dans ce cas , je vais exposer mon pb, il est simple :
soit la suite u(n)=sqrt(n+sqrt((n-1)+....+sqrt(2+sqrt(1)))) pour n>0
la relation de récurrence s'écrit alors : u(n+1)=sqrt((n+1)+u(n))
ensuite je dois montrer que u(n) est croissante
je pose donc
u(n+1)-u(n)=sqrt((n+1)+u(n))-u(n)=(n+1+u(n)-u²(n))/(sqrt((n+1)+u(n))+u(n))
il est clair que un>0 pour n>0
donc u(n+1)-u(n) est du signe de -u²(n)+u(n)+n+1
soit la fonction f définie par f(x)=-x²+x+n+1 pour x>0
f(x) est positive entre les 2 racines de f(x)=0
on a une racine positive et une négative
appelons alpha(n) la racine positive : alpha(n)=(1+sqrt(4*n+5))/2
pour montrer que u(n) est croissante, il faut donc que u(n)=alpha(n)), je trouve que u(n)>=alpha(n) et que
u(n+1)>=alpha(n+1)
et comme P est faux pour n=1, j'en aurais déduit que u(n)>=alpha(n) est faux
pour tout n donc que u(n)<alpha(n) pour tout n !
une piste?
merci
Lolo
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
On Mon, 20 Dec 2004 11:11:38 +0100, GuizLolo wrote:
> c'est bien ce que je pensais, ça m'a travaillé toute la nuit.
> dans ce cas , je vais exposer mon pb, il est simple :
> soit la suite u(n)=sqrt(n+sqrt((n-1)+....+sqrt(2+sqrt(1)))) pour n>0
> la relation de récurrence s'écrit alors : u(n+1)=sqrt((n+1)+u(n))
> ensuite je dois montrer que u(n) est croissante
Je propose de le faire par récurrence.
Ta méthode est inadéquate ici, la technique de la différence quand tu
as des racines carrées à manipuler est très désagréable.
Surtout quand comme ici, la croissance est si grossière (très rapide).
On a :
u(0) = sqrt(1) u(n)
alors (n+1) + u(n+1) > u(n) + (n+1)
alors comme (n+2) > (n+1),
(n+2) + u(n+1) > u(n) + (n+1)
puis en passant à la racine carrée (tout ceci étant facilement positif)
u(n+2) > u(n+1)
donc qqs n u(n+1) > u(n) ; autrement dit u est strictement croissante.
> appelons alpha(n) la racine positive : alpha(n)=(1+sqrt(4*n+5))/2
> pour montrer que u(n) est croissante, il faut donc que u(n) supposons P vrai pour n donc u(n) pour n+1:
> u(n+1)=sqrt((n+1)+u(n)) en èlevant au carré et en simplifiant , je trouve u(n) or alpha(n)<alpha(n+1) donc je ne peux pas conclure que u(n)<alpha(n) !
Attention, que cherches-tu à montrer ?
Au passage ton raisonnement fonctionne, bien qu'il soit un peu compliqué,
mais il faut bien raisonner.
--
Michel [overdose@alussinan.org]
> c'est bien ce que je pensais, ça m'a travaillé toute la nuit.
> dans ce cas , je vais exposer mon pb, il est simple :
> soit la suite u(n)=sqrt(n+sqrt((n-1)+....+sqrt(2+sqrt(1)))) pour n>0
> la relation de récurrence s'écrit alors : u(n+1)=sqrt((n+1)+u(n))
> ensuite je dois montrer que u(n) est croissante
Je propose de le faire par récurrence.
Ta méthode est inadéquate ici, la technique de la différence quand tu
as des racines carrées à manipuler est très désagréable.
Surtout quand comme ici, la croissance est si grossière (très rapide).
On a :
u(0) = sqrt(1) u(n)
alors (n+1) + u(n+1) > u(n) + (n+1)
alors comme (n+2) > (n+1),
(n+2) + u(n+1) > u(n) + (n+1)
puis en passant à la racine carrée (tout ceci étant facilement positif)
u(n+2) > u(n+1)
donc qqs n u(n+1) > u(n) ; autrement dit u est strictement croissante.
> appelons alpha(n) la racine positive : alpha(n)=(1+sqrt(4*n+5))/2
> pour montrer que u(n) est croissante, il faut donc que u(n) supposons P vrai pour n donc u(n) pour n+1:
> u(n+1)=sqrt((n+1)+u(n)) en èlevant au carré et en simplifiant , je trouve u(n) or alpha(n)<alpha(n+1) donc je ne peux pas conclure que u(n)<alpha(n) !
Attention, que cherches-tu à montrer ?
Au passage ton raisonnement fonctionne, bien qu'il soit un peu compliqué,
mais il faut bien raisonner.
--
Michel [overdose@alussinan.org]
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
Le 20/12/2004 10:28, Michel a écrit :
>
> La confusion provient sûrement du cas d'école
> (P => Q) => (non P => non Q)
Tu voulais peut-être écrire :
(P => Q) (non Q => non P) ?
En effet, ce que tu as écrit est faux lorsque P est faux et Q est vrai.
--
Olivier Miakinen
Non, monsieur le juge, je vous le jure : jamais je n'ai cité
Bruxelles dans ma signature.
>
> La confusion provient sûrement du cas d'école
> (P => Q) => (non P => non Q)
Tu voulais peut-être écrire :
(P => Q) (non Q => non P) ?
En effet, ce que tu as écrit est faux lorsque P est faux et Q est vrai.
--
Olivier Miakinen
Non, monsieur le juge, je vous le jure : jamais je n'ai cité
Bruxelles dans ma signature.
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
"Michel" a écrit dans le message de news:
pan.2004.12.20.10.32.56.605000@alussinan.org...
> On Mon, 20 Dec 2004 11:11:38 +0100, GuizLolo wrote:
>[color=green]
>> c'est bien ce que je pensais, ça m'a travaillé toute la nuit.
>> dans ce cas , je vais exposer mon pb, il est simple :
>> soit la suite u(n)=sqrt(n+sqrt((n-1)+....+sqrt(2+sqrt(1)))) pour n>0
>> la relation de récurrence s'écrit alors : u(n+1)=sqrt((n+1)+u(n))
>> ensuite je dois montrer que u(n) est croissante
>
> Je propose de le faire par récurrence.
> Ta méthode est inadéquate ici, la technique de la différence quand tu
> as des racines carrées à manipuler est très désagréable.
> Surtout quand comme ici, la croissance est si grossière (très rapide).
>
> On a :
> u(0) = sqrt(1) Supposons u(n+1) > u(n)
> alors (n+1) + u(n+1) > u(n) + (n+1)
> alors comme (n+2) > (n+1),
> (n+2) + u(n+1) > u(n) + (n+1)
> puis en passant à la racine carrée (tout ceci étant facilement positif)
> u(n+2) > u(n+1)
>
> donc qqs n u(n+1) > u(n) ; autrement dit u est strictement croissante.
>
>> appelons alpha(n) la racine positive : alpha(n)=(1+sqrt(4*n+5))/2
>> pour montrer que u(n) est croissante, il faut donc que u(n)
> Oui.
>[color=green]
>> supposons P vrai pour n donc u(n)> pour n+1:
>> u(n+1)=sqrt((n+1)+u(n))
> Non.
>[color=green]
>> en èlevant au carré et en simplifiant , je trouve u(n)> or alpha(n)
> Attention, que cherches-tu à montrer ?
>
> Au passage ton raisonnement fonctionne, bien qu'il soit un peu compliqué,
> mais il faut bien raisonner.
>
> --
> Michel [overdose@alussinan.org]
merci bcp monsieur michel
en effet, les méthodes les plus simples sont souvent les meilleurs!!
cordialement
Lolo
pan.2004.12.20.10.32.56.605000@alussinan.org...
> On Mon, 20 Dec 2004 11:11:38 +0100, GuizLolo wrote:
>[color=green]
>> c'est bien ce que je pensais, ça m'a travaillé toute la nuit.
>> dans ce cas , je vais exposer mon pb, il est simple :
>> soit la suite u(n)=sqrt(n+sqrt((n-1)+....+sqrt(2+sqrt(1)))) pour n>0
>> la relation de récurrence s'écrit alors : u(n+1)=sqrt((n+1)+u(n))
>> ensuite je dois montrer que u(n) est croissante
>
> Je propose de le faire par récurrence.
> Ta méthode est inadéquate ici, la technique de la différence quand tu
> as des racines carrées à manipuler est très désagréable.
> Surtout quand comme ici, la croissance est si grossière (très rapide).
>
> On a :
> u(0) = sqrt(1) Supposons u(n+1) > u(n)
> alors (n+1) + u(n+1) > u(n) + (n+1)
> alors comme (n+2) > (n+1),
> (n+2) + u(n+1) > u(n) + (n+1)
> puis en passant à la racine carrée (tout ceci étant facilement positif)
> u(n+2) > u(n+1)
>
> donc qqs n u(n+1) > u(n) ; autrement dit u est strictement croissante.
>
>> appelons alpha(n) la racine positive : alpha(n)=(1+sqrt(4*n+5))/2
>> pour montrer que u(n) est croissante, il faut donc que u(n)
> Oui.
>[color=green]
>> supposons P vrai pour n donc u(n)> pour n+1:
>> u(n+1)=sqrt((n+1)+u(n))
> Non.
>[color=green]
>> en èlevant au carré et en simplifiant , je trouve u(n)> or alpha(n)
> Attention, que cherches-tu à montrer ?
>
> Au passage ton raisonnement fonctionne, bien qu'il soit un peu compliqué,
> mais il faut bien raisonner.
>
> --
> Michel [overdose@alussinan.org]
merci bcp monsieur michel
en effet, les méthodes les plus simples sont souvent les meilleurs!!
cordialement
Lolo
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
On Mon, 20 Dec 2004 11:37:14 +0100, Olivier Miakinen wrote:
[color=green]
>> La confusion provient sûrement du cas d'école
>> (P => Q) => (non P => non Q)[/color]
Il manque un bout de ma citation, là.
je n'ai pas prétendu que c'était vrai.
Je me suis peut-être mal exprimé.
Ayant montré P(n) vrai => P(n+1) vrai, GuizLolo aurait nié un peu vite
la proposition en disant P(n) faux => P(n+1) faux, sans se soucier du
signe =>.
Ce qui n'est évidemment pas licite, mais qui peut rappeler le passage à
la négation dans les équivalences (correct cette fois)
(P Q) (nonP nonQ)
Ca découle en fait de la propriété (correcte) que tu as gentillement
rappelé.
> (P => Q) (non Q => non P) ?
--
Michel [overdose@alussinan.org]
[color=green]
>> La confusion provient sûrement du cas d'école
>> (P => Q) => (non P => non Q)[/color]
Il manque un bout de ma citation, là.
je n'ai pas prétendu que c'était vrai.
Je me suis peut-être mal exprimé.
Ayant montré P(n) vrai => P(n+1) vrai, GuizLolo aurait nié un peu vite
la proposition en disant P(n) faux => P(n+1) faux, sans se soucier du
signe =>.
Ce qui n'est évidemment pas licite, mais qui peut rappeler le passage à
la négation dans les équivalences (correct cette fois)
(P Q) (nonP nonQ)
Ca découle en fait de la propriété (correcte) que tu as gentillement
rappelé.
> (P => Q) (non Q => non P) ?
--
Michel [overdose@alussinan.org]
Re: Récurrence
par Anonyme » 30 Avr 2005, 18:05
GuizLolo a écrit :
> "Michel" a écrit dans le message de news:
> pan.2004.12.20.10.32.56.605000@alussinan.org...[color=green]
>>
>> Je propose de le faire par récurrence.
>> Ta méthode est inadéquate ici, la technique de la différence quand tu
>> as des racines carrées à manipuler est très désagréable.
>> Surtout quand comme ici, la croissance est si grossière (très rapide).
>>
>> On a :
>> u(0) = sqrt(1) > Supposons u(n+1) > u(n)
>> alors (n+1) + u(n+1) > u(n) + (n+1)
>> alors comme (n+2) > (n+1),
>> (n+2) + u(n+1) > u(n) + (n+1)
>> puis en passant à la racine carrée (tout ceci étant facilement positif)
>> u(n+2) > u(n+1)
>>
>> donc qqs n u(n+1) > u(n) ; autrement dit u est strictement croissante.
>>
>
> merci bcp monsieur michel
> en effet, les méthodes les plus simples sont souvent les meilleurs!!
> cordialement
> Lolo[/color]
et meme encore plus simple :
u(n) > sqrt(n)
--
philippe
(chephip at free dot fr)
> "Michel" a écrit dans le message de news:
> pan.2004.12.20.10.32.56.605000@alussinan.org...[color=green]
>>
>> Je propose de le faire par récurrence.
>> Ta méthode est inadéquate ici, la technique de la différence quand tu
>> as des racines carrées à manipuler est très désagréable.
>> Surtout quand comme ici, la croissance est si grossière (très rapide).
>>
>> On a :
>> u(0) = sqrt(1) > Supposons u(n+1) > u(n)
>> alors (n+1) + u(n+1) > u(n) + (n+1)
>> alors comme (n+2) > (n+1),
>> (n+2) + u(n+1) > u(n) + (n+1)
>> puis en passant à la racine carrée (tout ceci étant facilement positif)
>> u(n+2) > u(n+1)
>>
>> donc qqs n u(n+1) > u(n) ; autrement dit u est strictement croissante.
>>
>
> merci bcp monsieur michel
> en effet, les méthodes les plus simples sont souvent les meilleurs!!
> cordialement
> Lolo[/color]
et meme encore plus simple :
u(n) > sqrt(n)
--
philippe
(chephip at free dot fr)
11 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :