Résolution d'une relation de récurrence.

w1

Bonjour, je suis en train de reviser un annale de maths niveau L3 info et je bloques sur une recurrence linéaire que l'on doit ressoudre à l'aide d'un polynome caracteristique. Tout irai bien si il n'y avait pas une constante dans la relation :

A(n) = 2 * A(n-1) + 1, A(0) = 1.

J'ai essayé de faire une substitution en definissant une suite B(n) mais rien n'y fait, je n'arrive pas a retomber sur mes pieds.

Avez une solution ou une piste sur laquelle je pourrais travailler?
Amicalement.


[J'ai ramené le niveau à L1/L2. AD]

bisam

Pas besoin de polynôme caractéristique... n'importe quel élève de TS devrait savoir faire ça.

Cherche une suite géométrique de la forme B(n)=A(n)+c où c est une constante à déterminer.
Ensuite, tu devrais pouvoir t'en sortir.

Hugo_

Il faut poser $B_n= A_n + r$ ou r est une constante bien choisie qui fait en sorte que $B_n$ devienne géometrique (on trouve que $r$ est solution d'une petite équation toute bête)

Le barbu rasé

Mais, mille sabords, les suites arithmético-géométriques, ça se calcule {\bf bêtement} et {\bf simplement} :
$u_n = a.u_{n-1}+b$ donne
$u_n= a.(a.u_{n-2}+b)+b$
$u_n= a.(a.(...(a.u_0+b)...)+b)+b$
$u_n = a^n.u_0+a^{n-1}.b+a^{n-2}.b+...+a.b+b$
$u_n = a^n.u_0 + b . \sum_{i=0}^{n-1} a^i$
$u_n = a^n.u_0 + b\frac{a^n-1}{a-1}$
et on n'en parle plus...
(c'est quand même plus simple que de "bien choisir" une constante pour laquelle...)

GERARD

Effectivement, Barbu rasé, c'est plus simple .... pour quelqu'un qui calcule bien. Alors que la méthode de la constante auxiliaire donne, pour les élèves de ES par exemple, moins de calculs (3 ou 4 lignes).

Cordialement

Aleg

Gerard,
pour moi, ce n'est pas tellement que la méthode du barbu soit plus simple, c'est surtout qu'elle est très élégante.

GERARD

Oui, moi aussi je l'aime bien.

Richard André-Jeannin

La méthode du barbu-rasé est ..rasante. Je ne vois pas ce qu'on peut trouver d'élégant là-dedans.
De plus ce n'est pas une vraie preuve, mais un moyen pour deviner le résultat final qu'on peut ensuite montrer par récurrence.
Il est beaucoup plus simple de chercher une solution constante, autrement dit un nombre k tel que:
k=ak+b (k existe si a différent de 1, et si a=1, la suite est arithmétique).
On a:
u(n)=a*u(n-1)+b
k=ak+b
et par soustraction, en posant v(n)=u(n)-k:
v(n)=a*v(n-1). La suite v(n) est géométrique et après, ça roule tout seul.

Le barbu rasé

<< La méthode du barbu-rasé est ..rasante. Je ne vois pas ce qu'on peut trouver d'élégant là-dedans. >>

D'accord avec toi, RAJ.
Ni élégante, ni émoustillante.
Mais, indéniablement, elle est plus simple à mes yeux.


<< De plus ce n'est pas une vraie preuve, mais un moyen pour deviner le résultat final qu'on peut ensuite montrer par récurrence. >>

Là je ne suis pas d'accord.
Je ne vois pas pourquoi un calcul ne serait pas une preuve (et même la meilleure des preuves) pour établir une égalité.
C'est comme la preuve purement combinatoire du binôme de newton: pour moi, c'est une preuve.


<< Il est beaucoup plus simple ... >>

Peut-être. Quand j'étais en première, on m'a présenté les suites arithmético-géométriques. La méthode de calcul explicite m'a parue "tombée du chapeau" et compliquée. Puis j'ai réfléchi et j'ai réalisé que le résultat pouvait provenir d'un calcul banal, enfantin à retrouver. A l'époque cette seconde approche m'a parue plus simple. Aujourd'hui, elle me paraît toujours plus simple. Mais chacun ses goûts.

Si w1 (qui, disons, représente un terrain vierge) trouve mon explication peu satisfaisante, alors, c'est qu'elle est effectivement peu satisfaisante. En attendant, je reconnais volontiers qu'il n'y a pas une façon de voir les choses et que mon message initial pouvait paraître péremptoire (j'essayais seulement d'être amusant :-|)...

AlexB

Je me rappelle que quand je faisais des td d'algo, les étudiants aimaient bien écrire (pour a(n)=2a(n-1)+1, a(0)=1) :

a(n) = 2a(n-1)+1
2 a(n-1) = 4a(n-2)+2
...
2^k a(n-k) = 2^(k+1) a(n-k-1)+2^k
...
2^n a(0) = 2^n

après ils ajoutaient tout, simplifiaient et c'était fini (modulo le calcul de somme). Bilan : on a le résultat, c'est peu être pas très élégant (franchement, pour un futur ingénieur qui veut connaitre la complexité d'un programme c'est bien suffisant quand on pense que d'autres vont le lancer 10000 fois sur des entrées prises au hasard et chronométrer) et je pense que ça s'adapte à d'autres types de récurrences (sous réserve, finalement, que l'on sache calculer la somme qui apparait à droite).

Domi

Il est vrai que Richard à la dent dure , j'aime bien les interventions du barbu avec ou sans barbe et je comprends sa RAJ .

Vous avez un problème de couple , au travail , ... contacter : "Les-Mathématiques.net , Domi ( hors heures de bureau ) vous aurez une réponse dans les 24 heures .

Domi

Richard André-Jeannin

Un entassement de parenthèses avec plein de ....n'a jamais constitué une preuve. Imaginez vous présenter ça devant un jury de CAPES, ou plus simplement devant une classe.
Encore une fois, on peut utiliser cette méthode pour "deviner" le résultat, mais pas plus.

Yalcin

si non , ( je vais répéter je crois ) on fait :
Pour tout n de IN , on a : A(n+1)-k=2A(n)+1-k ,avec k un réel
Donc A(n+1)-k=2(A(n)-(k-1)/2) , et là on va chercher pou rêtre malin un k tel que : k=(k-1)/2 , d'où k=-1.
Donc A(n+1)-1=2(A(n)-1) et là on trouve la solution

le dadaiste

Je soutiens personnellement le barbu, et en particulier si on s'adresse a des élèves de lycée, car c'est une méthode quand même plus "constructive" à mon gout, que l'autre méthode, qui est très bien aussi, mais qui, je trouve, demande déjà un peu une espèce de "conjecture".

Coridalement, le dadaiste

Domi

D'accord Richard ,

je comprends tout à fait ta position mais instinctivement j'avais adopté celle du barbu rasé ( qui n'est pas une preuve ) . Mais bon nous ne sommes pas à l'oral du Capes ou de l'Agreg ( c'est du passé ) ni devant une classe . J'adore les artifices quand ils apportent une solution inespérée sinon , si c'est pour gagner quelques lignes ou apporter un peu de rigueur ...

Amicalement , Domi

Richard André-Jeannin

Ouais, mais, une équation linéaire avec second membre, il faut bien un jour ou l'autre apprendre à la résoudre.

Pour le dadaïste: Vous vous imaginez présenter tous les parasenthésages du barbu (j'en suis un autre) devant une classe de lycée?

Quant à l'autre méthode (recherche du nombre k tel que k=ak+b), je la présente à mes étudiants non pas comme la recherche d'une solution constante de la récurrence (ils seraient tous collés au plafond de l'amphi), mais comme iun calcul préliminaire: "on va chercher le nombre k tel que k = ak+b et on va voir que ça va nous servir".

PS. Le passage en TD montre que k=ak+b pose déjà de gros problèmes à beaucoup d'entre eux. Je ne vais pas m'étendre sur la 'baisse de niveau".

Domi

Richard ,

viens passer quelques jours au collège , les élèves arrivant en 6ème ne savent pas faire une division ( nouveau programmes de l'école primaire ) et (calculatrice oblige ) les élèves de 3ème ne connaissent plus leur tables de multiplication . chacun sa merde ( tant qu'on arrive à en rire ) .

Pour les réaction épidermiques je peux faire encore bien pire que toi ( à mon grand regret ) .

Domi

Christian Vassard

Salut,
Moi j'aime bien la méthode suivante...
J'appelle c le point fixe qui vérifie:
$c = ac+b$
Egalité que l'on rapproche de :
$u_{n+1}=au_n+b$
Par soustraction, on en tire:
$u_{n+1}-c=a(u_n-c)$
et voilà la suite géométrique...
On termine classiquement...
Cordialement,
Christian V

kilébo

RAJ ne voit pas pourquoi tu ne considères pas la méthode du barbu rusé comme une preuve. Pour moi, elle l'est. Indiscutablement.

Il s'agit de produits et de sommes en nombre finis. Il n'a simplement utilisé que la distributivé et l'associativité (toujours dans le cas d'un nombre finis d'élements). Franchement c'est irréprochable.

Le seul reproche que l'on puisse faire à ce calcul, c'est de donner l'impression d'être obligé de "refaire" le calcul à chaque rang dans le sens où l'on ne profite pas du calcul du rang précédent comme on le fait dans une récurence.

Par contre, je me montre incompétent pour dire si les élèves vont trouver ça plus simple ou même plus élégant. Pourquoi ne pas présenter les deux façons de faire ?

GERARD

Bonjour.

Pour une fois, je ne suis pas d'accord avec RAJ. La preuve est rédigée "rapidement", mais elle est logiquement saine, à condition de justifier le nombre de parenthèses, ce qui peut se faire par récurrence. Evidemment je ne présenterais pas ça au jury de l'agreg ou du capes. Ils sont tellement formalistes qu'il ne faut prendre aucun risque.
Je le rappelle, la rigueur ce n'est pas une question d'écriture, mais de vérification qu'on ne se trompe pas.

Cordialement