Récurrence multiple (et autres questions sur les suites)

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Kikoo <3 Bieber
Membre Transcendant
Messages: 3814
Enregistré le: 28 Avr 2012, 11:29

Récurrence multiple (et autres questions sur les suites)

par Kikoo <3 Bieber » 04 Sep 2012, 20:52

Salut,

Premier jour de cours, je rentre avec un polycop de maths à étudier.
Je dois traiter un exemple (récurrence double) :

Soit une suite définie par récurrence telle que :
;

Il me faut trouver en fonction de n.

On m'explique ensuite immédiatement le principe, mais j'ai du mal à le comprendre :

th : On vérifie vraies et on montre que pour
si sont vraies alors est vraie. On conclut


En fait le "point de pivot" de la démonstration est le p-ième terme, nan ? Mais dans ce cas-là, quelle est fastidieuse !



acoustica
Membre Irrationnel
Messages: 1043
Enregistré le: 08 Juil 2008, 12:00

par acoustica » 04 Sep 2012, 20:59

Kikoo <3 Bieber a écrit:Salut,

Premier jour de cours, je rentre avec un polycop de maths à étudier.
Je dois traiter un exemple (récurrence double) :

Soit une suite définie par récurrence telle que :
;

Il me faut trouver en fonction de n.

On m'explique ensuite immédiatement le principe, mais j'ai du mal à le comprendre :



En fait le "point de pivot" de la démonstration est le p-ième terme, nan ? Mais dans ce cas-là, quelle est fastidieuse !


Le principe de la récurrence multiple (qu'on appelle en fait "récurrence forte", et qui n'est pas vraiment une récurrence multiple à proprement parler puisqu'il n'y a pas de récurrences imbriquées, est la suivante : avant on disait "on suppose que c'est vrai au rang n, montrons que c'est vrai au rang n+1". Maintenant on dit "supposons que ce soit vrai jusqu'au rang n, montrons que c'est vrai au rang n+1". Dans ton exemple, ce serait plutôt "montrons que c'est vrai aux rangs n et n+1, montrons que c'est vrai au rang n+2". L'idée est que parfois tu n'as pas seulement besoin de l(hypothèse au rang n, mais aussi des précédantes. Mais si tu utilises les deux rangs d'avant, ton initialisation doit porter sur les DEUX premiers termes : si seul le premier marche et pas le deuxième, comment pourrait-tu supposer que les rangs 1 et 2 permettent d'établir le rang 3 ?

Luc
Membre Irrationnel
Messages: 1806
Enregistré le: 28 Jan 2006, 14:47

par Luc » 04 Sep 2012, 21:04

La récurrence forte c'est comme la récurrence simple, sauf qu'au lieu d'utiliser P(n-1) pour prouver P(n), on utilise P(n-d),P(n-(d-1)),...,P(n-1). Comme le dit acoustica, le saut conceptuel n'est pas gênant. En revanche, il faut faire très attention à l'initialisation en la vérifiant pour suffisamment de termes. (sinon on peut prouver des trucs absurdes, du genre tous les crayons de couleur d'une boite de crayons sont de la même couleur...)

L'exercice avec la suite U_n est un exemple d'application. Il se trouve qu'il est assez mal choisi parce que dans ce cas particulier, on peut calculer U_n sans utiliser de récurrence, mais cela demande des connaissances en algèbre linéaire. On peut bien sûr "intuiter" la forme de U_n, puis démontrer cette formule par récurrence (double) sur n.

Luc

Kikoo <3 Bieber
Membre Transcendant
Messages: 3814
Enregistré le: 28 Avr 2012, 11:29

par Kikoo <3 Bieber » 04 Sep 2012, 21:34

Alors là, je vous remercie énormément pour l'aide rapide que vous m'apportez ! :)

J'avais aussi essayé de calculer les premiers termes pour conjecturer une expression mais j'ai fait choux blanc (mais dans l'ambiance du bizuthage c'est pas facile de se concentrer).
J'essaierai de voir ça, merci encore à vous deux ;)


PS : Acoustica, justement il me semblait que récurrence forte et récurrence multiple ne sont pas des raisonnements semblables, vu que dans la récurrence forte on suppose que la propriété est vraie jusqu'au rang n et on essaie de la prouver au rang n+1.
Ici, l'énoncé du théorème est sensiblement différent je trouve.

SaintAmand
Membre Rationnel
Messages: 901
Enregistré le: 17 Oct 2011, 13:47

par SaintAmand » 04 Sep 2012, 21:54

Kikoo <3 Bieber a écrit:J'avais aussi essayé de calculer les premiers termes pour conjecturer une expression mais j'ai fait choux blanc (mais dans l'ambiance du bizuthage c'est pas facile de se concentrer).
J'essaierai de voir ça, merci encore à vous deux ;)


1. Cherche deux suites géométriques et qui vérifient la relation de récurrence.

2. Soit . Montre que la suite définie par



vérifie la relation de récurrence.

3. Détermine et pour que et

4. Montre qu'il n'y a pas d'autres solutions.

acoustica
Membre Irrationnel
Messages: 1043
Enregistré le: 08 Juil 2008, 12:00

par acoustica » 04 Sep 2012, 21:55

Kikoo <3 Bieber a écrit:Alors là, je vous remercie énormément pour l'aide rapide que vous m'apportez ! :)

J'avais aussi essayé de calculer les premiers termes pour conjecturer une expression mais j'ai fait choux blanc (mais dans l'ambiance du bizuthage c'est pas facile de se concentrer).
J'essaierai de voir ça, merci encore à vous deux ;)


PS : Acoustica, justement il me semblait que récurrence forte et récurrence multiple ne sont pas des raisonnements semblables, vu que dans la récurrence forte on suppose que la propriété est vraie jusqu'au rang n et on essaie de la prouver au rang n+1.
Ici, l'énoncé du théorème est sensiblement différent je trouve.


Non en effet ce n'est pas pareil. Si tu veux un bon exemple de récurrence forte, je te propose dans le document animath la section sur eXclusive Or : http://www.animath.fr/IMG/pdf/cours-base2.pdf

On a besoin de TOUS les indices d'avants. Mais on n'a besoin que d'une seule initialisation, ce qui n'est pas le cas de la récurrence multiple.

Luc
Membre Irrationnel
Messages: 1806
Enregistré le: 28 Jan 2006, 14:47

par Luc » 04 Sep 2012, 22:18

SaintAmand a écrit:1. Cherche deux suites géométriques et qui vérifient la relation de récurrence.
2. Soit . Montre que la suite définie par

vérifie la relation de récurrence.
3. Détermine et pour que et
4. Montre qu'il n'y a pas d'autres solutions.

C'est effectivement la méthode à utiliser si tu ne peux pas "intuiter" U_n. Chercher des solutions sous la forme de suites géométriques revient à résoudre l'équation r^2-3r+2=0 (d'inconnue r comme raison). Cette équation s'appelle l'équation caractéristique associée à la récurrence linéaire. Cette méthode n'est pas magique, elle est tout à fait générale (pour une récurrence triple, ..., ou d'ordre quelconque). Le nom "caractéristique" vient du "polynôme caractéristique" (notion de maths spé) d'une certaine application linéaire. Si l'équation caractéristique n'a que des racines simples, tout va bien, U_n est une combinaison linéaire de suites géométriques. En revanche si elle a une racine multiple, cela complique un peu les choses. Si est une racine double par exemple, il faut chercher les solutions correspondantes sous la forme . Le degré du polynôme en n que l'on met en facteur de est égal à la multiplicité de la racine moins un.

acoustica
Membre Irrationnel
Messages: 1043
Enregistré le: 08 Juil 2008, 12:00

par acoustica » 04 Sep 2012, 22:31

Luc a écrit:C'est effectivement la méthode à utiliser si tu ne peux pas "intuiter" U_n. Chercher des solutions sous la forme de suites géométriques revient à résoudre l'équation r^2-3r+2=0 (d'inconnue r comme raison). Cette équation s'appelle l'équation caractéristique associée à la récurrence linéaire. Cette méthode n'est pas magique, elle est tout à fait générale (pour une récurrence triple, ..., ou d'ordre quelconque). Le nom "caractéristique" vient du "polynôme caractéristique" (notion de maths spé) d'une certaine application linéaire. Si l'équation caractéristique n'a que des racines simples, tout va bien, U_n est une combinaison linéaire de suites géométriques. En revanche si elle a une racine multiple, cela complique un peu les choses. Si est une racine double par exemple, il faut chercher les solutions correspondantes sous la forme . Le degré du polynôme en n que l'on met en facteur de est égal à la multiplicité de la racine moins un.


Et si est une racine triple, il faut chercher les solutions correspondantes sous la forme non ?

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 04 Sep 2012, 22:32

Salut à tous,

je me souviens avoir deux ou trois fois rencontré une récurrence particulière faisant intervenir les 2^n, mais incapable de trouver quoi que ce soit y ressemblant sur le net.

Quelqu'un a-t-il une idée du résultat dont je veux parler?

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 04 Sep 2012, 22:37

Ah c'est bon, je l'ai retrouvé sur wikipédia, il ne s'agit pas de 2^n mais de 2n.

Le critère :

Si P(1) vraie
Si P(n) vraie => P(2n) vraie
Si P(n+1) vraie => P(n) vraie
Alors P(n) vraie pour tout n.

La preuve n'est pas inintéressante à travailler. Voyez-vous un bon exercice d'application de cette récurrence particulière?

Luc
Membre Irrationnel
Messages: 1806
Enregistré le: 28 Jan 2006, 14:47

par Luc » 04 Sep 2012, 22:38

acoustica a écrit:Et si est une racine triple, il faut chercher les solutions correspondantes sous la forme non ?

Non, il faut chercher sous la forme .
On garde autant d'inconnues scalaires que la multiplicité de la racine. http://en.wikipedia.org/wiki/Recurrence_relation#cite_note-0

Kikoo <3 Bieber
Membre Transcendant
Messages: 3814
Enregistré le: 28 Avr 2012, 11:29

par Kikoo <3 Bieber » 04 Sep 2012, 22:38

SaintAmand a écrit:1. Cherche deux suites géométriques et qui vérifient la relation de récurrence.

2. Soit . Montre que la suite définie par



vérifie la relation de récurrence.

3. Détermine et pour que et

4. Montre qu'il n'y a pas d'autres solutions.

Salut SaintAmand,

Pour le 1, je trouve deux suites géométriques et .

Pour la 2 :


Il vient de suite
De même,
La suite vérifie la relation de récurrence.

Pour la 3,
Il nous faut que
et que
et là je trouve pas de solution ??? :mur:

Kikoo <3 Bieber
Membre Transcendant
Messages: 3814
Enregistré le: 28 Avr 2012, 11:29

par Kikoo <3 Bieber » 04 Sep 2012, 22:38

SaintAmand a écrit:1. Cherche deux suites géométriques et qui vérifient la relation de récurrence.

2. Soit . Montre que la suite définie par



vérifie la relation de récurrence.

3. Détermine et pour que et

4. Montre qu'il n'y a pas d'autres solutions.

Salut SaintAmand,

Pour le 1, je trouve deux suites géométriques b_n=2\times 2^n et a_n=3\times 2^n.

Pour la 2 :
u_n=2\alpha 2^n + 3\beta 2^n=2^n(2\alpha+3\beta)

Il vient de suite u_{n+2}=2^n(8\alpha+12\beta)
De même, 3u_{n+1}- 2 u_n=3(2^{n+1}(2\alpha+3\beta))-2(2^n(2\alpha+3\beta)) \\
=2^n(2\alpha+3\beta)\times 4=2^n(8\alpha+12\beta)=u_{n+2}
La suite (u_n)_{n\in\mathbb{N}} vérifie la relation de récurrence.

Pour la 3,
Il nous faut que u_0=2\alpha+3\beta=2
et que u_1=4\alpha+6\beta=3
et là je trouve pas de solution ??? :mur:

Edit : je suis obligé de modifier mon message en raison du bug...

Kikoo <3 Bieber
Membre Transcendant
Messages: 3814
Enregistré le: 28 Avr 2012, 11:29

par Kikoo <3 Bieber » 04 Sep 2012, 22:39

Fait chier LaTeX... :/

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 04 Sep 2012, 22:40

A mon avis Tom_Pascal est en train de bosser dessus :happy3:

Kikoo <3 Bieber
Membre Transcendant
Messages: 3814
Enregistré le: 28 Avr 2012, 11:29

par Kikoo <3 Bieber » 04 Sep 2012, 22:42

Ah d'ac ^^ Je vais être patient alors !

Luc
Membre Irrationnel
Messages: 1806
Enregistré le: 28 Jan 2006, 14:47

par Luc » 04 Sep 2012, 22:48

Nightmare a écrit:Ah c'est bon, je l'ai retrouvé sur wikipédia, il ne s'agit pas de 2^n mais de 2n.

Le critère :

Si P(1) vraie
Si P(n) vraie => P(2n) vraie
Si P(n+1) vraie => P(n) vraie
Alors P(n) vraie pour tout n.

La preuve n'est pas inintéressante à travailler. Voyez-vous un bon exercice d'application de cette récurrence particulière?

Oui, l'inégalité arithmético-géométrique par récurrence (preuve due à Cauchy je crois). C'était mon 1er TD de sup :) C'est le seul résultat à ma connaissance par contre.

Luc
Membre Irrationnel
Messages: 1806
Enregistré le: 28 Jan 2006, 14:47

par Luc » 04 Sep 2012, 22:51

Kikoo <3 Bieber a écrit:
Pour le 1, je trouve deux suites géométriques et .

Non, tu as du faire une erreur de calcul :hein: Vérifie.

Tom_Pascal
Membre Relatif
Messages: 141
Enregistré le: 15 Aoû 2005, 17:38

par Tom_Pascal » 04 Sep 2012, 22:53

A mon avis Tom_Pascal est en train de bosser dessus


Ah d'ac ^^ Je vais être patient alors !


Yep, désolé.. je tatonne un peu .

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 04 Sep 2012, 22:54

Effectivement, ça serait pas mal pour un oral d'Algèbre sur la construction de N ça non? :lol3: (concours, toujours penser concours!)

Je viens d'en trouver une autre, apparemment attribuée à Cauchy, très jolie aussi :

Si :
- P(0) vraie
- Pour tout n, il existe un k > n tel que P(k) vraie
- P(n) vraie => P(n-1) vraie

Alors P(n) vraie pour tout n.

Edit : la condition 2 est équivalente à "il existe une infinité d'entiers n tels que P(n) vraie"




Je vais voir si je trouve un exo d'application.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 37 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite