m(n) ----- 0 si n = 0
------ 1 + 2 * m (n-1) si n > 0
donne : m(n) = somme de i=0 à n-1 de 2 i = (2 puissance n) - 1
merci pour toute explication,
dans quelle partie d'un cours de math peut on trouver les équations de
récurrence ?
Posted by: Lukas Reck
"pkw" <pa78@netcourrier.com> wrote
>
>je ne vois pas comment :
>
>m(n) ----- 0 si n = 0
> ------ 1 + 2 * m (n-1) si n > 0
>
>donne : m(n) = somme de i=0 à n-1 de 2 i = (2 puissance n) - 1
tu pourrais aussi prouver (par induction, bien sûr =) que
\sum_{i=0}^{n-1} 2^i = 2^{n + 1} - 1.
Lukas Reck
Posted by: pkw
> tu pourrais aussi prouver (par induction, bien sûr =) que
> \sum_{i=0}^{n-1} 2^i = 2^{n + 1} - 1.
en partant de \sum_{i=0}^{n-1} 2^i ou de 2^{n + 1} - 1 ?
Posted by: Lukas Reck
"pkw" <pa78@netcourrier.com> wrote
>> tu pourrais aussi prouver (par induction, bien sûr =) que
>> \sum_{i=0}^{n-1} 2^i = 2^{n + 1} - 1.
>
>en partant de \sum_{i=0}^{n-1} 2^i ou de 2^{n + 1} - 1 ?
>
de quelconque, le résultat est le même.
Posted by: pkw
> >> tu pourrais aussi prouver (par induction, bien sûr =) que
> >> \sum_{i=0}^{n-1} 2^i = 2^{n + 1} - 1.
> >
> >en partant de \sum_{i=0}^{n-1} 2^i ou de 2^{n + 1} - 1 ?
> >
>
> de quelconque, le résultat est le même.
non, je sèche ...
Posted by: Jean-Claude Poujade
"pkw" <pa78@netcourrier.com> wrote in message news:<bodj9l$lf$1@s1.read.news.oleane.net>...
> > >> tu pourrais aussi prouver (par induction, bien sûr =) que
> > >> \sum_{i=0}^{n-1} 2^i = 2^{n + 1} - 1.
> > >
> > >en partant de \sum_{i=0}^{n-1} 2^i ou de 2^{n + 1} - 1 ?
> > >
> >
> > de quelconque, le résultat est le même.
>
> non, je sèche ...
Pas besoin d'induction!
Si on écrit le début de la récurrence
m(0) = 0
m(1) = 1 + 2m(0)
m(2) = 1 + 2m(1)
m(3) = 1 + 2m(2)
....
m(n) = 1 + 2m(n-1)
on constate qu'en ajoutant membre à membre
(même avec des coefficients)
"ça ne marche pas" à cause de la présence du terme constant '1'.
D'où l'idée de faire un changement de variable
pour faire disparaitre ces '1'.
Posons m(n) = a u(n)+b
et remplaçons dans la relation
m(n) = 1 + 2m(n-1)
a u(n)+b = 1 + 2(a u(n-1)+b)
le terme constant disparait
si b = 1 + 2b
c'est à dire b = -1
a étant indifférent mettons-le à 1
on a donc m(n) = u(n)-1
et u(n) = 2u(n-1)
Par conséquent u est une progression géométrique
de premier terme 1 et de raison 2
u(n) = 2^n
donc m(n) = 2^n-1.
Et voilà...
---
jcp