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

[Kikoo <3 Bieber]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Fait chier LaTeX... :/

[Nightmare]

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

[Kikoo <3 Bieber]

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

[Luc]

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]

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]

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]

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.