Récurrence

par **Lulu_007** » 15 Sep 2007, 10:43

Bonjour !
Als voila je bloque sur une récurrence qui a tout de ce qu'il ya de plus simple j'ai l'impression ...
Soit f de N dans N une application vérifiant que pour tout n appartenant à N , f(n+1)> f(f(n))

Je dois montrer par récurrence sur l'entier p que pour tout n appartenant à l'ensemble des entiers allant de p à +00 , f(n) >= p (supérieur ou égal...)
Seulement je ne comprends pas ce que veut dire faire une récurrence sur "p" ... instinctivement moi je l'aurais faites sur n...

par **fahr451** » 15 Sep 2007, 10:54

bonjour
sur p donc

Hp : "pour tout n >= p ..."

H0 : " pour tout n >= 0 " à vérifier

etc

par **Lulu_007** » 15 Sep 2007, 11:05

D'accord !
Donc pour ho :
Si n >= 0 , on a bien f(n) >=0 comme f est une application de N dans N

Hp : si n >= p , f(n) >= p

Et maintenant le but est de montrer H(p+1) vrai si j'ai bien compris ?

par **fahr451** » 15 Sep 2007, 11:20

en effet

prendre un n > p+1

par **Lulu_007** » 15 Sep 2007, 12:01

mais j'ai un problème als...je n'arrive pas a utiliser l'hyposthèse de récurence...

par **fahr451** » 15 Sep 2007, 12:03

c'est assez rigolo

on prend donc n>= p+1

donc n-1 >= p

on a par hypothèse Hp f(n-1) >= p

et on réapplique l 'hypothèse Hp

f (f (n-1) ) >= p

or par hypothèse sur f

f (n) > f (f(n-1) ) >= p

et donc f(n) >= p+1

par **Lulu_007** » 15 Sep 2007, 12:22

Je vois...je n'avais pas vu que quand
n>= p+1
donc que n-1 >= p
on a par hypothèse f(n-1) >= p ...
Enfait c'est parce que ici le n-1 ce l'intervalle [p+1 ; +00 [ correspond au n de l'intervalle [p ; + 00 [ c'est ca ?

Cela dit je cne comprends pas comment tu réapplique l'hypothèse Hp ...

par **fahr451** » 15 Sep 2007, 12:24

n ' = f(n-1) est lui même un élément de [p,+infini [ donc on peut appliquer Hp pour cet élément n '

par **Lulu_007** » 15 Sep 2007, 12:37

D'accord j'ai compris !
mais pour reprendre ma quetion d'avant on peut dire que f(n-1) >= p parce que ici le n-1 ce l'intervalle [p+1 ; +00 [ correspond au n de l'intervalle [p ; + 00 [ c'est ca ?

et deuxième petite question on trouve même que si n>= p+1 on a f(n) > p si j'ai bien compris ?

par **fahr451** » 15 Sep 2007, 12:41

question 1 réponse : oui

les lettres sont muettes si tu veux tu écris

Hp : pour tout entier tructruc avec tructruc >= p on a ...

et ensuite ton entier n-1 est bien un tructruc >=p tout comme f(n-1) est un autre tructruc valable

question 2 réponse oui et comme les entiers vont de 1 en 1 ..
f(n) > p donne exactement f(n) >=p +1

par **Lulu_007** » 15 Sep 2007, 12:59

D'accord

Bon on me demande de montrer que f est strictement croissante sur N ...Je me suis fixé comme objectif de montrer que pour n +1 > n , f(n+1) > f(n)
Bon départ ?

par **fahr451** » 15 Sep 2007, 13:02

ça semble raisonnable modulo le fait que n+1 est toujours > à n ...

par **Lulu_007** » 15 Sep 2007, 13:06

OUi c'est vrai... :marteau:

Donc je veux montrer que f(n+1) > f(n), et pour ca je part de n+1 > n ?

par **fahr451** » 15 Sep 2007, 13:16

pose donc p = f(n)

que peux tu écrire en utilisant la question précédente ?

par **Lulu_007** » 15 Sep 2007, 13:24

Je crois avoir trouvé ...
Donc je pose f(n) = p
Donc comme f(n) >= p on a f(f(n)) >= p

D'ou f(n+1) > f(f(n)) >= f(n)
f(n+1) > f(n)

par **fahr451** » 15 Sep 2007, 13:26

en effet c'est ça

par **Lulu_007** » 15 Sep 2007, 13:46

merci !
Reste a prouver que f = Id N, je m'y met !
A ++

par **Lulu_007** » 15 Sep 2007, 14:02

J'ai juste une question encore
Comme f(n+1) > f(f(n)) et que f est strictment croissante (donc injective )
ai je le droit de dire que n+1 > f(n) ?

par **fahr451** » 15 Sep 2007, 14:04

à ton avis ?

par **Lulu_007** » 15 Sep 2007, 14:06

A mon avis oui ...mais j'ai dja fait tellment de conneire en ce début d'année de sup que je suis prudent ^^

Récurrence

Récurrence

Qui est en ligne