|
[[AL Approfondissements de lycée|Approfondissements de lycée]]
'''Avant de commencer :''' Ce chapitre suppose des connaissances en
</blockquote>
De toute manière, nous ne ferons attention qu'aux belles propriétés algébriques et non aux valeurs numériques. A partir de maintenant, nous omettrons la condition pour que l'égalité soit vraie lorsque nous écrivons les séries de puissances.
Anyway we really only care about its nice algebraic properties not its numerical value. From now on we will omit the condition for equality to be true when writing out generating functions.
Considérons un cas plus général :
Consider a more general case:
:<math>
S = A + ABx + AB^2x^2 + AB^3x^3 + ...
</math>
whereoù ''A'' andet ''B'' aresont constantsdes constantes.
Nous pouvons déduire la ''forme fermée'' comme suit :
We can derive the ''closed-form'' as follows:
:<math>
\begin{matrix}
</math>
L'identité suivante que l'on a déduit ci-dessus prend du temps et un effort de mémorisation.
The following identity as derived above is worth investing time and effort memorising.
:<math>
A + ABx + AB^2x^2 + AB^3x^3 + ... = \frac{A}{1 - Bx}
</math>
===ExercisesExercices===
1. Trouver la forme fermée :
1. Find the closed-form:
:(a)<math> 1 - z + z^2 - z^3 + z^4 - z^5 + ... \ldots\,</math>
:(b)<math> 1 + 2z + 4z^2 + 8z^3 + 16z^4 + 32z^5 + ... \ldots\,</math>
:(c)<math> z + z^2 + z^3 + z^4 + z^5 + ... \ldots\,</math>
:(d)<math> 3 - 4z + 4z^2 - 4z^3 + 4z^4 - 4z^5 + ... \ldots\,</math>
:(e)<math> 1 - z^2 + z^4 - z^6 + z^8 - z^{10} + ... \ldots\,</math>
2. GivenPour theune closed-formforme fermée donnée, findtrouver aune functionfonction f(n) forpour theles coefficients ofde x<sup>n</sup>:
:(a)<math>\frac{1}{1 + z} </math> (HintAstuce : notenoter thele plussigne sign inplus theau denominatordénominateur)
:(b)<math>\frac{z^3}{1 - z^2} </math> (HintAstuce : obtainobtenir thela generatingsérie functionde forpuissances pour <math>\frac{1/}{(1 - z^2)}\,</math> firstd'abord, thenpuis multiplymultiplier bypar thel'expression appropriate expressionappropriée)
:(c)<math>\frac{z^2 - 1}{1 + 3z^3} </math> (HintAstuce : breakscinder intoen theune sumsomme ofde twodeux distinctformes closefermées formsdistinctes)
=== MethodMéthode ofde Substitutionsubstitution ===
Soit la forme suivante donnée :
We are given that:
:<math>1 + z + z<sup>^2</sup> + ...\ldots = \frac{1/}{(1 - z)}\,</math>
and we can obtain many other generating functions by substitution. ForPar exemple example: lettingsi <math>z = x<sup>^2\,</supmath>, nous weavons have:
:<math>1 + x<sup>^2</sup> + x<sup>^4</sup> + ...\dots = \frac{1/}{(1 - x<sup>^2)}\,</supmath>)
De manière similaire
Similarly
:<math>A + ABx + A(Bx)<sup>^2</sup> + ...\ldots = \frac{A/}{(1 - Bx)}\,</math>
isest obtainedobtenue byen lettingsubstituant z = Bx thenpuis multiplyingen the wholemultipliant l'expression byentière par A.
==== ExercisesExercices ====
1. WhatQuels aresont theles coefficients ofdes thepuissances powers ofde x :
:<math>\frac{1/}{(1 - 2x<sup>^3)}\,</supmath>)
2. WhatQuels aresont theles coefficients ofdes thepuissances powers ofde x (HintAstuce : takeextraire outun a factor offacteur d'1/2) :
:<math>\frac{1/}{(2 - x)}\,</math>
3. En regardant une expression appropriée de deux manières différentes, conclure que
3. By looking at an appropriate expression in two different ways, conclude that
:<math>\frac{1}{4}(1 + \frac{x}{4} + (\frac{x}{4})^2 + ...\ldots )= 1 + (x - 3) + (x - 3)^2 + ... \ldots\,</math>
Sont-elles réellement égales ?
Are they really equal?
=== Relations de récurrences linéaires ===
=== Linear Recurrence Relations ===
La suite de Fibonacci
The Fibonacci series
:1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
où chaque nombre, excepté le premier 2, est la somme des deux nombres précédents. Nous disons que les nombres sont ''reliés'' si la valeur qu'un nombre prend dépend des valeurs précédentes dans la suite. La suite de Fibonacci est un exemple de relation de récurrence, elle est exprimée par :
where each and every number, except the first two, is the sum of the two preceding numbers. We say the numbers are ''related'' if the value a number takes depends on the values that come before it in the sequence. The Fibonacci sequence is an example of a recurrence relation, it is expressed as:
:<math>
\begin{matrix}
\end{matrix}
</math>
whereoù x<submath>nx_n\,</submath> isest thele (''n''+ 1)thème numbernombre inde thela sequencesuite. NoteNoter thatque thele firstpremier numbernombre indans thela sequencesuite isest denotednoté x<submath>0x_0\,</submath>. GivenCette thisrelation recurrencede relationrécurrence donnée, thela question weque wantnous tovoulons askposer isest "canpouvons-nous wetrouver findune aformule formulapour for thele (''n''+1)thème numbernombre indans thela suite sequence?". TheLa answerréponse isest yesoui, butmais beforeavant we come to thatcela, let's look atregardons somequelques examplesexemples.
==== ExampleExemple 1 ====
TheLes expressions
:<math>
\begin{matrix}
\end{matrix}
</math>
definedéfinit a recurrenceune relation de récurrence. TheLa suite sequenceest is: 1, 1, 5, 13, 41, 121, 365... FindTrouver aune formulaformule forpour thele (''n''+1)thème numbernombre indans thela sequencesuite.
'''Solution'''
Soit G(z) la série de puissances de la suite, ce qui signifie que le coefficient de chaque puissance (en ordre croissant) est le nombre correspondant dans la suite. Donc, la série de puissances ressemble à
Let G(z) be generating function of the sequence, meaning the coefficient of each power (in ascending order) is the corresponding number in the sequence. So the generating functions looks like this
:<math>
G(z) = 1 + z + 5z^2 + 13z^3 + 41z^4 + 121z^5 + ...
</math>
NowMaintenant, bypar aune seriessérie of algebraicde manipulations algébriques, wenous canpouvons findtrouver thela closedforme formfermée ofde thela generatingsérie functionde andpuissances fromet thatà partir de là, thela formulaformule forpour eachchaque coefficient
:<math>
\begin{matrix}
\end{matrix}
</math>
bypar definitiondéfinition x<sub>n</sub> - 2x<sub>n - 1</sub> - 3x<sub>n - 2</sub> = 0
:<math>
\begin{matrix}
\end{matrix}
</math>
bypar thela [[HSE PartialAL Fractions partielles|methodméthode of partialdes fractions partielles]], nous weobtenons get:
:<math>
G(z) = \frac {1} {2} \times \frac {1} {1 - 3z} + \frac {1} {2} \times \frac {1} {1 + z}
</math>
chaque partie de la somme est une forme fermée reconnaissable. Nous pouvons conclure que :
each part of the sum is in a recognisable closed-form. We can conclude that:
:<math>
x_n = \frac {1} {2} \times 3^n + \frac {1} {2} \times (-1)^n
</math>
le lecteur peut facilement vérifier la précision de la formule.
the reader can easily check the accuracy of the formula.
==== ExampleExemple 2 ====
:<math>
\begin{matrix}
\end{matrix}
</math>
FindTrouver aune formule non-recurrent formularécurrente forpour x<sub>n</sub>.
'''Solution'''
Soit G(z), la série de puissances de la suite décrite ci-dessus.
Let G(z) be the generating function of the sequence described above.
:<math>G(z) = x_0 + x_1z + x_2z^2 + ...</math>
\end{matrix}
</math>
ThereforePar conséquent x<sub>n</submath>x_n = 1\,</math>, quel forque allsoit n.
====Example 3====
Une relation de récurrence linéaire est définie par :
A linear recurrence relation is defined by:
:<math>
\begin{matrix}
\end{matrix}
</math>
FindTrouver thela generalformule formulagénérale forpour x<sub>n</sub>.
'''Solution'''
LetSoit G(z) bela thesérie generatingde functionpuissances ofde the recurrencela relation de récurrence.
:<math>G(z)(1 - z - 6z^2) = x_0 + (x_1 - x_0)z + (x_2 - x_1 - 6x_0)z^2 +...</math>
:<math>G(z)(1 - z - 6z^2) = 1 + z^2 + z^3 + z^4 + ...</math>
</math>
Par conséquent
Therefore
:<math> x_n = -\frac{1}{6} + \frac{7}{15}(-2)^n + \frac{7}{10}3^n</math>
==== ExercisesExercices ====
1. Derive the formula for the (''n+1'')th numbers in the sequence defined by the linear recurrence relations:
:<math>
| 