[Term S] Explication sur le raisonnement par récurrence.

Bonjour j'aimerai trouver des astuces ou des aides pour effectuer un raisonnement par récurrence.

Parce que c'est un outil très pratique pour prouver tout plein de chose.

Problème c'est que je vois comment faire mais je ne sais absolument pas le formuler.

Ensuite je suis ouvert à des astuces qui me permettront d'aller plus vite.

Merci beaucoup ++

Bonsoir,

J'ai déplacé ton sujet pour le mettre dans la partie cours car je pense qu'il s'agit purement de cours pour le coup.

Le raisonnement par récurrence est un raisonnement très pratique en mathématiques et repose sur un aspect purement logique des choses. Mais attention au raisonnement faux. ET pour éviter cela, je vais commencer par te montrer que tous les crayons d'un ensemble sont d'une même couleur.

En effet, j'initialise en disant que j'ai deux crayons de la même couleur et je suppose que ceci est vrai. A partir de là, si je prend deux crayons et que je suppose que 9 sont de la même couleur alors je peux dire que les 9 premiers sont de la même couleur et que les neuf dernier aussi.

Conclusion, ils sont tous de la même couleur vu qu'il y a une couleur commune au 10.

Ce raisonnement est bien entendu faux et pourtant il paraît vrai. Le soucis vient de l'initialisation. En effet, j'ai initialiser pour deux crayon ce qui permet de faire fonctionner mon hérédité mais je ne peux pas initialiser pour trois crayons car celui du milieu peu avoir une couleur différente de deux extrémités ce qui met le raisonnement à plat.


Alors l'importance d'un raisonnement par l'absurde se voit tout de suite ici: "Il faut savoir jusqu'à quel rang, il faut initialiser"

Le plus souvent, on dit que pour n=0 ça marche et on démarre sur l'hérédité mais dès fois on a besoin de l'hérédité d'avoir le fait que pour n=1 c'est vrai et si on ne l'a pas initialiser au départ et bien notre raisonnement n'est plus bon.

La deuxième chose à faire après avoir bien initialisé, c'est l'hérédité c'est à dire que si notre propriété est vrai au rang n-1 alors elle est vraie au rang n.

Alors jusque là tout paraît simple mais le soucis d'une récurrence c'est qu'il n'y a pas de façon prédéfinie pour résoudre une récurrence, tout dépend de la propriété à démontrer. Il faut donc avoir une capacité d'adaptation face à ce qu'on doit démontrer par récurrence pour pouvoir résoudre le problème.

Cependant, il n'y a pas besoin d'être très doué pour savoir faire des récurrence, il suffit juste d'en avoir fait un minimum pour appliquer la méthode plusieurs fois et voir les mécanismes de réflexion qui sont sous jasent.

Et bien fini et bavarder sur la théorie passons à la pratique. On sait qu'une récurrence est faisable à partir du moment où nous avons une propriété qui doit être montrer pour tous entier car il faut passer d'un rang au suivant, il faut donc utiliser des entiers pour se faire. C'est donc pour celà que les raisonnement par récurrence sont appliqué essentiellement sur les suites car il s'agit de démontrer qu'une propriété est vraie pour tout n et donc pour tout entier.

Alors voyons un exemple concret car les récurrence, il faut pratiquer.

Citation :

Soit U_n définie par U₀=1 et U_n+1=√(2+U_n)

Démontrer que pour tout nЄN, 0<U_n<2

Il s'agit d'un exercice classique dans le genre et qu'on peut retrouver par exemple dans 100%Exo Maths TermS. Ce bouquin d'exercice à quelque défaut mais c'est un bon livre pour de l'entraînement et faire quelque exerccie type.

Alors je pourrait rédiger la réponse de façon brut de décoffrage mais le mieux c'est que ça soit toi qui écrive pour voir comment tu t'y prends et ainsi nous verrons ensemble si ce que tu fais est juste ou si il y a besoin au niveau de la rédaction d'en ajouter ou d'en enlever.

Bon courage!

Soit Un définie par U0=1 et Un+1=√(2+Un)

Démontrer que pour tout nЄN, 0<Un<2

Démontrons par récurrence que :
P(n) "pour tout nЄN, 0<Un<2"
n = 0

Initialisation
U0 = 1, donc 0 < U0 < 2.
Donc P(0) vrai.

Hérédité
Supposons p(k) vrai c'est à dire que 0<p(k)<2.
Démontrons que p(k+1) est vrai pour un entier naturel k quelconque.
Soit que 0<p(k+1)<2
0< √(2+Uk)< 2

Arf même pour ca je bloque

Bloquer sur la récurrence elle-même n'est pas un soucis car ce qui te bloque est ailleurs en fait mais on va voir ça tranquillement.

Ton initialisation est bonne. On sait que l'énoncer nous donne une relation entre U_n+1 et U_n et par conséquent, si on a U₀, on a U₁ et ainsi de suite. Donc initialiser seulement pour P(0) cela est tout à fait juste.

Je ne sais pas si tu avais fait ce raisonnement là lorsque tu as fait ton initialisation mais en tout cas, tu aurais dû le faire car par exemple si on avait une relation qui nous donnait U_n+2 en fonction de U_n+1 et de U_n et bien on constate que pour avoir U₂, il nous faudra U₀ ET U₁ ce qui nous mènera à faire une initialisation de P(0) ET de P(1) car sinon, notre hérédité n'aurait pas de sens en soi si on initialisait seulement à P(0) car pour montrer P(n+1), on aurait besoin de P(n) ET de P(n-1) et par conséquent, on voit ici le fait qu'il nous fallait initialiser 2 deux valeurs de n pour que notre hérédité soit cohérent.

Est-ce que tu comprends mieux le lien entre l'initialisation et l'hérédité?

Sinon, l'hérédité commence bien mais s'arrête net avec une mauvaise compréhension de ce qu'est P(n) en fait:

Citation :

Hérédité
Supposons p(k) vrai c'est à dire que 0<p(k)<2.
Démontrons que p(k+1) est vrai pour un entier naturel k quelconque.
Soit que 0<p(k+1)<2
0< √(2+Uk-1)< 2

Qu'est-ce que p(k) ou P(k) pour toi? Et si dès fois, tu ne vois pas ton erreur logique, que signifie "0<p(k)<2" sachant que tu as marquer que P(n) "pour tout nЄN, 0<Un<2" ?

Le problème que tu rencontre pour le moment et tu vas t'en apercevoir très vite réside dans le fait que tu ne sais pas concrètement ce que tu manipule et c'est ça qui te bloque dans tes raisonnement, je pense.

Soit Un définie par U0=1 et Un+1=√(2+Un)

Démontrer que pour tout nЄN, 0<Un<2

Démontrons par récurrence que :
P(n) "pour tout nЄN, 0<Un<2"
n = 0

Initialisation
U0 = 1, donc 0 < U0 < 2.
U1 = √(2+U0) = √(2+1) = √3 soit 1.7 en gros. donc bien compris entre 0 < U1 < 2
Donc P(0) vrai.

Bah p(k) c'est que pour un entier naturel k quelconque, p(k) soit vrai donc que p(k) soit compris strictement entre 0 et 2. Donc que Uk-1 et Uk soit tout les deux compris entre 0 et 2

Je ne suis sans doute pas très clair.

Je reprend, je disais que ton initialisation était juste et que P(1) n'était pas utile donc mais je te disait pouruqoi de montrer que P(1) était vraie n'était pas utile et quand il l'était.

Lorsqu'on fait une récurrence, on fait une initialisation qui permet de lever l'ambiguïté lorsqu'on passera à l'hérédité. En effet, si on a une relation entre U_n+1 et U_n par exemple.

On constate que pour passer d'un terme à un autre, on a besoin seulement du terme précédent. Donc on a accès à tous les termes de notre suites à partir du moment où on connaît U₀. C'est pour celà qu'on initialise seulement avec P(0).

Mais en revanche, si on avait une relation entre U_n+2, U_n+1 et U_n, on constate que pour avoir tous les termes de notre suite on a besoin d'au minimum U₀ et de U₁. Par conséquent, si on veut faire une récurrence, il va nous falloir considérer au minimum P(0) et P(1) vraie et donc initialiser les deux et non seulement P(0).

Est-ce plus clair ainsi?


Sinon, lorsque tu écris ceci:

Citation :

Bah p(k) c'est que pour un entier naturel k quelconque, p(k) soit vrai donc que p(k) soit compris strictement entre 0 et 2. Donc que Uk-1 et Uk soit tout les deux compris entre 0 et 2

Il y a une grosse confusion entre une propriété et le terme d'une suite. Alors reprenons, on pose au début notre propriété de récurrence qui est:

P(n): "pour tout nЄN, 0<Un<2"

P(n) est une prorpiété qu'on va démontrer par récurrence. Par conséquent, P(n) est un objet mathématique qu'on appelle une propriété, c'est l'énoncer d'une phrase dont on cherche à démontrer la véracité. Pour te faire une analogie un peu frappante, je dirai que "P(n)" c'est un peu comme "théorème", comme "propriété", comme "proposition", c'est un objet qui ne se manipule pas de façon mathématique.

Tu ne dirais pas "Propriété" est compris entre 0 et 2, j'en suis certain et pourtant lorsque tu écris P(k) est compris entre 0 et 2 c'est comme si tu disais celà. Tu te rends sans doute compte maintenant du problème.

Et maintenant, on va pouvoir aborder un autre soucis c'est la définition même de P(n). En effet, tu écris:

P(n): "pour tout nЄN, 0<Un<2"

Mais si c'est pour tout n, comment cela se fait-il que P dépende de n si la propriété est déjà vrai pour tout n ???????

Et oui, la récurrence est mal posée dès le début car tu ne savais pas ce que tu écrivais et que ça avait un sens mathématique concret, je pense. J'espère que maintenant, cela est plus clair au niveau des termes que tu écris entre P(n) et U_n. Mais c'est bien beau tout ça mais comment écrire P(n) alors???

Et bien, on dit celà:

Soit nЄN, on pose P(n): "0<U_n<2" et le but de notre récurrence c'est de montrer que "Pour tout nЄN, P(n) est vraie" c'est à dire que "Pour tout nЄN, 0<U_n<2".

Alors, je sais que je vais paraître pour un bourreau sans coeur car je viens de remettre en cause toute ta rédaction et je pense que j'ai sans doute remis en cause la conception même de la récurrence là.

Mais est-ce que c'est plus clair maintenant au niveau de la définition des choses et de la manipulation de celles-ci ou je te parle en hiéroglyphe?

Bonsoir,

J'espère que je ne t'ai pas effrayé en remettant en question beaucoup de point mais le but est vraiment de comprendre ce qu'on fait et non d'appliquer une recette de cuisine qui marche car hélas dans un raisonnement par récurrence, le gâteau n'est jamais le même et par conséquent la cuisine est différente à chaque fois. Donc il faut mieux bien comprendre ce qu'on manipule pour mieux comprendre les enchaînements entre chaque étape.

Voici une rédaction qui vaut ce qu'elle vaut mais qui j'espère te montrera ou te remémorera ce que j'ai dit dans mon message précédent sur l'initialisation et sur ce qu'est concrètement P(n).

Citation :

Soit (U_n) définie par U₀=1 et U_n+1=√(2+U_n)

Démontrer que pour tout nЄN, 0<U_n<2

Première remarque au brouillon:

U_n est définie par récurrence et que cette récurrence lie un terme et son suivant. Par conséquent, on constate que possèdant U₀, nous sommes capable de calculer avec plus ou moins de temps, un terme donné de cette suite.
Par conséquent, nous pouvons tenter de répondre à la question par récurrence en initialisan seulement pour n=0.


Rédaction au propre:

Soit nЄN, On pose: P(n): "0<U_n<2"

On va démontrer par réccurence que pour tout nЄN, P(n) est vraie.

Initialisation: Montrer que P(0) est vraie.

On a: U₀=1 et 0<1<2

Donc 0<U₀<2
D'où P(0) est vraie

Hérédité: Supposons P(n) vraie et démontrons que P(n+1) est vraie.

C'est à dire qu'on suppose que 0<U_n<2 et démontrons que 0<U_n+1<2

On sait que: U_n+1=√(2+U_n)

Or par hypothèse de récurrence, 0<U_n<2
Donc 0+2<2+U_n<2+2 c'està dire 2<2+U_n<4

La fonction racine carré est croissante sur R₊, donc on a:

√2 < √(2+U_n)<√4

D'où 0<√2<U_n+1<2

Donc P(n+1) est vraie

La propriété P(n) étant vraie pour n=0 et étant héréditaire, elle est donc vraie pour tout nЄN

Conclusion, Pour tout nЄN, 0<U_n<2



J'ai tendance à trop détailler et certain passage pourrait donc être plus rapide mais le principale est de bien montrer ce qu'on utilise et quand et pourquoi aussi.

J'espère que ceci est plus clair ainsi et n'hésite pas à poser tes questions surtout car cette notion est compliquée assimiler surtout cette histoire d'initialisation et de P(n) mais bon, avec de la pratique et du temps cela devient de plus en plus compréhensible.

Bon courage pour la suite!

Désolé j'étais parti me coucher, parce que bon journée de cours quand même.

Ok j'crois que j'ai pigé pour le raisonnement par récurrence.

Merci beaucoup des explications et de la correction de mes fautes.