[TS+] Lostounet en MPSI

[Lostounet]

Bonjour à tous!

J'ai commencé à faire quelques exercices de mathématiques (en lisant les œuvres au programme!).
Je travaille les exercices proposés par Louis le Grand à ses élèves: ici

J'ai quelques difficultés à résoudre l'exercice suivant:

La suite est définie par et:



a) Montrer que:


b) Trouver C > 0 tel que:






a) Faut-il nécessairement passer par une "récurrence forte" ? Je ne saisis pas vraiment la différence entre les deux récurrences (simple et forte) dans cet exemple. Je ne comprends donc pas à quoi se réfèrent n et N.
Voici une solution d'un ami matheux (que j'ai bien compris, à ces deux détails près):

Initialisation:
Pour n = 0 (on vérifie, c'est vrai)

Hérédité:

Supposons que pour un certain rang N, .
Montrons alors que

Nous avons:




Or

Et de même



Par hypothèse de récurrence:



Alors:


Comme est un entier, on a donc

Voilà, merci de m'aider à saisir les quelques subtilités. Je passerai ensuite à la deuxième question !

[Sourire_banane]

Salut,

Pour une récurrence forte, faut supposer que la propriété est vraie pour tout rang depuis le rang de départ jusqu'à un certain rang n supérieur au rang de départ.

[Lostounet]

Salut !

Dans quels cas faut-il tenter une récurrence forte ? On ne peut pas pas faire une récurrence simple ici?

[busard_des_roseaux]

bonsoir,
quand est fonction de on peut faire une récurrence faible (habituelle)

quand est fonction de on fait une récurrence forte

[busard_des_roseaux]

exemple de récurrence forte
"tout entier naturel inférieur ou égal à n admet une factorisation en facteurs premiers"

supposons
si n+1 est premier, c'est fini, sinon
n+1 s'écrit

avec premier et et on applique l'hypothèse de récurrence (forte) à .

[Lostounet]

Salut,

Merci pour votre réponse.
Je connais la démonstration évoquée :)

Par contre, je ne comprends pas pourquoi on ne peut pas travailler avec une récurrence normale. Il n'y a pas "plusieurs rangs" impliqués dans la relation de récurrence

[busard_des_roseaux]

par exemple, pour l'entier qui "apparait"" dans la factorisation de , n'est pas nécessairement (le prédécesseur de ) et il faut pouvoir appliquer l'hypothèse de récurrence à tous les entiers de
l'intervalle entier

[Lostounet]

Oui ! Je suis d'accord !

Mais pour notre exercice? Il faut que tous les termes de la suite soient > n + 1 ?
On ne peut pas commencer par un seul ?

[busard_des_roseaux]

Avec l'égalité

si l'on souhaite démontrer une propriété pour ,
on utilise les indices

qui sont situés environ à la moitié, au tiers et au sixième de [1;n]
Pour cette raison, la récurrence est forte.

[Lostounet]

Je vois mieux!
Merci beaucoup.

Et on peut sans problème supposer que la propriété est vraie sur plusieurs rangs? Cela ne pose aucun problème de logique?

[LeJeu]

Je vois mieux!
Merci beaucoup.

Et on peut sans problème supposer que la propriété est vraie sur plusieurs rangs? Cela ne pose aucun problème de logique?

Bonsoir,

@ busard_des_roseaux

Je rejoins le questionnement de Lostounet , il y a t'il une différence entre récurrence forte ou faible ?

Je dois me tromper, mais n'est ce pas exactement la même chose ? à quel moment la démarche est elle différente ?

[busard_des_roseaux]

soit une propriété logique (sa valeur de vérité V ou F dépend de l'entier )

l'hypothèse de récurrence faible est:


l'hypothèse de récurrence forte au rang est: est vérifiée

[LeJeu]

soit une propriété logique (sa valeur de vérité V ou F dépend de l'entier )

l'hypothèse de récurrence faible est:

l'hypothèse de récurrence forte au rang est: est vérifiée

merci, Je comprends bien ,

mais les deux énoncés ne sont ils pas équivalents ?
Ou dit plus 'simplement' , ca change quoi ?, à quel moment dans la démo ca va intervenir ?

n'ai je pas le droit de toujours considérer que ma récurrence est forte ?

[busard_des_roseaux]

l'implication est un connecteur entre les propositions A et B .
Dans l'hérédité simple, on connecte avec
dans l'hérédité forte , on connecte

( et et ..et ) avec

et ensuite , on utilise et

[Lostounet]

On est bien d'accord, mais n'a-t-on pas le droit de toujours supposer la récurrence forte? Même lorsqu'on veut connecter H_n avec H_n+1, comme H_n-1 et H_n sont connectés, finalement... c'est une récurrence forte en ce sens..?

[busard_des_roseaux]

oui, excuse moi, je n'avais pas compris ta question... :mur:
effectivement , on peut toujours écrire une récurrence forte mais la rédaction est considérée comme "lourde" si une récurrence simple suffit. Par contre, dans certains cas, une récurrence simple ne permet pas de conclure

[LeJeu]

l'implication est un connecteur entre les propositions A et B .
Dans l'hérédité simple, on connecte avec
dans l'hérédité forte , on connecte

( et et ..et ) avec

et ensuite , on utilise et

Ok je te suis toujours ....

mais non ... il y a t'il un démo qui a besoin de se revendiquer d'une hérédité simple ou forte?

je ne vois pas, pardon...

[Lostounet]

D'accord ! Je comprends.

Mais j'ai un autre problème ... Je ne comprends pas le principe de la récurrence forte :p

Pour la récurrence simple, on vérifie qu'au premier rang la propriété est vraie. Ensuite, on la suppose vraie pour un certain n, et on montre que cela implique que c'est vrai au rang n + 1...

Mais pour la récurrence forte, comment peut-on la supposer vraie à tous les rangs jusqu'à n... C'est un peu contre-intuitif, par rapport à la récurrence simple. C'est un peu une "grosse supposition" ... Je ne sais pas si je me fais comprendre :p

[busard_des_roseaux]

dans l'exercice de Lostounet, la récurrence est forte car


donc si on veut démontrer une formule pour , il faut aller chercher une propriété vérifiée par , et et non pas une propriété vérifiée par

[Sylviel]

Comme l'a déjà fait remarquer Busard une récurrence forte c'est une récurrence simple sur une plus grosse propriété.

Imaginons que l'on veut montrer la propriété Hn pour tout n.

Maintenant imaginons que pour montrer Hn+1 on ai besoin de Hn et Hn-1 par exemple. Dans ce cas on peut introduire
Pn = {Hk est vraie pour tout k \leq n}

Si H0 est vraie alors P0 est vraie.
Si de plus H1 est vraie alors P1 est vraie.
Supposons que Pn soit vraie, alors en pariticulier Hn et Hn-1 sont vraie donc Hn+1 est vraie.
Donc Pn+1 est vraie.

Donc par récurrence Pn est vraie pour tout n, ce qui est bien équivalent à Hn est vraie pour tout n.


Bref parler de récurrence forte permet juste d'éviter d'introduire une propriété de type Pn plus longue à écrire.