Bonsoir

J'ai du mal à comprendre la récurrence immédiate.

J'aimerais savoir si cela a un lien avec la récurrence forte ? Et est ce que vous pouvez m'aider à bien ancrer la récurrence immédiate dans ce cas ?

Merci

(Je suis sur une solution d'un exercice donc je pourrais donner un exemple mais je préférais le comprendre sans rien donner ici sinon j'aurais juste l'impression d'avoir bien compris mais en fait...ça ne le sera pas ! Or je n'ai pas trouvé de démonstration sur la récurrence immédiate sur le net.)

Salut.
edit ;  En fait, ce que tu entends pas récurrence immédiate est le concepts de récurrence simple vs forte.
L'idée principale d'une récurrence simple est que la propriété au rang k+1 ne dépends que le la propriété au rang k. 

Une récurrence forte se base sur l'ensemble des instants précédant l'instant k+1 pour montrer que la propriété reste vraie à l'instant k+1.

https://fr.wikipedia.org/wiki/Raisonnement_par_r%C3%A9currence Pour plus de détails

-
Edité par edouard22 4 mai 2018 à 23:28:31

Je ne comprend pas bien ta phrase :

edouard22 a écrit:

edit ;  En fait, ce que tu entends pas récurrence immédiate est le concepts de récurrence simple vs forte.

J'ai vu entre autres l'explication de wikipedia sur le recurrence forte c'est d'ailleurs ce qui m'a fait penser à une autre définition/nomination de la recurrence immédiate, d'où mon post

Donc selon toi peut on dire grosso modo?

récurrence faible : 0 à n=>n+1

récurrence forte : n+1=>n à 0

et récurrence faible <= récurrence forte

Mais cela ne m'explique pas bien la récurrence immédiate!

Bonjour,

Il me faudrait des exemples de ce que tu entends par récurrence immédiate; mais pour moi, cela ne veut rien dire. Personnellement, les seuls fois ou j'ai entendu parler de récurrence immédiate, c'était pour dire qu'il était inutile d'écrire la preuve de la récurrence avec initialisation/hérédité car le résultat était immédiat une fois écrit.

Donc, ce concept est très subjectif en fonction de ton niveau scolaire et de la personne qui va lire ton travail.

Sinon, pour récurrence faible vs forte c'est plutot :

faible : n => n+1
forte : 0, .. , n => n+1

-
Edité par edouard22 5 mai 2018 à 10:27:38

Ok ! je comprend mieux pourquoi on ne trouve rien sur la récurrence immédiate ce n'est pas une autre méthode de faire de la récurrence, c'est juste pour dire autrement "récurrence triviale".

...(j'essaie de formuler mes 2 exos en mathjax ou latex mais j'ai du mal visiblement je ne suis pas doué, je teste en ligne mais il faudrait ici aussi avoir la possibilité de prévisualiser )

Bref l'exercice et le correction porte sur les puissance nième d'une matrice. Et dans la correction la récurrence n'est pas forcément pour moi intuitive rapidement donc pas immédiate

-
Edité par mitakuye 5 mai 2018 à 11:29:49

C'est vrai que si les corrections sont concises, souvent on voit quelque chose du genre : « Par une récurrence immédiate, on a : ». Ça veut juste dire que la récurrence est facile : il suffit d'écrire les choses et faire les calculs (même s'ils sont longs), ça n'a donc aucun intérêt d'être détaillé. Une récurrence qui n'est pas immédiate, c'est par exemple lorsque pour établir l'hérédité, il faut appliquer un certain théorème et, donc, vérifier certaines hypothèses : c'est un travail en plus.

De façon générale, je pense qu'on peut dire qu'une démonstration est immédiate lorsque, pour démontrer que A implique B, on part de A et on aboutit à B (par exemple pour démontrer l'hérédité, on calcule la propriété à l'ordre n+1 et on trouve qu'elle correspond à la formule à démontrer). Une démonstration n'est pas immédiate lorsque, pour aller de A à B, on doit prendre des chemins de traverse : aller de A à C, aller de B à D, puis démontrer que C implique D, éventuellement en utilisant un théorème dont on doit d'abord démontrer les hypothèses. Bref, ce n'est pas direct, il faut réfléchir à un cheminement, qu'on ne trouvera pas du premier coup... Là, la correction doit indiquer toutes les étapes.

immédiate ou pas, forte ou pas  ?  \(A \rightarrow B \) ou \(A \rightarrow?  \rightarrow?  \rightarrow B \)   

montrer par récurrence que \(\forall n\geq 1, n! \leq \left(\frac{n+1}{2}\right)^n\)

-
Edité par Sennacherib 6 mai 2018 à 17:53:30

immédiat A-> B ?

-
Edité par edouard22 6 mai 2018 à 22:12:14

si B est vrai alors A est nécessairement vrai sinon A->B est faux OU B est faux !?

Pour mon problème je me suis attaqué à un autre exo de matrice et puissance de n où là je n'ai pas regardé encore la correction mais si c'est encore "immédiat" alors là... je vais me poser des questions non immédiates sur moi... car à C^4 j'ai pas encore de suite évidente sur les résultats (j'ai même refait les calculs pour être sur mais non c'est bon et c'est un matrice carré diagonale donc pas de problème pr avancer dans les calculs direct mais pour trouver 'n' je vais peut-être devoir passer par quelque chose de moins "immédiat")

mitakuye a écrit:

si B est vrai alors A est nécessairement vrai sinon A->B est faux OU B est faux !?

Pas sur d'avoir compris, A implique B signifie que lorsque A est vraie, B l'est aussi on le note A => B. Le fait que A soit faux; n'implique pas que B soit faux également. En revanche, tu sais que si B est faux, alors A l'est aussi : A => B  est équivalent à non B => non A  c'est la contraposé.

edouard22 a écrit:

immédiat A-> B ?

-
Edité par edouard22 il y a environ 10 heures

je suppose que ta remarque concerne mon exemple
je ne crois pas ou alors j'attends ta preuve immédiate...

-
Edité par Sennacherib 7 mai 2018 à 8:41:03

Sennacherib a écrit:

edouard22 a écrit:

immédiat A-> B ?

-
Edité par edouard22 il y a environ 10 heures

je suppose que ta remarque concerne mon exemple
je ne crois pas ou alors j'attends ta preuve immédiate...

-
Edité par Sennacherib il y a environ 1 heure

Instincivement, les deux quantités sont égales pour n=1; et une fonction en n^n croit plus vite que n!
Sinon, tu as la preuve écrite ici : https://math.stackexchange.com/questions/76130/n-leq-left-fracn12-rightn-via-induction (qui n'est finalement pas si trivial;  mais quand même )

-
Edité par edouard22 7 mai 2018 à 11:11:11

Ce que tu dis "instinctivement" reste une preuve ornithoryntique de l'inégalité demandée, pas mathématique . 
oui OK ton lien est une  preuve possible connue   mais ce n'est pas ce j'appelle une récurrence immédiate au sens évoqué ici... 

( qu'est ce tu as trouvé de façon "immédiate", la preuve ou le lien ?...  attention, je ne dis pas qu'elle n'est pas trouvable proprement par un étudiant cherchant un peu )

J'ai une autre preuve de cette inégalité encore moins "immédiate" qui part de la relation bien connue de tout ornithorynque dés le berceau et qui pourrait illustrer une récurrence "forte":
\((n+1)!=1.1!+ 2.2! +...+k.k!+...n.n!\) 

Le but initial de ma remarque avec cet exemple  était une considération sur une certaine inutilité du vocabulaire  jusque à   un certain niveau de purisme: immédiate, faible , forte  . On peut aussi parler de la notion de récurrence bien fondée et voir que le principe de récurrence est équivalent à celui de bon ordre... et on peut remonter de fil en aiguille aux axiomes de Peano 

Bref pour l'usage courant, comme tu l'as dit toi-même dans un des posts , tout cela est très subjectif  et je dirais qu'il y a des récurrences plus ou moins faciles à établir.

-
Edité par Sennacherib 7 mai 2018 à 11:45:17

Certes, mais on trouve quand même souvent des corrections où tout n'est pas détaillé, sous prétexte que c'est « immédiat ». Et je trouve ça normal.

De nos jours, la récurrence est présentée en terminale. À ce moment là, il est nécessaire de tout corriger puisque c'est une notion nouvelle. Mais imaginons un problème de licence (par exemple) dont une question nécessite une démonstration par récurrence. Si cette récurrence est « immédiate », c'est-à-dire s'il faut juste écrire les choses et se laisser guider par les calculs, il est inutile de la mettre dans la correction. On dira juste « par une récurrence immédiate ». Par contre, si la récurrence ne se fait pas par un simple petit calcul, mais nécessite par exemple d'utiliser un certain théorème, ou utilise une certaine astuce, là il faut au moins en parler dans la correction, genre : « en appliquant Cauchy-Schwartz et le résultat de la question 2.6, on démontre par récurrence que... ». Là ce n'est plus immédiat : il faut détailler.

La récurrence ci-dessus n'est pas « immédiate » puisqu'en se laissant guider par les calculs on trouve :

\[ (n+1)! \leq (n+1)\dfrac{(n+1)^n}{2^n} = \dfrac{(n+1)^{n+1}}{2^n}, \]

qui n'est pas le résultat cherché. (Elle aurait été « immédiate » si on était tombé directement sur \( 2^{n+1} \).)

-
Edité par robun 7 mai 2018 à 12:09:08

robun a écrit:

 La récurrence ci-dessus n'est pas « immédiate » puisqu'en se laissant guider par les calculs on trouve :

\[ (n+1)! \leq (n+1)\dfrac{(n+1)^n}{2^n} = \dfrac{(n+1)^{n+1}}{2^n}, \]

qui n'est pas le résultat cherché. (Elle aurait été « immédiate » si on était tombé directement sur \( 2^{n+1} \).)

-
Edité par robun il y a 3 minutes

c'est bien dans ce sens que je "réfutais" le caractère immédiat de cet exemple  supposé par edouard22.

Ah oui, OK.