PROPOSITION
Problème.
10. Etant donnée une suite de termes dont les valeurs soient connue^, trouver si cette suite est récurrente, et déterminer dans ce cas la forme générale de ses termes.
Soient les Um mes doiiiiés el connus
T. T', r, T"', T■^...; on en formera la série
T 4- Tx + Tx^ -+- T"x^ + 'V"x' -^...,
que je supposerai égale à s, pour abréger; et il n'y aura (|u'à eliereher si cette série peut résulter du développement d'une fonction rationnelle quelconque, où la plus haute puissance de x dans le numérateur soit moindre que dans le dénominateur.
Supposons d'abord (juc la série proposée soit récurrente du premier ordre; on aura, dans ce cas,
donc
d'où il s'ensuit que, si l'on divise l'unité par le polynôme s, en ordonnant dans l'opération les termes suivant les puissances de x, on trouvera nécessairement un quotient fini de deux termes/? -i- qx.
Supposons ensuite que la série proposée soit récurrente du second ordre; on aura, dans ce cas,
a' -t- b' X a H- bx H- cx^
I a -h bx + ex- ^
7 ~ a'^hlyx '
bx '
bx
qx
qu'on divise le numérateur trinôme a-^ bx -[- ex'- par le dénominateur binôme a' h- b'x, on aura un quotient binôme/? -h qx et un reste a"x'^ ;
donc
d'où je conclus d'abord que, si l'on divise l'unité par le polynôme s, et qu'on pousse la division jusqu'à ce que l'on ait dans le quotient deux termes tels que p -+- qx, ce (jui ne demande que deux opérations, on aui'a un reste qui sera nécessairement divisible par ^c^ et que je représenterai par s' X-, s' étant une nouvelle série de la forme
Donc
~ = p -h qx -\ =z p -h qx -\ — , rr- ;
par conséquent
et de là
Donc, si l'on divise le polynôme s par le polynôme s', on aura nécessairement un quotient fini de deux termes tels que/?'-t- q'x.
Supposons que la série proposée soit récurrente du troisième ordre,
on aura alors
a H- bx -{- ex'' -\- ax^
donc
I a -\- bx + ex'' -\- dx^
qu'on divise le numérateur de cette fraction par son dénominateur, on aura un (|U()lientde la forme/? + qx et un reste de la forme a!' x"^ -\- h" xr^ ; donc
- ^=^P -^ qx -\ ; j- -— ■
n'APUKS I.KS OliSEKVATlONS. 527
De lii il s'ensuit aussi que, si l'on divise l'unilé pai- If polviiômc v, ci (|u'()n continue l;i division jus(ju'à ce (ju'on ail dans le quolienl dryw termes tels (|ue/> -i- (/r, le reste sera tout divisible \y.\r x'^ et |)OMrra èlr'e i'eprés(;nté par^'-r-, s' étant une série de la Coinn'
On aura donc
donc
et de là
s' a"-hb"x
Or, en divisanl le numérateur de cette fraction par le dénominateur, il est clair qu'on aura un reste de la forme a"x^, en sorte que
s . , eif"x'
Donc, si l'on divise le polynôme s par le polynôme s\ et (pTon pousse la division jusqu'à ce qu'on ait dans le quotient deux termes tels que p ~\- q V , le reste sera nécessairement divisible par ,î - et pourra étie représenté par s"x'', s" étant une nouvelle série de la forme
\^\'x-\-\"x' + \"'x^ Ainsi on aura
s SX' <
(I ou
et de là
D'où il s'ensuit qu'en divisant le polynômes' par le polynôme s\ on aura nécessairement un quotient fini, tel que /j'-h q"'x.
Si la série proposée était récurrente d'un ordre quelconque supérieur, on y pourrait faire des raisonnements et des opérations semblables. De là je conclus, en général, que, pour leconnaître si la série proposée s est récurrente d'un ordre quelconque, il n'y a qu'à diviser d'abord l'unité par s jusqu'à ce. qu'on ait dans le quotient deux termes tels que/? -4- qx, et, dénotant le reste par s'x-, on divisera ensuite s par s' jusqu'à ce que l'on ait aussi dans le quotient deux termes comme /? H- ^'a:; dénotant de même le reste par 5"^-, on divisera encore^' par /' jusqu'à ce que l'on ait dans le quotient deux termes comme />' '+ qx"\ et ainsi de suite. Si la série s est véritablement récuriente d'un ordre quelconque n, l'opération se terminera nécessairement à la /^'""^ division; en sorte que le reste s^"''x- sera nu!; sinon l'opération ira à l'infini.
Lors donc qu'on sera parvenu à une division qui ne laissera aucun reste, on sera d'abord assuré que la série proposée est récurrente d'un ordre égal au quantième de cette division; et, de plus, les quotients trouvés donneront la fraction même d'où la série tire son origine.
Car ou a les équations suivantes
d'où
p -\- qx -\- — x^
Do 110
qx
Ainsi il n'y aura plus qu'à réduire cette fraction continue en une fraction ordinaire, qui sera par conséquent la fraction cherchée; et il est clair que cette fraction aura pour numérateur un polynôme du degré n — i , et pour dénominateur un polynôme du degré n, dont les coefficients donneront l'échelle de relation de la série.
Ayant trouvé ainsi la fraction génératrice de la série, on en déduira aisément l'expression du terme général de la série pai- les méthodes connues.
Corollaire.
11. Pour faire avec facilité la réduction dont il s'agit, il n'y auia qu'à considérer la suite des quotients
p-\-qx, p'+q'x,..., y^i"-') H- y'"-'>^, VI. 67
et ies disposer à rebours, de cette manière
ensuite on formera par leur moyen les quantités suivantes
l"',= {p(''-') -hq^''-'^x]'t,"-hx^'E,', ^iv- ^^^(«-.) ^ q{n-^)x) ^"'+ x^i;', »
et l'on aura"^^^;^ pour la fraction génératrice de la série récurrente.
Exemple I.
1 2 . Etant proposée la suite des nombres
I, 2, 3, 3, 7, 5, i5, 9, -Si, 17, 63, 33, 127, 65,...,
dont on ignore la loi, on demande si cette suite est récurrente, et quelle est, dans ce cas, l'expression de son terme général.
Ayant formé la série
.$ = I + Q-x -t- 3 .r 2 + Zx^ -\- <] X* -\- S x^ -\- 1 5 .r** H- 9 ^'
-h 3i.ar» H- 17X» -4- 63.^'»-+- 33.r" -4- 127a-'' + 65x'^ -f- . . . ,
on divisera, par la méthode ordinaire, l'unité par cette série, et l'on trouvera le quotient 1 — 207 et le reste x'^ -\-'^x'^ — x"* -\-..., qui est, comme l'on voit, tout divisible para:'-; on divisera donc ce reste par x-, et l'on aura la nouvelle série
*' = I H- 3x — x'^ -\- 9^' — Sjt" + Il x'^ — \2tx^
D'A PUES IJ<:S OBSKHVATIONS. 531
par laqiKîlle il l'audra maiiitenaiiL diviser la série s\ la division faite, on aura le quotient i — x cÀ le reste 70-- — 7a?'* -^ 21 £t.* 4-..., Ie(|uel, étant divisé para;^, donnera la série
s"=^ 7 — 7 :r -I- 2 1 x^— 2 1 j^' -f- 49^*— 49-*' 4- I o5:c" — io5x' -I- ?. 1 7 x» — 2 1 7 x" -f- . . . ;
on eonlinuera donc l'opéiation en divisant l'avanl-dernière série par ^",
et l'on trouvera le (iiiolient - H- — ; eoninie ensuite il ne i-este rien, ce '77
sera une marque que l'opération est terminée, et que la suite proposée est elTectivcnient récurrente du troisième ordre.
Pour en trouver maintenant la fraction génératrice, on considérera les trois quotients qu'on vient de trouver, et on les rangera ainsi par ordre, en commençant du dernier,
ensuite on en formera les quantités ^, ^', ^",... de cette manière
v// / xy/ ny ï -h 3x -\- 3x^
^"=(1— x)i' -hx'^ — ,
]^"'={l-'2X]l"-hx'l'-
et la fraction génératrice de la série s sera jj^,-, savoir
l -^ X — IX* — 2X^
d'où l'on voit d'abord que l'échelle de relation est
en sorte que, si t, t\ t" , t'" sont quatre termes consécutifs quelconques (le la série proposée, on aura
Pour trouver maintenant l'expression du terme général, on cherchera d'abord les facteurs du quadrinôme
l + X — IX^ — 2^%
lesquels sont
\-hX, I+^y'2, I — Xsfi,
et l'on décomposera ensuite la fraction
{\-\- x){\ -\- x\Jo.) ( r — ^ ^^2 )
en ces trois-ci
